Photo by Chris Abney on Unsplash
Navigating the Graph Jungle: A Journey Through Graph Traversal Algorithms
In the vast realm of computer science, where data structures and algorithms reign supreme, one topic that often stands out is graph theory. Graphs are versatile data structures that represent a wide array of real-world relationships and systems, from social networks to transportation networks, from the World Wide Web to recommendation engines. They are the backbone of modern computing, enabling us to model and understand complex systems.
But what good is a graph if you can't explore it effectively? This is where graph traversal comes into play. Imagine you are embarking on a journey through an intricate labyrinth, and your goal is to navigate from one point to another, making informed decisions at every crossroads. Graph traversal algorithms provide you with the tools to do just that in the digital world.
In this exploration, we will dive deep into the fascinating world of graph traversal. We will learn how to systematically traverse a graph, uncover its hidden secrets, and solve problems that range from finding the shortest path between two points to understanding the structure of networks. We will embark on this journey using two fundamental techniques: Depth-First Search (DFS) and Breadth-First Search (BFS).
So, fasten your seatbelts, as we embark on a quest to unravel the mysteries of graphs and their traversal. Whether you're a budding computer scientist, a seasoned developer, or simply someone curious about the inner workings of the digital world, join us on this adventure, and let's traverse the Graph Jungle together!
Graph Traversal Algorithm
Generally, there are two types of Graph Traversal techniques that we commonly use on a day-to-day basis:
Depth First Search (DFS)
Depth First Search as the name suggests the graph traversal algorithm will traverse the depth of the graph and explore as far as possible along each branch before backtracking. This means that it starts at the root node and explores as far as possible along each branch before backtracking.
DFS can be implemented using recursion or by using a stack data structure. When implemented recursively, it uses the call stack to keep track of the nodes to be visited.
The algorithm works as follows:
Start at the initial or root node of the graph.
Mark the current node as visited.
Explore each unvisited neighbor of the current node recursively by calling the DFS function on it.
Repeat step 3 for all unvisited neighbors.
Backtrack when there are no more unvisited neighbors from the current node.
Continue the process until all nodes have been visited.
So you may ask how we got to know about these two things :
Visited Node: For this, we will take a visited array of the size of N (total nodes in Graph) initialized with all zeros, which indicates that none of the nodes is visited till now.
neighbors of the Current Node: To know about the neighbors of the current node we have an adjacency list that stores the connected nodes to the given node.
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency list
vector<bool> visited; // Visited array
vector<vector<int>> adjNodes; // Adjacent nodes for each vertex
public:
Graph(int vertices) : V(vertices), adj(vertices), visited(vertices, false), adjNodes(vertices) {}
void addEdge(int v, int w) {
adj[v].push_back(w); //because it is a undirected graph
adjNodes[v].push_back(w);
}
void DFS(int node) {
visited[node] = true;
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
DFS(neighbor);
}
}
}
void DFSTraversal(int startVertex) {
DFS(startVertex);
}
void printAdjNodes() {
for (int i = 0; i < V; i++) {
cout << "Adjacent nodes for vertex " << i << ": ";
for (int neighbor : adjNodes[i]) {
cout << neighbor << " ";
}
cout << endl;
}
}
};
int main() {
Graph g(7); // Create a graph with 7 vertices
// Add edges to the graph
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
cout << "Depth First Traversal (starting from vertex 0): ";
g.DFSTraversal(0);
cout << endl;
g.printAdjNodes();
return 0;
}
Depth First Traversal (starting from vertex 0): 0 1 3 4 2 5 6
Adjacent nodes for vertex 0: 1 2
Adjacent nodes for vertex 1: 3 4
Adjacent nodes for vertex 2: 5 6
Adjacent nodes for vertex 3:
Adjacent nodes for vertex 4:
Adjacent nodes for vertex 5:
Adjacent nodes for vertex 6:
Breadth First Search (BFS)
- BFS is a graph traversal algorithm used to explore all the neighbors of a node before moving on to their neighbors. It systematically explores nodes level by level, starting from the root node. It is often used to find the shortest path between two nodes in an unweighted graph. BFS is implemented using a queue data structure.
The algorithm works as follows:
Start at the initial or root node of the graph.
Mark the root node as visited to avoid revisiting it.
Create a queue data structure to store nodes to be visited next.
Enqueue (insert) the root node into the queue.
While the queue is not empty:
a. Dequeue (remove and retrieve) the front element from the queue. This represents the current node you are exploring.
b. Process the current node (e.g., print or perform some operation).
c. Traverse all unvisited neighbors of the current node:
Mark each neighbor as visited to avoid revisiting it.
Enqueue (insert) each unvisited neighbor into the queue to explore them later.
Repeat steps 5 until the queue is empty. This ensures that you explore nodes at the current level before moving to the next level.
The traversal is complete when all nodes have been visited.
I know it might be confusing and to get you the depth of the BFS I want you to visit this website to visualize the algorithm correctly.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency list
public:
Graph(int vertices) : V(vertices), adj(vertices) {}
// Function to add an edge to the graph
void addEdge(int v, int w) {
adj[v].push_back(w);
}
// Function to perform BFS
void BFS(int start) {
vector<bool> visited(V, false); // Initialize all nodes as not visited
queue<int> q; // Create a queue for BFS
visited[start] = true; // Mark the start node as visited
q.push(start); // Enqueue the start node
while (!q.empty()) {
int current = q.front(); // Get the front element of the queue
cout << current << " "; // Print the current node
q.pop(); // Dequeue the current node
// Visit all adjacent nodes of the current node
for (int neighbor : adj[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true; // Mark the neighbor as visited
q.push(neighbor); // Enqueue the neighbor
}
}
}
}
};
int main() {
// Create a graph with 7 vertices
Graph g(7);
// Add edges to the graph
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
cout << "Breadth-First Traversal (starting from vertex 0): ";
g.BFS(0);
return 0;
}
Breadth-First Traversal (starting from vertex 0): 0 1 2 3 4 5 6
Use of BFS and DFS in real-world
Breadth-First Search (BFS):
Shortest Path and Minimum Spanning Tree: BFS can be used to find the shortest path between two nodes in an unweighted graph. It can also be applied to find the minimum spanning tree of a graph.
Web Crawling: Search engines like Google use BFS to crawl web pages by starting from a seed URL and exploring all linked pages at the same depth level before moving deeper.
Social Network Analysis: BFS can be used to find the shortest path between users in a social network or to explore the connectivity of users within a certain distance.
Maze Solving: BFS can find the shortest path to solve mazes or puzzles where each cell represents a state, and transitions between cells represent moves.
Network Broadcasting: BFS is used in computer networks to broadcast messages to all connected devices within a certain number of hops.
Depth-First Search (DFS):
Topological Sorting: DFS can be used to perform topological sorting of a directed acyclic graph (DAG). This is crucial in scheduling tasks with dependencies.
Pathfinding: In mazes and puzzles, DFS can be used to explore all possible paths exhaustively. It's also useful in finding paths in weighted graphs, where it can be adapted to depth-first search variants like Dijkstra's algorithm or A* search.
Detecting Cycles: DFS can be used to detect cycles in a graph. It's a fundamental component in checking for the presence of cycles in a graph, which is essential in various applications, including compiler optimization and deadlock detection.
Game AI: DFS is often used in game AI to explore possible game states, especially in games with complex decision trees or game boards.
Solving Puzzles: DFS can be applied to solve puzzles like the Eight-Puzzle, Sudoku, and more, by searching for valid configurations.
I hope you learned something new from this blog, and if you are enjoying the graph series, please consider sharing it with your friends and college group. Learning about graph algorithms opens doors to solving complex problems in computer science and beyond.
Don't hesitate to explore more topics in the world of computer science and technology. Keep the curiosity alive, and keep sharing knowledge with those around you.
Thank you for being a part of this learning journey. Stay tuned for more exciting content in the future!