C Program for Traversing Undirected Graph through DFS and classifying edges as tree edges and back edges

By | 29.06.2017

Traversing Undirected Graph through DFS and classifying edges as tree edges and back edges


Write a C Program for Traversing Undirected Graph through DFS and classifying edges as tree edges and back edges. Here’s simple Program for Traversing Undirected Graph through DFS and classifying edges as tree edges and back edges in C Programming Language.


Depth First Search (DFS)


Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

It employs the following rules.

  • Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
  • Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
  • Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

We shall not see the implementation of Depth First Traversal (or Depth First Search) in C programming language


Also Read : : C Program for Traversing Directed Graph through DFS and classifying all edges

Below is the source code for C Program for Traversing Undirected Graph through DFS and classifying edges as tree edges and back edges in output which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program for Traversing an Undirected Graph through DFS
 and classifying edges as tree edges and back edges*/

#include<stdio.h>
#define MAX 100
#define NIL -1

#define initial 1
#define visited 2
#define finished 3

int adj[MAX][MAX];
int n;    /* Denotes number of vertices in the graph */
int state[MAX];

int predecessor[MAX];
void create_graph();
void DF_Traversal();
void DFS(int v);

int main()
{
        create_graph();
        DF_Traversal();
        return 0;
}/*End of main()*/

void DF_Traversal()
{
        int v;
        for(v=0; v<n; v++)
        {
                state[v] = initial;
                predecessor[v] = NIL;
        }
        printf("\nEnter starting vertex for Depth First Search : ");
        scanf("%d",&v);
        DFS(v);
        for(v=0; v<n; v++)
        {
                if(state[v] == initial)
                        DFS(v);
        }
}/*End of DF_Traversal()*/

void DFS(int v)
{
        int i;
        state[v] = visited;
        for(i=0; i<n; i++)
        {
                if(adj[v][i] == 1 && predecessor[v]!=i )
                {
                        if(state[i] == initial)
                        {
                                predecessor[i] = v;
                                printf("\n(%d,%d) Tree edge\n", v, i);
                                DFS(i);
                        }
                        else if(state[i] == visited)
                        {
                                printf("\n(%d,%d) Back edge\n", v, i);
                        }
                }
        }
        state[v] = finished;
}/*End of DFS()*/


void create_graph()
{
        int i,max_edges,origin,destin;

        printf("\nEnter number of vertices : ");
        scanf("%d",&n);
        max_edges=n*(n-1)/2;

        for(i=1; i<=max_edges; i++)
        {
                printf("\nEnter edge %d( -1 -1 to quit ) : ",i);
                scanf("%d %d",&origin,&destin);
                if( (origin == -1) && (destin == -1) )
                        break;
                if(origin >= n || destin >= n || origin<0 || destin<0)
                {
                        printf("\nInvalid edge!\n");
                        i--;
                }
                else
                {
                        adj[origin][destin] = 1;
                        adj[destin][origin] = 1;
                }
        }
}

OUTPUT : :


/* C Program for Traversing an Undirected Graph through DFS
 and classifying edges as tree edges and back edges*/

Enter number of vertices : 6

Enter edge 1( -1 -1 to quit ) : 0 1

Enter edge 2( -1 -1 to quit ) : 0 2

Enter edge 3( -1 -1 to quit ) : 0 3

Enter edge 4( -1 -1 to quit ) : 0 4

Enter edge 5( -1 -1 to quit ) : 3 5

Enter edge 6( -1 -1 to quit ) : 1 4

Enter edge 7( -1 -1 to quit ) : -1 -1

Enter starting vertex for Depth First Search : 0

(0,1) Tree edge

(1,4) Tree edge

(4,0) Back edge

(0,2) Tree edge

(0,3) Tree edge

(3,5) Tree edge

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post…


Recommended Posts : :

0 0 votes
Article Rating
Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments