Umesh Chandra

A graph is a non-linear data structure, which is represented by vertices(nodes) and edges. Every pair of vertices is connected with one edge between them.

In simple words, traversal means the process of visiting every node in the graph. There are 2 standard methods of graph traversal Breadth-First Search and Depth First Search

Breadth First Search

Breadth-First Search (BFS) is a graph traversal algorithm, where we start from a selected(source) node and traverse the graph level by level, by exploring the neighbor nodes at each level.

Depth First Search

Depth First Search (DFS) is a graph traversal algorithm, where we start from a selected(source) node and go into the depth of this node by recursively calling the DFS function until no children are encountered. When the dead-end is reached, this algorithm backtracks and starts visiting the other children of the current node.

Implementation of BFS and DFS:

#include<stdio.h>
#include<stdlib.h>
struct Node
{
    int data;
    struct Node *next;
}*front = NULL, *rear = NULL;

void enqueue(int x)
{
    struct Node *t;
    t = (struct Node*)malloc(sizeof(struct Node));
    if(t == NULL)
    {
        printf("Queue is full");
    }
    else
    {
        t->data = x;
        t->next = NULL;
        if(front == NULL)
        {
            front = rear = t;
        }
        else
        {
            rear->next = t;
            rear = t;
            rear->next = NULL;
        }
    }
}

int dequeue()
{
    int x=-1;
    struct Node *p;
    if(front == NULL)
    {
        printf("Queue is Empty");
    }
    else
    {
        p = front;
        front = front->next;
        x = p->data;
        free(p);
    }
    return x;
}

int isEmpty()
{
    return front == NULL;
}

void BFS(int G[][7], int start, int n)
{
    int i=start;
    int visited[n];
    for(int a=0; a<n; a++)
    {
        visited[a] = 0;
    }
    printf("%d ", i);
    visited[i] = 1;
    enqueue(i);
    while(!isEmpty())
    {
        i = dequeue();
        for(int j=1; j<n; j++)
        {
            if(G[i][j] == 1 && visited[j] == 0)
            {
                printf("%d ", j);
                visited[j] = 1;
                enqueue(j);
            }
        }
    }
    
}

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

int main()
{
    int G[7][7] = {{0,0,0,0,0,0,0},
                   {0,0,1,1,0,0,0},
                   {0,1,0,0,1,0,0},
                   {0,1,0,0,1,0,0},
                   {0,0,1,1,0,1,1},
                   {0,0,0,0,1,0,0},
                   {0,0,0,0,1,0,0}};
    int n = sizeof(G)/sizeof(G[0]);
    BFS(G, 4, n);
    printf("\n");
    DFS(G, 4, n);
}