DFS & BFS

#include <stdio.h>
#define max 10

int G[max][max],visited[max],n;
int rear,front;
int queue[max];

void insert(int x)
{
    rear++;
    queue[rear]=x;
}

int delete()
{
    int x;
    x=queue[front];
    if(front==rear+1)
    {
        rear=-1;
        front=-1;
    }
    else
        front++;
    return x;
}

void DFS(int i)
{
    int j;
    printf("%d ",i);
    visited[i]=1;
    for(j=0;j<n;j++)
    {
        if(!visited[j]&&G[i][j]==1)
            DFS(j);
    }
}

void BFS(int v)
{
    int i;
    rear=-1;
    front=-1;
    insert(v);
    printf("%d ",v);
    visited[v]=1;
    while(rear!=-1)
    {
        v=delete();
        for(i=0;i<n;i++)
        {
            if(visited[i]==0&&G[v][i]!=0)
            {
                insert(i);
                visited[i]=1;
                printf("%d ",i);
            }
        }
    }
}

int main()
{
    int i,j,x,y;
    printf("Enter no. of vertices ");
    scanf("%d",&n);
    printf("Enter adjecency matrix of graph\n");
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&G[i][j]);
    do
    {
        for(i=0;i<n;i++)
            visited[i]=0;
        printf("\nEnter\n1.DFS\n2.BFS\n3.Exit\n");
        scanf("%d",&y);
        switch(y)
        {
            case 1:
                printf("Enter the starting vertex ");
                scanf("%d",&x);
                DFS(x);
                printf("\n");
                break;
            case 2:
                printf("Enter the starting vertex ");
                scanf("%d",&x);
                BFS(x);
                printf("\n");
                break;
        }
    }while(y!=3);
    return 0;
}

/*Output
Enter no. of vertices 8
Enter adjecency matrix of graph
0 1 1 1 1 0 0 0
1 0 0 0 0 1 0 0
1 0 0 0 0 1 0 0
1 0 0 0 0 0 1 0
1 0 0 0 0 0 1 0
0 1 1 0 0 0 0 1
0 0 0 1 1 0 0 1
0 0 0 0 0 1 1 0

Enter
1.DFS
2.BFS
3.Exit
1
Enter the starting vertex 0
0 1 5 2 7 6 3 4

Enter
1.DFS
2.BFS
3.Exit
2
Enter the starting vertex 0
0 1 2 3 4 5 6 7

Enter
1.DFS
2.BFS
3.Exit
3
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s