Je sais qu'il y a deux façons de représenter mon graphique: on utilise une matrice, et l'autre utilise une liste.
Si j'utilise une matrice, je dois retourner tous les bits de la matrice. Ça ne prend pas de temps o (v ^ 2)?
Si j'utilise une liste, je ne dois pas traverser chaque liste, une à une et créer un nouvel ensemble? Cela semblerait prendre o (v + e) temps linéaire. Suis-je correct?
Alors, j'ai une autre question ici. Considérez, par exemple, que j'utilise l'algorithme Dijkstra sur mon graphique (une matrice ou une liste), et nous utilisons une file d'attente prioritaire pour la structure de données derrière la scène. Existe-t-il une relation de représentation graphique et de l'utilisation de la structure de données? Cela affectera-t-il la performance de l'algorithme?
Supposons que je devais utiliser une liste pour les représentations et une file d'attente prioritaire pour l'algorithme de Dijkstra, il y aurait une différence entre la matrice et l'utilisation de la file d'attente prioritaire pour Dijkstra?
Je suppose que cela concerne maqueur opération uniquement? Ou ils n'ont pas de différence du tout?
4 Réponses :
Je pense que l'inverser le graphique en parcourant la liste prend o (v 2 ), car pour chaque sommet, vous devez ajouter ou supprimer des bords (V-1).
Quant à l'algorithme de Dijkstra, si vous le comprenez, si vous représentez le graphique en tant que matrice ou liste, l'algorithme prend O (v 2 ), mais certaines autres structures de données sont plus rapides. Le plus rapide connu est un tas de fibonacci, qui donne O (E + Vlogv).
Que diriez-vous si je garde deux listes? La liste des bords entrants et la liste des bords sortants, cela semble être une bonne idée?
@Timothyleung: Pourquoi? Je ne vois pas comment cela donnerait un avantage sur une liste des bords sortants.
@Beta J'imagine que ce ne serait que O (v ^ 2) lorsque le graphique est dense. Ne considérez pas de bords. Vous ne feriez que O (1) travailler à chaque sommet, donc O (V). Ainsi, les bords doivent entrer en jeu dans la complexité.
@Dukeling: parlez-vous de renversement ou de Dijkstra?
@Beta inversion , comme dans l'inverse la direction de tous les bords. On dirait que vous l'avez peut-être interprété comme un Complément Opération (supprimer tous les bords existants et créer des bords où il n'y a pas existait). Peut-être que c'est ce que OP voulait, je ne suis pas sûr.
@Dukeling: l'OP a dit "Si j'utilise Matrix, je dois retourner tous les bits de la matrice." J'ai déduit qu'il voulait dire le complément. S'il voulait dire inverser la direction des bords, c'est OUI, c'est O (v + e) et en conservant deux listes pourraient faire une différence, en fonction de la mise en œuvre.
@Beta: Garder une deuxième liste est inutile. En tant que collapsar mentionné dans les commentaires, des instructions d'inverser dans une matrice peuvent être accomplies en passant de la principale indexation majeure à Col-major (ou inversement) en échangeant simplement les indices à chaque recherche. Vous pouvez utiliser la même logique pour une liste d'adjacence et rechercher la liste des nœuds de destination (inversée) pour le nœud source (inversé). Si un bord existe du nœud P au noeud Q dans le graphique d'origine, un bord existe du nœud Q au nœud P dans le graphique inversé de direction.
Au fait, juste au cas où la puissance que l'OP signifiait vraiment compléter, vous pouvez utiliser des tours similaires sans dupliquer ou la transformation de la matrice / la liste.
Inverser les listes de adjacence d'un graphique dirigé peut être effectuée en temps linéaire. Nous traversons le graphique une seule fois. L'ordre de complexité sera O (| v | + | e |).
public static HashMap<Character,ArrayList <Character>> getReversedAdjLists(RGraph g)
{
HashMap <Character, ArrayList<Character>> revAdjListMap = new HashMap <Character, ArrayList<Character>>();
Set <Character> oldLabelSet = g.adjListMap.keySet();
for(char oldLabel:oldLabelSet)
{
ArrayList<Character> oldLabelList = g.adjListMap.get(oldLabel);
for (char newLabel : oldLabelList)
{
ArrayList<Character> newLabelList = revAdjListMap.get(newLabel);
if (newLabelList == null)
{
newLabelList = new ArrayList<Character>();
newLabelList.add(oldLabel);
}
else if ( ! newLabelList.contains(oldLabel))
{
newLabelList.add(oldLabel);
}
revAdjListMap.put(newLabel, newLabelList);
}
}
return revAdjListMap;
}
Bonne réponse. J'essaie initialement de le faire avec un tableau 2D statique, mais la transposition de cette matrice (pour réverser l'inversion) est O (n ^ 2) Je suis à peu près sûr.
Y a-t-il une possibilité d'une solution spatiale constante? Est-il possible d'inverser le graphique en place?
G = {"A":["B", "C","D"],"B":["C", "E"], "C":["D", "E"],"D":[],"E":["D"] }
res ={}
for k in G.keys():
for val in G[k]:
if val not in res.keys():
res[val] = [k]
else:
res[val].append(k)
print(res)
Étant donné que je vois quelques commentaires posant des questions sur une transposition forte> en place forte> graphique (inversion), voici ma version de celle-ci. Veuillez noter que cela ne fonctionnera que sur Dags.Feedback et les suggestions d'amélioration seraient les bienvenues
def transpose(G):
"""
Return the transpose of a directed graph i.e. all the edges are reversed (In Place)
"""
#note this is not a standard lib function afaik and you would have to
#implement topological sort but that should be easy
topsort = topological_sort(G)
topsort.reverse() # we want to process starting from sink node
for v in topsort:
for node in G[v]:
G[node].append(v)
# remove all older members of the vertex 'v'
G[v] = []
print(G)
Traverses des listes de adjacence ne se produit pas en général linéaire en général comme e = o (v ^ 2).
@Collapsar IT TOUJOURS arrive en temps linéaire avec la relation avec les sommets et les bords . Pour définir la complexité du temps uniquement sur une partie de l'entrée (juste juste des sommets) (sans l'indiquer explicitement) semble quelque peu illogique, surtout lorsque le temps est directement lié à une autre partie de l'entrée (mais je peux «t affirment que beaucoup de gens peuvent le définir comme vous l'avez fait). Et e = o (v ^ 2) concerne des graphiques denses. Les graphiques clairsemés sont E = O (v).
@dukeling Vous avez raison de souligner que la réduction de la «taille» d'un problème à un seul scalaire implique un manque de précision. OTOH, la notation Big-Oh décrit le pire des cas et, en considérant des graphiques, sans contraintes supplémentaires, le pire cas signifie E = O (v ^ 2). Être précis, O (v ^ 2) n'est pas correct pour l'inversion des bords sur une matrice d'adjacence non plus - si la représentation sportive un drapeau principal-major-Col-major, la transposition est O (1).