DFS Search

//Here we have used the Adjacnet Matrix method hence time complexity for the DFS is O(V^2)
//Since whole matrix of V^2 has to be searched for the adjacnet nodes
//If Adjacent list would have been used in that case complexiy would have been 0(V+E) since only only V vertices had been passed and E edges would have searched for
//Not an optimal solution...
//But saves lots of space
//if A[u][v]=1 it implies that there exist a path from u to v hence v is adjacent to u

DFS:A>B>D>F>C>G>E

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int V;//Number of vertices

int E;//number of Edges..not used since adjacent matrix  representation has been used

int A[10][10];//Adjacent matrix

int visited[10]={0,0,0,0,0,0,0,0,0,0};//visited array...initially all are set to zero since no node has been visited

void dfs(int u)
{
        visited[u]=1;//whatever node is passed to node is consider to be visited hence we make it visited
        printf("%c\t",(65+u));//printing the node visited..and nodes are in character form A,B,C..
        int i;
        for( i=0;i<V;i++)
        if(!visited[i]&&A[u][i])//if node is not visited and it is adjacent to the node passed as argument to the function then only we will visit it..the first adjacent node will be visited and the remaing adjacent node will be visited recursively
        {    
        dfs(i);
        }
}

main()
       {
           
             puts("Enter the number of Vertices and Graph");
             scanf("%d",&(V));
             scanf("%d",&(E));
           
           
             int i;
             int j;
             puts("Enter the Adjacent Matrix Row wise");
             for(i=0;i<V;i++)
             {
                for(j=0;j<V;j++)
                scanf("%d",&(A[i][j]));
             }                                
              i=0,j=0;        
              puts("Adjacent Matrix");        
             for(i=0;i<V;i++)
             {
                                 
                for(j=0;j<V;j++)
                printf("%d\t",(A[i][j]));
                printf("\n");
                   
             }
         
             dfs(0);//Here since graph is single componet we can take only one vertex and start dfs else in separate component then we have to do dfs for all the nodes

 getch();          
}