Représentation graphique en C++

Question

Je vais dans un livre The Design and Analysis of Computer Algorithms En lisant le chapitre graphique, je suis en train de mettre en œuvre DFS. Par définition La lecture de cet algorithme, il dit, graphique G=(V,E) partiions les bords de E en deux ensembles T et B. Un bord (v,w) est dans T ensemble si w n'a pas vertes été précédemment visitée quand nous sommes au sommet v considérant tranchant (v,w), bord autrement `(v, w) est dans l'ensemble B.

Fondamentalement, son algorithme de DFS sera donne moi un nouveau graphique qui sera G=(V,T). Je veux savoir comment on pourrait l'implémenter en C++.

J'ai essayé d'utiliser adjacency list, mais je suis confondez est-il nécessaire de stocker edges de juste un map de list devrait être bon.

Answer 1

En VTK, les arêtes sont stockées dans un vector et elles stockent toujours une paire (v, w). Près de ce vecteur, il y a 2 autres vecteurs de vecteurs pour stocker les bords d'entrée et de sortie des noeuds du graphe. Quand un nouveau bord est ajouté, il a ajouté au vecteur de bord, ses noeuds (v, w) sont ajoutés aux vecteurs de vecteurs d'entrée et de sortie, aussi.

Answer 2

Je ne suis pas tout à fait clair sur ce que votre question est exacte. Je suppose que vous demandez comment maintenir deux ensembles T et B pour distinguer les arêtes qui ont été visitées d'arêtes qui n'ont pas été au cours de DFS. Je pense que la façon la plus simple de le faire est d'ajouter un champ booléen "visité" à la structure du nœud dans votre liste d'adjacence. La valeur initiale de ce champ pour tous les nœuds est "false". Supposons que dans le cas ci-dessus, lorsque DFS arrive à v, et que le front (v, w) ne soit pas visité, alors le nœud sur la liste de v qui correspond à w aurait une valeur "false" pour "visited" à ce moment là . Sinon, il aura la valeur "vrai".

Je pense que l'auteur essaie juste de vous donner l'idée que les arêtes seront classées en deux catégories: visitées et non visitées à la fin de DFS. Mais je ne pense pas garder deux ensembles explicites en maintenant ces deux types d'arêtes sont nécessaires. Vous pouvez toujours imprimer les arêtes visitées après DFS en fonction de leur valeur "visitée" mise à jour.