Published: December 6, 2024 | Reading Time: 6 minutes
Graph traversal refers to the process of visiting all the nodes in a graph systematically. Traversing a graph is crucial in many real-world applications, as it enables efficient searching, data retrieval, and graph-based decision-making. Two of the most commonly used techniques for graph traversal are Breadth-First Search (BFS) and Depth-First Search (DFS). These algorithms are fundamental to various applications. In this article, we will explore graph traversal types, applications, advantages, and examples.
Graph traversal is the process of visiting all the vertices of a graph in a specific order. The primary goal of graph traversal is to explore all the nodes and edges in a graph, which helps in tasks such as finding the shortest path, detecting cycles, or searching for specific information.
There are two primary types of graph traversal techniques:
BFS is a graph traversal technique that explores all the neighboring nodes at the present depth level before moving on to nodes at the next depth level. It starts from a given node, visits all its adjacent nodes, and continues this process level by level. BFS is particularly useful for finding the shortest path in an unweighted graph.
| Complexity Type | Value |
|---|---|
| Time Complexity | O(V + E) |
| Space Complexity | O(V) |
Where V represents vertices and E represents edges in the graph.
This is a basic algorithm used to explore graph structures. It starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
| Complexity Type | Value |
|---|---|
| Time Complexity | O(V + E) |
| Space Complexity | O(V) |
Where V represents vertices and E represents edges in the graph.
Here are the advantages of graph traversal:
Here are the disadvantages of graph traversal:
Here are some of the applications of how graph traversal is used in real-world scenarios:
Here are the example programs of BFS and DFS in C programming:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Structure for the graph
struct Graph {
int V;
int **adjMatrix;
};
// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->adjMatrix = (int**)malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
graph->adjMatrix[i] = (int*)malloc(V * sizeof(int));
for (int j = 0; j < V; j++) {
graph->adjMatrix[i][j] = 0; // Initialize all edges as 0 (no edges)
}
}
return graph;
}
// Function to add an edge to the graph (undirected graph)
void addEdge(struct Graph* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1;
}
// Function to perform BFS traversal
void BFS(struct Graph* graph, int start) {
bool* visited = (bool*)malloc(graph->V * sizeof(bool));
for (int i = 0; i < graph->V; i++) {
visited[i] = false;
}
int* queue = (int*)malloc(graph->V * sizeof(int));
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start;
while (front != rear) {
int node = queue[front++];
printf("%d ", node);
for (int i = 0; i < graph->V; i++) {
if (graph->adjMatrix[node][i] == 1 && !visited[i]) {
visited[i] = true;
queue[rear++] = i;
}
}
}
free(visited);
free(queue);
}
int main() {
struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 5);
printf("BFS starting from vertex 0:\n");
BFS(graph, 0);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Structure for the graph
struct Graph {
int V;
int **adjMatrix;
};
// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->adjMatrix = (int**)malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
graph->adjMatrix[i] = (int*)malloc(V * sizeof(int));
for (int j = 0; j < V; j++) {
graph->adjMatrix[i][j] = 0; // Initialize all edges as 0 (no edges)
}
}
return graph;
}
// Function to add an edge to the graph (undirected graph)
void addEdge(struct Graph* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1;
}
// Recursive function to perform DFS traversal
void DFS(struct Graph* graph, int node, bool* visited) {
visited[node] = true;
printf("%d ", node);
for (int i = 0; i < graph->V; i++) {
if (graph->adjMatrix[node][i] == 1 && !visited[i]) {
DFS(graph, i, visited);
}
}
}
int main() {
struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 5);
bool* visited = (bool*)malloc(graph->V * sizeof(bool));
for (int i = 0; i < graph->V; i++) {
visited[i] = false;
}
printf("DFS starting from vertex 0:\n");
DFS(graph, 0, visited);
free(visited);
return 0;
}
In conclusion, graph traversal is a crucial operation in data structures. Both BFS and DFS are fundamental algorithms used for searching, exploring, and analyzing graphs. So, BFS is ideal for finding the shortest path and DFS is used for deeper nodes and solving problems. Understanding these traversal techniques and their complexities can help in optimizing graph-based operations and solving a wide range of computational problems.
BFS explores the graph level by level, ensuring the shortest path in an unweighted graph, while DFS explores as far down a branch as possible before backtracking, which can be more memory efficient but doesn't guarantee the shortest path.
In binary trees, BFS is also known as level-order traversal which visits all the nodes at the present level before moving on to the next level, which is useful for tasks like printing the tree level by level.
Both BFS and DFS explore all nodes and edges of a graph. BFS explores level by level, while DFS explores deeper paths before backtracking, with each having unique use cases based on the problems.
Source: NxtWave - CCBP Blog
Original URL: https://www.ccbp.in/blog/articles/graph-traversal-in-data-structures