DFS für ungerichtete Graphen whithout zwei Suchen

Question

Guten Morgen,

ich ein Neuling in der Grafik Welt bin, und ich habe einige Fragen zu DFS, die ich nicht in den anderen Themen gefunden.

ich die DFS-Code der Seite dauerte:

http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

(ich die Java-Implementierung nahm)

Die Grafik in der Hauptfunktion eingebaut:

g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(1, 2); 
    g.addEdge(2, 0); 
    g.addEdge(2, 3); 
    g.addEdge(3, 1); 
    g.addEdge(2, 4); 

aber Wenn ich die erste Zeile wie folgt ändere:

g.addEdge(1, 0); 

Das DFS-Ergebnis ist anders, weil es ein gerichteter Graph ist. Was ist also der beste Weg, das DFS als ungerichtete Graphen zu implementieren, ohne dass zwei Suchen in der Liste durchgeführt werden müssen? (Ich denke, das ist der einfachste Weg, das zu tun). Ich habe mehrere Möglichkeiten gefunden, DFS zu gerichteten Graphen, aber keine zu ungerichteten Graphen zu implementieren. Wäre DFS nur für gerichtete Graphen gedacht?

Was ist das beste Buch über Graphen?

Grüße

Antonio

Answer 1

Der Code, den Sie verwenden, ist eigentlich ziemlich gut. Der einfachste Weg, damit umzugehen, ist, den Graphen zu ändern, nicht die Implementierung von DFS. So können Sie die Funktion addEdge wie folgt ändern die Kante in beiden Richtungen hinzuzufügen:

void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
    adj[w].push_back(v); 
}