Graph Traversal Definition

Graph traversal refers to the process of visiting all vertices in a connected graph exactly once, starting from a given vertex and following edges. This is a fundamental graph operation.

The essence of graph traversal is finding adjacent vertices for each node. Since graphs may contain cycles where vertices can be revisited, we need mechanisms to prevent redundant visits.

Solution approach: Use a visited array to track visited vertices. Initialize all elements to false (0), and mark as true (1) when visited to prevent multiple visits.

Two primary graph traversal methods exist:

• Depth-First Search (DFS)
• Breadth-First Search (BFS)

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking, similar to navigating a maze by following one path until reaching a dead end.

DFS process:

1. Start from initial vertex v, mark it visited
2. Visit an unvisited adjacent vertex w₁
3. From w₁, visit its unvisited adjacent vertex w₂
4. Continue this process until reaching a vertex with all adjacent vertices visited
5. Backtrack to the previous vertex and check for other unvisited adjacent vertices
6. Repeat until all vertices are visited

DFS Implementation with Adjacency Matrix

#include <stdio.h>
#include <stdbool.h>

#define MAX_NODES 100

int adjMatrix[MAX_NODES][MAX_NODES];
bool isVisited[MAX_NODES];
int nodeCount;

void depthFirstSearch(int currentNode) {
    isVisited[currentNode] = true;
    printf("%d ", currentNode);
    
    for (int i = 0; i < nodeCount; i++) {
        if (adjMatrix[currentNode][i] == 1 && !isVisited[i]) {
            depthFirstSearch(i);
        }
    }
}

int main() {
    printf("Enter number of vertices: ");
    scanf("%d", &nodeCount);
    
    printf("Enter adjacency matrix:\n");
    for (int i = 0; i < nodeCount; i++) {
        for (int j = 0; j < nodeCount; j++) {
            scanf("%d", &adjMatrix[i][j]);
        }
    }
    
    printf("DFS traversal: ");
    for (int i = 0; i < nodeCount; i++) {
        isVisited[i] = false;
    }
    
    for (int i = 0; i < nodeCount; i++) {
        if (!isVisited[i]) {
            depthFirstSearch(i);
        }
    }
    
    return 0;
}

DFS Implementation with Adjacency List

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

#define MAX_VERTICES 100

typedef struct GraphNode {
    int vertexIndex;
    struct GraphNode* nextNode;
} GraphNode;

typedef struct GraphStructure {
    int vertexCount;
    GraphNode* adjacencyLists[MAX_VERTICES];
} GraphStructure;

void addConnection(GraphStructure* graph, int source, int destination) {
    GraphNode* newVertex = (GraphNode*)malloc(sizeof(GraphNode));
    newVertex->vertexIndex = destination;
    newVertex->nextNode = graph->adjacencyLists[source];
    graph->adjacencyLists[source] = newVertex;
}

void dfsTraversal(GraphStructure* graph, int currentVertex, int visited[]) {
    visited[currentVertex] = 1;
    printf("%d ", currentVertex);
    
    GraphNode* currentNode = graph->adjacencyLists[currentVertex];
    while (currentNode != NULL) {
        int connectedVertex = currentNode->vertexIndex;
        if (!visited[connectedVertex]) {
            dfsTraversal(graph, connectedVertex, visited);
        }
        currentNode = currentNode->nextNode;
    }
}

void performDFS(GraphStructure* graph) {
    int visited[MAX_VERTICES] = {0};
    for (int i = 0; i < graph->vertexCount; i++) {
        if (!visited[i]) {
            dfsTraversal(graph, i, visited);
        }
    }
}

int main() {
    GraphStructure* graph = (GraphStructure*)malloc(sizeof(GraphStructure));
    graph->vertexCount = 5;
    
    for (int i = 0; i < graph->vertexCount; i++) {
        graph->adjacencyLists[i] = NULL;
    }
    
    addConnection(graph, 0, 1);
    addConnection(graph, 0, 2);
    addConnection(graph, 1, 3);
    addConnection(graph, 1, 4);
    
    printf("DFS traversal: ");
    performDFS(graph);
    
    return 0;
}

DFS Performance Analysis

Adjacency Matrix: O(n²) - Each vertex requires scanning entire row

Adjacency List: O(n + e) - Scan e edges plus n vertex headers

Conclusion: Dense graphs suit adjacency matrix DFS; sparse graphs suit adjacency list DFS.

DFS for Disconnected Graphs

For disconnected graphs, perform DFS on each connected component separately.

Breadth-First Search (BFS)

BFS explores all neighbors at the current depth before moving to the next level, similar to exploring a maze layer by layer.

BFS process:

1. Visit starting vertex v, mark visited, enqueue
2. While queue not empty:
   1. Dequeue vertex u
   2. Visit all unvisited adjacent vertices of u, mark visited, enqueue
3. Repeat until all vertices visited

BFS uses a queue data structure and doesn't involve recursion.

BFS Implementation with Adjacency Matrix

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

#define QUEUE_SIZE 100

typedef struct Queue {
    int elements[QUEUE_SIZE];
    int front, rear;
} Queue;

void initializeQueue(Queue* q) {
    q->front = q->rear = 0;
}

int isQueueEmpty(Queue* q) {
    return q->front == q->rear;
}

void enqueueElement(Queue* q, int value) {
    if ((q->rear + 1) % QUEUE_SIZE == q->front) {
        printf("Queue overflow!\n");
        exit(1);
    }
    q->elements[q->rear] = value;
    q->rear = (q->rear + 1) % QUEUE_SIZE;
}

int dequeueElement(Queue* q) {
    if (isQueueEmpty(q)) {
        printf("Queue underflow!\n");
        exit(1);
    }
    int value = q->elements[q->front];
    q->front = (q->front + 1) % QUEUE_SIZE;
    return value;
}

void breadthFirstSearch(int graph[][QUEUE_SIZE], int visited[], int startVertex, int vertexCount) {
    Queue q;
    initializeQueue(&q);
    enqueueElement(&q, startVertex);
    visited[startVertex] = 1;
    printf("%d ", startVertex);
    
    while (!isQueueEmpty(&q)) {
        int current = dequeueElement(&q);
        for (int i = 0; i < vertexCount; i++) {
            if (graph[current][i] && !visited[i]) {
                enqueueElement(&q, i);
                visited[i] = 1;
                printf("%d ", i);
            }
        }
    }
}

int main() {
    int vertices, edges;
    printf("Enter vertices and edges count: ");
    scanf("%d %d", &vertices, &edges);
    
    int graph[QUEUE_SIZE][QUEUE_SIZE] = {0};
    int visited[QUEUE_SIZE] = {0};
    
    printf("Enter edges (u v):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1;
    }
    
    printf("BFS from vertex 0: ");
    breadthFirstSearch(graph, visited, 0, vertices);
    
    return 0;
}

BFS Implementation with Adjacecny List

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

typedef struct ListNode {
    int vertex;
    struct ListNode* next;
} ListNode;

typedef struct Graph {
    int vertexCount;
    ListNode** adjacencyList;
} Graph;

ListNode* createListNode(int v) {
    ListNode* newNode = malloc(sizeof(ListNode));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addGraphEdge(Graph* graph, int src, int dest) {
    ListNode* newNode = createListNode(dest);
    newNode->next = graph->adjacencyList[src];
    graph->adjacencyList[src] = newNode;
    
    newNode = createListNode(src);
    newNode->next = graph->adjacencyList[dest];
    graph->adjacencyList[dest] = newNode;
}

Graph* initializeGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->vertexCount = vertices;
    graph->adjacencyList = malloc(vertices * sizeof(ListNode*));
    for (int i = 0; i < vertices; i++) {
        graph->adjacencyList[i] = NULL;
    }
    return graph;
}

void bfsTraversal(Graph* graph, int startVertex) {
    int visited[graph->vertexCount];
    for (int i = 0; i < graph->vertexCount; i++) {
        visited[i] = 0;
    }
    
    ListNode* queue = createListNode(startVertex);
    visited[startVertex] = 1;
    
    while (queue != NULL) {
        printf("%d ", queue->vertex);
        
        ListNode* current = graph->adjacencyList[queue->vertex];
        while (current != NULL) {
            int adjacentVertex = current->vertex;
            if (!visited[adjacentVertex]) {
                ListNode* newQueueNode = createListNode(adjacentVertex);
                newQueueNode->next = queue->next;
                queue->next = newQueueNode;
                visited[adjacentVertex] = 1;
            }
            current = current->next;
        }
        
        ListNode* removedNode = queue;
        queue = queue->next;
        free(removedNode);
    }
}

int main() {
    int vertices = 6;
    Graph* graph = initializeGraph(vertices);
    addGraphEdge(graph, 0, 1);
    addGraphEdge(graph, 0, 2);
    addGraphEdge(graph, 1, 3);
    addGraphEdge(graph, 1, 4);
    addGraphEdge(graph, 2, 4);
    addGraphEdge(graph, 3, 5);
    addGraphEdge(graph, 4, 5);
    
    printf("BFS from vertex 0: ");
    bfsTraversal(graph, 0);
    
    return 0;
}

BFS Performance Analysis

Adjacency Matrix: O(n²) - Check entire row for each visited vertex

Adjacency List: O(n + e) - Process n vertices and e edges

DFS vs BFS Efficiency Comparison

Space complexity: Both O(n) - Using stack (DFS) or queue (BFS)

Time complexity: Depends on storage structure, not traversal method