Depth First Search

Lets see DFS(Depth First Search) traversal of an undirected graph using a non recursive function.

What is DFS ?

It is a graph traversal in which you start from the source vertex.(2 here)

If you have an adjacent vertex not visited previously you visit it.

If you have no adjacent vertices/you have visited the adjacent vertices previously then you backtrack.

Follow same procedure until all vertices are visited.

Blue    ---> current vertex

Yellow ---> visited vertices

Algorithm

Let source vertex be current vertex.

a. Visit adjacent unvisited vertex of current vertex.Mark it visited,print it,push it 
   in stack and make it as current vertex.

b. If no adjacent vertex exists/all adjacent vertices are visited pop a vertex from stack 
   and backtrack.The vertex to which you backtrack is now the current vertex.

c. Repeat 1 and 2 till stack is empty.

Code

See how to implement stack using array

void read_graph()
{
    int i,j;

    printf("Enter the no of vertices in the graph ");
    scanf("%d",&g.n);

    printf("\nEnter adjacency matrix\n");

    for(i=1;i<=g.n;i++)
    {
        for(j=1;j<=g.n;j++)
            scanf("%d",&g.adj_mat[i][j]);

        vis[i] = 0;
    }
}

void dfs(int source)
{
    int curr,i = 1;

    vis[source] = 1;
    push(source);
    printf("%d ",source);

    while(!empty())
    {
        curr = top();

        while(i<=g.n)
        {
            if(vis[i]==0 && g.adj_mat[curr][i]==1)
            {
                curr = i;

                vis[curr] = 1;
                push(curr);
                printf("%d ",curr);

                i = 1;

                continue;
            }

            i++;
        }

        i = pop();
        i++;
    }
}

Code Tracing

Complete Code