Алгоритм обхода ориентированного графа вот так (картинка внутри)

Question

У меня есть такой график:

Одно простое правило:
Каждый узел в графе знает только о своем преемнике.

Как видите, проблема возникает, когда мы подошли к 6 (по первой ветви 1 → 6), поэтому мы не знаем, когда пришло время остановиться и начать обход другой ветви (2 → 6 ).

Может кто-нибудь предложить такой алгоритм обхода графа, пожалуйста?

Мне пришла в голову идея, когда я прохожу 1 → 6 → end of graph, а затем возвращаюсь к 2 → 6.
Но я думаю, что это не очень хорошая идея, потому что на пути 1 → 6 → end of graph может быть много вил.

Answer 1

По сути, есть только два способа пересечь график .

1. Поиск в глубину
2. Поиск в ширину

Есть много других вариантов, конечно, но они самые простые и наиболее применимые. Другие алгоритмы в большинстве случаев можно рассматривать как вариации на эти темы. Выберите тот, который лучше для вашей проблемы и отправляйтесь в город!

Answer 2

Рекурсивно, вы отмечаете каждый узел, когда пересекаете его, и когда больше нечего исследовать, вы возвращаетесь.

Нечто похожее

function 

mark the current edge
for all it's vertices
call the function on the edge that is connected with the vertice if the edge is not marked
do something with the edge (display or whatever)
once there is no vertices left return 

C пример, если граф представлен смежной матрицей, длина 1000 означает, что вершин нет.

void inDepth(int i)
{
    int j;

    edges[i] = 1; //edges is the marking vector

    for (j=0; j<N; j++)
    {
        if ((vertices[i][j]<1000) && (vertices[i][j]>0) && (edges[j]==0)) 
        {
            inDepth(j); 
        }
    }

    printf("%d ",i);
}

Answer 3

Разве это не поиск DFS?( Первый поиск в глубину )