Pourquoi l'heure de la complexité de DFS et BFS dépend de la façon dont le graphe est représenté?

Le site http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html explique que lorsqu'une liste d'adjacence est utilisée alors, DFS et BFS ont complexité O(V+E), et si une matrice de contiguïté est utilisé, la complexité est O(V2). Pourquoi est-ce?

Cette question semble être hors-sujet, car il n'est pas sur un programme d'ordinateur ou un langage de programmation.

OriginalL'auteur Nitish Jain | 2014-05-29

  1. 24

    Dans les deux cas, le moteur d'exécution dépend de combien de temps il faut pour itérer à travers le sortant bords d'un nœud donné. Avec une liste d'adjacence, l'exécution est directement proportionnelle au nombre de sortants bords. Depuis chaque nœud est visité une fois, le coût est le nombre de nœuds et le nombre d'arêtes, ce qui est O(m + n). Avec suis matrice de contiguïté, le temps requis pour trouver tous les bords de est O(n), car tous les n colonnes de la ligne pour un nœud doit être inspecté. Résumé à travers tous les n nœuds, cela fonctionne à O(n2).

    Espérons que cette aide!

    merci beaucoup, je l'ai eu... j'ai été en enfer confus que sur wikipédia aussi un espace de complexité O(n+m) a été décrit pour la liste d'adjacence et O(n^2) matrice de contiguïté, mais le temps de la complexité a été donné comme O(n+m)...

    OriginalL'auteur templatetypedef

  2. 0

    Vous devez noter que pour l'exploration de chaque vertex temps nécessaire pour explorer, il est seulement égale à c*x où x est le indegree du vertex.Puisque nous sommes intéressés dans la recherche, la complexité, la durée totale serait c1*x1+c2*x2...cnxn pour n nœuds.La prise de max(ci)=d,nous voyons que le temps total est de <=d(somme des indegrees de tous les sommets)=d*2 m=O(m).Ici, nous avons calculé le temps pour pas un sommet, mais de tous les sommets sont pris ensemble.Mais le replacement opération prend du temps O(n), de sorte overalll O(n+m).

    OriginalL'auteur aman khunt