🌉 Graph Traversal – Comprehensive Study Guide

**Graph Traversal** refers to **systematically visiting** all the vertices of a graph. It is an essential concept in graph algorithms used in **networking, artificial intelligence, and shortest path problems**.

⚡ Why is Graph Traversal Important?

  • ✅ **Used in pathfinding (AI, Robotics, GPS Navigation).**
  • 🚀 **Essential for cycle detection & topological sorting.**
  • 📡 **Used in Web Crawling & Social Networks.**
  • 🔄 **Forms the foundation of advanced graph algorithms.**

📌 Types of Graph Traversal

📤 **1. Breadth-First Search (BFS) – Level Order Traversal**

Explores all neighbors before moving to deeper levels.


                void BFS(vector>& adj, int start) {
                    queue q;
                    vector visited(adj.size(), false);
                    
                    q.push(start);
                    visited[start] = true;
            
                    while (!q.empty()) {
                        int node = q.front();
                        q.pop();
                        cout << node << " ";
            
                        for (int neighbor : adj[node]) {
                            if (!visited[neighbor]) {
                                visited[neighbor] = true;
                                q.push(neighbor);
                            }
                        }
                    }
                }

📥 **2. Depth-First Search (DFS) – Recursive & Iterative**

Explores **as deep as possible** before backtracking.

🔍 **Recursive DFS**


                void DFS(vector>& adj, int node, vector& visited) {
                    visited[node] = true;
                    cout << node << " ";
                    
                    for (int neighbor : adj[node]) {
                        if (!visited[neighbor]) {
                            DFS(adj, neighbor, visited);
                        }
                    }
                }

🔄 **Iterative DFS (Using Stack)**


                void iterativeDFS(vector>& adj, int start) {
                    stack s;
                    vector visited(adj.size(), false);
                    
                    s.push(start);
                    while (!s.empty()) {
                        int node = s.top();
                        s.pop();
                        
                        if (!visited[node]) {
                            cout << node << " ";
                            visited[node] = true;
                            for (auto it = adj[node].rbegin(); it != adj[node].rend(); ++it) {
                                if (!visited[*it]) s.push(*it);
                            }
                        }
                    }
                }

🔗 Detecting Cycles in Graphs

📌 **Cycle Detection in Directed Graph (Using DFS)**


                bool detectCycleDFS(int node, vector>& adj, vector& visited, vector& recStack) {
                    visited[node] = true;
                    recStack[node] = true;
            
                    for (int neighbor : adj[node]) {
                        if (!visited[neighbor] && detectCycleDFS(neighbor, adj, visited, recStack))
                            return true;
                        else if (recStack[neighbor])
                            return true;
                    }
                    
                    recStack[node] = false;
                    return false;
                }

📜 Topological Sorting (Ordering of Nodes)

📌 **1. Topological Sorting Using DFS**

Used in **task scheduling & dependency resolution**.


                void topologicalSortDFS(int node, vector>& adj, vector& visited, stack& s) {
                    visited[node] = true;
                    for (int neighbor : adj[node])
                        if (!visited[neighbor])
                            topologicalSortDFS(neighbor, adj, visited, s);
                    s.push(node);
                }

📌 **2. Topological Sorting Using Kahn’s Algorithm (BFS)**


                void kahnTopologicalSort(vector>& adj, int V) {
                    vector inDegree(V, 0);
                    for (auto& edges : adj) for (int v : edges) inDegree[v]++;
                    
                    queue q;
                    for (int i = 0; i < V; i++) if (inDegree[i] == 0) q.push(i);
            
                    while (!q.empty()) {
                        int node = q.front(); q.pop();
                        cout << node << " ";
                        for (int neighbor : adj[node]) if (--inDegree[neighbor] == 0) q.push(neighbor);
                    }
                }

⏳ Time Complexity Analysis

Algorithm Time Complexity
BFS O(V + E)
DFS O(V + E)
Cycle Detection O(V + E)
Topological Sorting O(V + E)

🌍 Real-World Applications of Graph Traversal

  • 📡 **Google Maps & GPS Navigation** – Finding the shortest route.
  • 🕵️ **Web Crawling (Google Search Engine)** – Exploring all websites.
  • 🤖 **AI & Robotics** – Pathfinding in automated systems.
  • 🎮 **Game Development** – AI-based movement in strategy games.

🔗 Next Topics