depth first search

[tuananh87vn]

I have a depth first search algorithm like below

Mark all nodes unvisited.
While nodes are unvisited, perform DFS on them.
Function DFS (node aNode)
...Visit (aNode)
...Set aNode to be visited
...For each neighbor N of aNode that is unvisited, DFS(N)

can anybody help me convert it into C source code

[Ganon11]

Which part are you having trouble with? Do you have your Graph set up, with Nodes and Edges?

[tuananh87vn]

yeah, some kind of homework. I've just done a bit:

/* assume there are n nodes in the graph */
void main() 
{
    int i;
    for (i=1;i<=n;i++)
    {
        node[i]=0;             // 0 means unvisited
    }                        // mark all nodes in the graph                             // as unvisited
    for(i=1;i<=n;i++)
    {
        while(node[i]==0)        //while a node is unvisited
        {                    //call function dfs()
            dfs(node[i]);
        }
    }
 
    getch();
}
 
void dfs(node n)                // define function dfs()
{
    node w;
    n=1;                     // 1 means visited
    for each w in adj_list(n)    // adj_list(n) shows all nodes         {                    // that are connected to n
            If(w==0)
            {
                dfs(w)        //call dsf()function recursively
            }
        }    
}

i'm quite sure the function dfs() is not correct. can u help me to correct it or, better, the entitre source code

thanks!

[MarshMallow]

yeah, some kind of homework. I've just done a bit:

/* assume there are n nodes in the graph */
void main() 
{
int i;
    for (i=1;i<=n;i++)
    {
        node[i]=0;                
    }                                                                                   
    for(i=1;i<=n;i++)  <------ HERE IS THE PROBLEM 
    {
        while(node[i]==0)        //while a node is unvisited
        {                    //call function dfs()
            dfs(node[i]);
        }
    }
    getch();
}
void dfs(node n)            // DFS functions it's correct    
{
    node w;
    n=1;                     // 1 means visited
    for each w in adj_list(n)            {
            If(w==0)
            {
                dfs(w)        //call dsf()function recursively
            }
        }    
}
 

thanks!

instead of calling the dfs functions on every node,as you do in the for loop in main function,you 'd rather choose a starting node,call dfs function just on that node and then wait for the magic of recursion to do all the work.Hope you understood,otherwise send me a PM.

[tuananh87vn]

yeah, I see the case: the for loop actually can run once only because the dfs() function inside it marks all the nodes as visited. And the problem is, the for loop makes the starting node always the first one, right? so how can I randomly choose starting node in C?

[MarshMallow]

I can't asnwer because I don't know how you stored the nodes.

[tuananh87vn]

I can't asnwer because I don't know how you stored the nodes.

Assume that nodes are store in 2-dimensional array, so how it would be?
- to choose a random starting node
- to make a list of its neighbour, and put on them a for loop

i really get stuck at this, so can you help me?