Precisa de um algoritmo de gráfico semelhante ao DFS

Question

Estou curioso para saber se houver um algoritmo de gráfico específico que atravessa um gráfico direcionado acíclico não ponderado, escolhendo um nó de partida e depois prosseguindo via DFS. Se for encontrado um nó que tenha predecessores não pesquisados, ele deve rastrear os caminhos de entrada até que todos os caminhos a serem iniciados tenham sido explorados.

Achei um Categoria da Wikipedia para algoritmos de gráfico Mas há um pequeno mar de algoritmos aqui e não estou familiarizado com a maioria deles.

EDIT: Exemplo: Dado o gráfico {AB, EB, BC, BD}, Traverse como: {a, b, e, b, c, d} ou ordem única como {a, b, e, c, d}. Observe que esse algoritmo, diferentemente do BFS ou DFS, não precisa começar de novo em um novo nó de partida se todos os caminhos do primeiro nó de partida estiverem esgotados.

Answer 1

No DFS, você geralmente escolhe o vértice a ser visitado após U com base nas bordas que começam em u. Você deseja escolher com base primeiro nas bordas que terminam em u. Para fazer isso, você pode ter um Gráfico de transposição informações e tente obter o vértice a partir daí primeiro.

Seria algo assim:

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

O que você está procurando é do tipo topológico. Tanto quanto sei, não há maneira fácil de atravessar um gráfico em sua ordem topologicamente classificada sem nenhuma pré -computação.

A maneira padrão de obter o TOPSORT é fazer um DFS padrão e, em seguida, armazenar os nós visitados em ordem de seus tempos de visita. Finalmente, reverte esses nós e pronto, você os tem na ordem que deseja.

Pseudo-código:

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

A lista topsort então conterá os vértices na ordem inversa que você deseja. Basta reverter os elementos do TOPSORT para corrigir isso.

Answer 3

Se você está procurando topological sort, você também pode fazer isso, dado um Lista de adjacência (ou uma lista de arestas (u,v) em que você pode pré -processar O(E) Tempo):

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 )

Dado um adjacency list (ou uma lista de arestas (u,v)), isto é O( V + E ), uma vez que cada borda é tocada duas vezes - uma vez para aumentar, uma vez para diminuir, em O(1) tempo cada. Com uma fila normal, cada vértice também será processado pela fila no máximo duas vezes - o que também pode ser feito em O(1) com uma fila padrão.

Observe que isso difere do DFS (pelo menos uma implementação direta), pois lida com as florestas.

Outra nota interessante é que, se você substituir queue com um priority_queue Impor algum tipo de estrutura/pedidos, você pode retornar os resultados classificados em algum pedido.

Por exemplo, para um gráfico de dependência de classe canônica (você só pode participar da aula X se teve aula Y):

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

Você provavelmente obteria, como resultado:

100, 201, 101, 202, 200

Mas se você alterá -lo para que você sempre deseje ter classes numeradas mais baixas primeiro, poderá alterá -lo facilmente para retornar:

100, 101, 200, 201, 202