Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 5 M

Year: Dec 2014

C function:

void dfs_traversal(int adj[][MAX], int visited[], int start)
{
    int stack[MAX];
    int top = -1, i;
    printf("%d", start);
    visited[start] = 1;
    stack[++top] = start;
    while (top != -1)
    {
        start = stack[top];
        for (i = 0;i < MAX;i++)
        {
            if (adj[start][i] && visited[i] == 0)
            {
                stack[++top] = i;
                printf("%d", i);
                visited[i] = 1;
                break;
            }
        }
        if (i == MAX)
            top--;
    }
}

Explanation:

• The input to the above function is the adjacency matrix which is entered by the user and the visited matrix which is initialized to zero to indicate that all vertices are unvisited.
• When a node is visited, the value becomes 1.
• The start value specifies the node number form where to start e.g. 0 means to start traversal from 0th node.
• It then considers one of the unvisited vertices adjacent to it and marks it visited, then repeats the process by considering one of it unvisited adjacent vertices.
• Let us understand by an example:

• Adjacency matrix is :
• First we consider node 0.
• We mark it visited and we put it to the stack top
• Inside the while loop, check if the adjacency matrix value is 1 and the node is not visited.
• If not move it to the stack top.
• Print the node on screen and mark it as visited.
• Continue the loop until the stack is empty.
• The Output for the above will be : 0 , 2, 4