Uitleg over runtimes van BFS en DFS

Waarom zijn de looptijden van BFS en DFS O(V+E), vooral wanneer er een knooppunt is met een gerichte rand naar een knooppunt dat kan worden bereikt vanaf het hoekpunt, zoals in dit voorbeeld op de volgende site

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


Antwoord 1, autoriteit 100%

E is de verzameling van alle randen in de grafiek, als G={V,E}. Dus, |E| is het tellen van alle randen in de grafiek.

Dit alleen zou voldoende moeten zijn om u ervan te overtuigen dat de algehele complexiteit niet |V| . kan zijn keer |E|, aangezien we niet alle randen in de grafiek voor elk hoekpunt herhalen.

In de weergave van de aangrenzende lijst gaan we voor elk hoekpunt v alleen door die knooppunten die ernaast liggen.

De |V| factor van de |V|+|E| lijkt te komen van het aantal uitgevoerde wachtrijbewerkingen.

Merk op dat de complexiteit van het algoritme afhangt van de gebruikte datastructuur.
in feite bezoeken we elk stukje informatie dat aanwezig is in de weergave van de grafiek, daarom wordt voor de matrixweergave van de grafiek de complexiteit V-kwadraat.

Citaat van Cormen,

“De operaties van wachtrijen en de wachtrijen kosten O(1) tijd, dus de
totale tijd besteed aan wachtrijbewerkingen is O( V). Omdat de nabijheid
lijst van elk hoekpunt wordt alleen gescand wanneer het hoekpunt uit de wachtrij wordt gehaald, elk
aangrenzende lijst wordt maximaal één keer gescand. Aangezien de som van de lengtes
van alle aangrenzende lijsten is Θ(E), de totale tijd besteed aan scannen
aangrenzende lijsten is O(E). De overhead voor initialisatie is O( V),
en dus is de totale looptijd van BFS O( V + E).”


Antwoord 2, autoriteit 52%

Dit probleem nam ongeveer 4 uur van mijn tijd in beslag, maar uiteindelijk denk ik dat ik een gemakkelijke manier heb om de foto te krijgen, in het begin kwam ik in de verleiding om O ( V * E ) te zeggen.

Een samenvatting van het algoritme dat je in Cormen vindt, dat is hetzelfde op http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htmje hebt zoiets als dit:

for (vi in V)
{
   Some O(1) instructions
   for ( e in Adj(vi) ) {
      Some O(1) instructions
   }
}

De vraag is hoeveel instructies hier worden uitgevoerd? dat is de Sigma-Sum (Adj(vi)), en deze waarde wordt als bovengrens begrensd door 2|E|.

In het begin denken we automatisch aan het vermenigvuldigen van het aantal iteraties van de binnenste en buitenste lussen, maar in dit geval is het totale aantal iteraties op de binnenste lus een functie van de buitenste iterator, dus vermenigvuldiging is niet mogelijk .


Antwoord 3, autoriteit 24%

Je bezoekt elke rand maximaal twee keer. Er zijn E-randen. Er zullen dus 2*E edge-bezoekoperaties zijn. Plus de knopen die geen randen hebben of met andere woorden, met graad 0. Er kunnen maximaal V zulke knopen zijn. Dus de complexiteit blijkt te zijn, O(2*E + V) = O(E + V)


Antwoord 4, autoriteit 15%

Het wordt duidelijk wanneer u een grafiek ziet als een gegevensstructuur die wordt weergegeven als een aangrenzende lijst

Je ziet Vertices: A,B,C,D,E en aangrenzende hoekpunten voor elke Vert/Node als lijst van die vert. Je moet alle vakjes “zien” om te controleren of het is “bezocht” in het geval van een cyclische grafiek of je gaat gewoon door alle kinderen als het een boomachtige grafiek is


Antwoord 5

Je herhaalt de |V| knooppunten, voor maximaal |V| keer. Omdat we een bovengrens hebben van |E| randen in totaal in de grafiek, we controleren maximaal |E| randen. Verschillende hoekpunten hebben een verschillend aantal aangrenzende knopen, dus we kunnenniet zomaar |V|*|E| vermenigvuldigen. (het betekent dat we voor elk hoekpunt |E|-randen doorlopen, wat niet waar is, |E| is het totale aantal randen over alle knooppunten), in plaats daarvan controleren we V-knooppunten en controleren we in totaal E randen. Aan het einde hebben we O(|V|+|E|)

Voor DFS is het iets soortgelijks, we doorlopen alle lijsten met aanliggende hoekpunten en roepen DFS(v) aan als het niet is bezocht, wat betekent dat we |V| tijdstappen, plus de tijd die nodig is om aangrenzende knooppunten te bezoeken (in wezen vormen deze een rand, en we hebben in totaal |E| randen, dus O(V+E) tijd.

   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);
            }
        }
    }

Other episodes