besoin d'un algorithme de graphique similaire à DFS

Question

Je suis curieux de savoir s'il existe un algorithme de graphe spécifique qui traverse un graphe orienté acyclique non pondérée par le choix d'un noeud de départ et ensuite de procéder via DFS. Si un noeud est rencontré qui a prédécesseurs Unsearched alors il devrait BackTrack les chemins entrants jusqu'à ce que tous les chemins pour commencer ont été explorées.

J'ai trouvé un wikipedia catégorie pour les algorithmes de graphique mais il y a une petite mer de algorithmes ici et je ne suis pas familier avec la plupart d'entre eux.

EDIT: Exemple: étant donné le graphique {AB, EB, BC, BD}, traversée comme: {A, B, E, B, C, D} ou {ordre unique en A, B, E, C, D}. Notez cet algorithme à la différence BFS ou DFS n'a pas besoin de recommencer à un nouveau nœud de départ si tous les chemins du premier noeud de départ sont épuisées.

Answer 1

Dans DFS, vous choisissez habituellement le sommet à visiter après u basées sur les bords à partir de u. Vous voulez choisir en fonction d'abord sur les bords qui se terminent à u. Pour ce faire, vous pourriez avoir un graphique Transpose info, et essayer d'obtenir le sommet à partir de là premier.

Ce serait quelque chose comme ceci:

procedure dfs(vertex u)
  mark u as visited
  for each edge (v, u) //found in transpose graph
    if v not visited
      dfs(v)
  for each edge (u, w)
    if v not visited
      dfs(w)

Answer 2

Ce que vous cherchez est le genre topologique. Pour autant que je sache, il n'y a aucun moyen facile de parcourir un graphique dans son ordre topologiquement sans précalcul triée.

La méthode standard pour obtenir le topsort est de faire une norme DFS, puis stocker les nœuds visités afin de leur temps de visite. Enfin, inverser les noeuds et le tour est joué, vous les avez dans l'ordre que vous désirez.

pseudocode:

list topsort

procedure dfs(vertex u)
  mark u as visited
  for each edge (u, v)
    if v not visited
      dfs(v)
  add u to the back of topsort

La topsort liste contiendra alors les sommets dans l'ordre inverse que vous voulez. Il suffit de renverser les éléments de topsort pour corriger cela.

Answer 3

Si vous cherchez topological sort, vous pouvez aussi le faire, étant donné un liste contiguïté (ou une liste des arêtes (u,v) que vous pouvez prétraiter dans le temps de O(E)):

list top_sort( graph in adjacency list )
     parent = new list
     queue = new queue
     for each u in nodes
         parent(u) = number of parents
         if ( parent(u) is 0 ) // nothing points to node i
             queue.enqueue( u )

     while ( queue is not empty )
         u = queue.pop
         add u to visited
         for each edge ( u, v )
             decrement parent(v) // children all have one less parent
             if ( parent(v) is 0 )
                 queue.enqueue( v )

Étant donné un adjacency list (ou une liste des arêtes (u,v)), c'est O( V + E ), puisque chaque bord est touché deux fois - une fois pour augmenter, une fois à décrémenter, dans le temps de O(1) chacun. Avec une file d'attente normale, chaque Vertice sera également traité par la file d'attente au maximum deux fois - ce qui peut être fait aussi en O(1) avec une file d'attente standard

.

Notez que cela diffère de la DFS (au moins une mise en œuvre straight-up) dans les forêts qu'il gère.

Une autre note intéressante est que si vous queue substitut avec un priority_queue imposant une sorte de structure / commande, vous pouvez réellement retourner les résultats triés dans un ordre.

Par exemple, pour un graphe de dépendance de classe canonique (vous ne pouvez prendre la classe X si vous avez pris la classe Y):

100:
101: 100
200: 100 101
201: 
202: 201

vous obtiendriez probablement, en conséquence:

100, 201, 101, 202, 200

mais si vous le changez de sorte que vous voulez toujours prendre des cours les plus petits numéros, vous pouvez facilement changer pour revenir:

100, 101, 200, 201, 202