Explication des durées d'exécution DE BFS et DFS

E est L'ensemble de tous les bords du graphique, en G = {V,E}. Donc, |E / est le compte de tous les bords dans le graphique.

cela devrait suffire à vous convaincre que la complexité globale ne peut pas être |V| times |E|, puisque nous ne sommes pas en train d'itérer sur tous les bords du graphe pour chaque sommet.

dans la représentation de la liste de contiguïté, pour chaque vertex v, nous ne traversons que les noeuds qui lui sont adjacents.

le facteur / V / du |V / + / E / semble provenir du nombre d'opérations en file d'attente effectuées.

Notez que la complexité de l'algorithme dépend de la structure de données utilisée. en effet, nous visitons chaque élément d'information présent dans la représentation du graphe, c'est pourquoi pour la représentation matricielle du Graphe, la complexité devient V au carré.

citant Cormen,

ce numéro prend environ 4 heures de mon temps, mais finalement je pense que j'ai un moyen facile pour obtenir le tableau, au début j'ai été 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 in V) Some O (1) instructions pour (E en Adj (vi) ) { Certains O(1) instruction }

la question Est de savoir combien d'instructions sont exécutées ici ? ce sera le Sigma-Sum (Adj (vi)), et cette valeur est limitée en haut par 2|E|.

au début nous pensons automatiquement à multiplier le nombre d'itérations des boucles intérieure et extérieure, mais dans ce cas le nombre total d'itérations sur la boucle intérieure est une fonction de l'itérateur extérieur, donc aucune multiplication n'est possible.

vous visitez chaque bord au plus deux fois. Il y a des bords en E. Il y aura donc des opérations de 2 * e edge visit. Plus les noeuds qui n'ont pas de bords ou en d'autres termes, avec le degré 0. Il peut y avoir au plus V tels noeuds. Donc la complexité s'avère être, O (2*E + V) = O (E + V)

vous itérez sur les noeuds / V|, pour AU PLUS| V / fois. Puisque nous avons une limite supérieure de |E| edges au total dans le graphique, nous vérifierons au plus |e| edges. Différents sommets auront un nombre variable de noeuds adjacents, donc nous ne peut pas il suffit de multiplier / V / * / E| (cela signifie que pour chaque vertex, nous traversons |e| Arges, ce qui n'est pas vrai, |E| est le nombre total d'arêtes sur tous les noeuds), plutôt, nous vérifions les noeuds V, et nous vérifions un total d'arêtes E. À la fin, nous avons O (|V|+|E/)

pour DFS, c'est quelque chose de similaire, nous bouclons toutes les listes de contiguïté des sommets, appelant DFS(v) si elle n'a pas été visitée, ce qui signifie que nous encourons |V| Pas de temps, plus le temps encouru pour visiter les noeuds adjacents (essentiellement, ceux-ci forment 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);
            }
        }
    }