Geek asks and answers

Algorithm for moving a directed graph like this (image inside)

I have a chart like this:

graph

One simple rule:
Each node on the chart only knows about its successor.

As you can see, the problem arises when we come to 6(on the first branch, 1 → 6), so we don’t know when it is time to stop and start traversing another branch ( 2 → 6).

Can someone suggest an algorithm for moving this graph, please?

I came up with the idea when I cross 1 → 6 → end of graphand then return to 2 → 6.
But I think this is not a good idea, because there 1 → 6 → end of graphcan be many forks on the way .

+3
source share
3 answers

, .

, , . , . , , !

+2

DFS? ( )

0

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

Something that will look

function 

mark the current edge
for all it 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 For example, if a graph is represented by an adjacent matrix, a length of 1000 means that 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);
}
0
source

More articles:


All Articles