Detailed Explanation of Graph DFS and BFS

1. Basic Definitions of Graphs

A graph is a collection of vertices and edges. Graphs can be classified as undirected graphs or directed graphs, and further subdivided into weighted graphs and unweighted graphs depending on whether edges carry weights.

2. Depth-First Search (DFS)

Definition

Depth-First Search (DFS) is a graph traversal method that starts from an initial vertex and explores as deeply as possible along each branch before backtracking to the previous vertex to continue exploring unvisited branches, until all vertices have been visited.

Steps

1. Start from the initial vertex and mark it as visited.
2. Recursively visit all unvisited adjacent vertices.
3. Backtrack to the previous vertex and continue visiting unvisited adjacent vertices.

Code Implementation (C)

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int visited[MAX]; // Visited marker array

// Graph adjacency matrix representation
typedef struct Graph {
    int vertices;
    int adjMatrix[MAX][MAX];
} Graph;

// Initialize graph
void initGraph(Graph* g, int vertices) {
    g->vertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// Add edge
void addEdge(Graph* g, int src, int dest) {
    g->adjMatrix[src][dest] = 1;
    g->adjMatrix[dest][src] = 1; // Undirected graph
}

// Depth-first traversal
void DFS(Graph* g, int vertex) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    for (int i = 0; i < g->vertices; i++) {
        if (g->adjMatrix[vertex][i] == 1 && !visited[i]) {
            DFS(g, i);
        }
    }
}

int main() {
    Graph g;
    initGraph(&g, 6);

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    addEdge(&g, 2, 5);

    for (int i = 0; i < 6; i++) {
        visited[i] = 0;
    }

    printf("Depth First Search starting from vertex 0:\n");
    DFS(&g, 0);

    return 0;
}

3. Breadth-First Search (BFS)

Definition

Breadth-First Search (BFS) is a graph traversal method that starts from an initial vertex, first visits all adjacent vertices of that vertex, and then sequentially visits the adjacent vertices of those vertices, until all vertices have been visited.

Steps

1. Start from the initial vertex, mark it as visited, and add it to the queue.
2. Dequeue a vertex, visit all its unvisited adjacent vertices, and enqueue those adjacent vertices.
3. Repeat step 2 until the queue is empty.

Code Implementation (C)

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int visited[MAX]; // Visited marker array

// Graph adjacency matrix representation
typedef struct Graph {
    int vertices;
    int adjMatrix[MAX][MAX];
} Graph;

// Queue structure definition
typedef struct Queue {
    int items[MAX];
    int front, rear;
} Queue;

// Initialize queue
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// Check if queue is empty
int isEmpty(Queue* q) {
    return q->rear == -1;
}

// Enqueue
void enqueue(Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue is full\n");
    } else {
        if (q->front == -1) q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// Dequeue
int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        return item;
    }
}

// Initialize graph
void initGraph(Graph* g, int vertices) {
    g->vertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// Add edge
void addEdge(Graph* g, int src, int dest) {
    g->adjMatrix[src][dest] = 1;
    g->adjMatrix[dest][src] = 1; // Undirected graph
}

// Breadth-first traversal
void BFS(Graph* g, int startVertex) {
    Queue* q = createQueue();
    visited[startVertex] = 1;
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);

        for (int i = 0; i < g->vertices; i++) {
            if (g->adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
}

int main() {
    Graph g;
    initGraph(&g, 6);

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    addEdge(&g, 2, 5);

    for (int i = 0; i < 6; i++) {
        visited[i] = 0;
    }

    printf("Breadth First Search starting from vertex 0:\n");
    BFS(&g, 0);

    return 0;
}

4. Time and Space Complexity Analysis

Depth-First Search (DFS)

• Time Complexity: $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. Each vertex and each edge is visited exactly once.
• Space Complexity: $O(V)$, primarily used for the recursive call stack and storing visit markers.

Breadth-First Search (BFS)

• Time Complexity: $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. Each vertex and each edge is visited exactly once.
• Space Complexity: $O(V)$, primarily used for the queue and storing visit markers.