Explication de l'exécution de la BFS et DFS

Pourquoi les temps de fonctionnement de la BFS et DFS O(V+E), surtout quand il y a un nœud qui a dirigé bord d'un nœud qui peut être atteint à partir du sommet, comme dans cet exemple dans le site suivant

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

InformationsquelleAutor miss24 | 2011-07-27
  1. 40

    E est l'ensemble de toutes les arêtes dans le graphe G={V,E}. Donc, |E| est le nombre d'arêtes dans le graphe.

    Cela seul devrait suffire à vous convaincre que la complexité globale ne peut pas être |V| fois |E|, puisque nous ne sommes pas itération sur toutes les arêtes dans le graphe pour chaque vertex.

    Dans la liste d'adjacence de la représentation, pour chaque sommet v, nous ne traverse ces nœuds qui sont adjacentes.

    Le |V| facteur de l' |V|+|E| semble venir à partir du numéro de la file d'attente des opérations de fait.

    Noter que la complexité de l'algorithme dépend de la structure de données utilisée.
    effectivement nous sommes en visitant chaque pièce de l'information présente dans la représentation du graphe, c'est pourquoi pendant la matrice de la représentation du graphe, la complexité devient V au carré.

    Citant le Cormen,

    ", Les opérations de replacement et la file d'attente prendre en O(1), afin que la
    total du temps consacré aux opérations de mise en attente est O( V). En raison de la proximité
    liste de chaque sommet est analysée seulement lorsque le sommet est retiré, chaque
    liste d'adjacence est analysé plus d'une fois. Puisque la somme des longueurs
    de toutes les listes d'adjacence est Θ(E), le temps total passé dans la numérisation
    les listes d'adjacence est O( E). Les frais généraux pour l'initialisation est O( V),
    et ainsi, le temps total d'exécution de la SECTION est de O( V + E)."

    InformationsquelleAutor Abhijeet Kashnia
  2. 18

    Cette question consommer comme 4 heures de mon temps, mais finalement, je pense que j'ai un moyen facile d'obtenir de l'image, au début j'étais tenté de dire O ( V * E ).

    Résumant l'algorithme que vous trouverez dans Cormen, qui est le même sur http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm vous avez quelque chose comme ceci :

    pour (vi, V)
    Certains O(1) instructions
    pour ( e Adj (vi) )
    { Certains O(1) instructions
    }

    La question est de savoir comment de nombreuses instructions sont exécutées ici ? qui sera le Sigma-Somme (Adj(vi)), et cette valeur est supérieure délimitée par 2|E|.

    Au début, nous pensons automatiquement à propos de multiplier le nombre d'itérations des boucles internes et externes, mais dans ce cas, le nombre total d'itérations de la boucle interne est une fonction de l'extérieur itérateur, donc pas de multiplication est possible.

    • Merci à vous, @Jose Francisco. J'ai trouvé cette réponse plus utile et perspicace que celle actuellement avec un maximum de upvotes. 🙂
    InformationsquelleAutor Jose Francisco
  3. 8

    Vous visitez chaque arête au plus deux fois. Il y a E des bords. Donc il y aura 2*E bord des opérations de visite. Plus les nœuds ceux qui ont pas de bords ou en d'autres termes, le degré 0. Il peut y avoir au plus V tels noeuds. D'où la complexité s'avère être, O(2*E + V) = O(E + V)

    InformationsquelleAutor Fallen
  4. 1

    Il devient clair quand vous voyez un graphique comme une structure de données représenté comme une liste adjacente

    Explication de l'exécution de la BFS et DFS

    Vous voir Sommets: A,B,C,D,E et à côté des sommets pour chaque Vert/Nœud dans la liste de ceux vert. Vous avez à "voir" toutes les cases afin de vérifier si elle a été "visité" en cas de cyclique graphique ou vous allez à travers tous les enfants si c'est l'arbre comme graphique

    InformationsquelleAutor AleC
  5. 0

    Vous itérer sur les |V| nœuds, au plus |V| temps. Depuis que nous avons une limite supérieure de |E| bords au total dans le graphique, nous allons vérifier à la plupart des |E| bords. Différents sommets varient nombre de nœuds adjacents, de sorte que nous ne peut pas il suffit de multiplier |V|*|E| (cela signifie que, pour chaque sommet, nous traversons |E| bords, ce qui n'est pas vrai, |E| est le nombre total d'arêtes sur tous les nœuds), plutôt, nous vérifions V nœuds, et nous vérifions sur un total de E bords. À la fin, nous avons O(|V|+|E|)

    Pour DFS, c'est quelque chose de semblable, nous parcourir l'ensemble de sommets listes d'adjacence, l'appel à DFS(v) si cela n'a pas été visité, ce qui signifie que nous subissons |V| pas de temps, plus le laps de temps nécessaire pour visiter les nœuds adjacents (il s'agit de former un bord, et nous avons un total de |E| bords, donc O(V+E) temps.

        private static void visitUsingDFS(Node startNode) {
        if(startNode.visited){
            return;
        }
        startNode.visited = true;
        System.out.println("Visited "+startNode.data);
        for(Node node: startNode.AdjacentNodes){
            if(!node.visited){
                visitUsingDFS(node);
            }
        }
    }
    InformationsquelleAutor Bavinho