DFS pour les graphes non orientés whithout deux recherches

Question

Bonjour,

Je suis un débutant dans le monde graphique et j'ai quelques questions au sujet de DFS, que je ne l'ai pas trouvé dans les autres sujets.

Je pris le code DFS du site:

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

(je pris la mise en œuvre Java)

Le graphique est construit dans la fonction principale:

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

mais si je change la première ligne comme ceci:

g.addEdge(1, 0); 

Le résultat DFS est différent car il s'agit d'un graphe orienté. Alors quelle est la meilleure façon d'implémenter le DFS comme un graphique non orienté, sans avoir besoin de faire deux "recherches" sur la liste? (Je pense que c'est la façon la plus simple de le faire). J'ai trouvé plusieurs façons d'implémenter DFS aux graphes orientés mais pas aux graphes non orientés. DFS serait-il juste utilisé pour des graphes orientés?

Quel est le meilleur livre sur les graphiques?

Cordialement

Antonio

Answer 1

Le code que vous utilisez est en fait assez bonne. La façon la plus simple de gérer cela est de changer le graphique et non l'implémentation de DFS. Donc, vous changez la fonction addEdge comme suit pour ajouter le bord dans les deux sens:

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