Algorithm for traversing directed graph like this (picture inside)

I have a graph like this:

One simple rule:

Every node in the graph only knows about its successor.

As you can see, the problem occurs when we came to 6 (by the first branch, 1 → 6), so that we do not know when it is time to stop and start traversing another branch (2 → 6).

Could anyone suggest an algorithm for traversing graph like this, please?

I came开发者_Python百科 up with the idea when I am traversing 1 → 6 → end of graph, and then returning to 2 → 6.

But I think this is not good idea, because there could be a lot of forks on the 1 → 6 → end of graph way.

---

Fundamentally, there are only two ways to traverse a graph.

1. Depth-first search
2. Breadth-first search

There are plenty of other options, of course, but these are the simplest and most generally applicable. The other algorithms can mostly be thought of as variations on these themes anyway. Choose whichever one is best for your problem and go to town!

---

Recursively, you mark each node when you cross it and when there is nothing left to explore you go back.

Something that will look like

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 example, if the graph is represented by a adjacent matrix, a length of 1000 means there are no vertices.

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

---

Isn't that a DFS search? (Depth First Search)