W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Graphs

Non-linear data structure - BFS, DFS, Cycle Detection, Topological Sort.

What is a Graph?

Adjacency List: Space O(V + E), Add Edge O(1)

Networked Connections

Imagine a social network like LinkedIn or Facebook. Each user profile represents a node, and their friendships or mutual connections represent links between them. If you follow someone on Twitter, that link is directed (one-way); if you are connected on LinkedIn, that link is undirected (two-way).

In computer science, a Graph is a non-linear data structure consisting of a finite set of Vertices (Nodes) and a set of Edges (Connections) joining these vertices.

Key Terminology:

Vertex (Node): An individual data point or object in the graph.
Edge: A link or connection path joining two vertices.
Adjacent Nodes: Two vertices connected directly by a single edge.
Degree: The number of edges connected to a vertex. (In directed graphs, we track In-degree and Out-degree).
Path: A sequence of edges allowing traversal between a series of vertices.
Cycle: A path that starts and ends at the exact same vertex.

Graph Classifications:

Directed Graph (Digraph): Edges have direction arrows (e.g., website link pointing to another page).
Undirected Graph: Edges are bidirectional and have no specific directions (e.g., bilateral trade agreements).
Weighted Graph: Edges carry numerical values representing distance, cost, or time (e.g., flight routing costs).

C++ Code — What is a Graph?

#include <iostream>
#include <vector>
using namespace std;

// Graph using Adjacency List (most common)
class Graph {
public:
    int V;  // Number of vertices
    vector<vector<int>> adj;  // Adjacency list
    
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }
    
    // Add edge (undirected)
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // Remove for directed graph
    }
    
    // Print graph
    void printGraph() {
        for (int i = 0; i < V; i++) {
            cout << "Vertex " << i << " -> ";
            for (int neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    // Create a graph with 5 vertices
    Graph g(5);
    
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    
    g.printGraph();
    
    return 0;
}

Graph Representations

Matrix: O(V²) space | List: O(V + E) space

Storing Graph Topologies

Choosing how to represent a graph in memory has a massive impact on performance and storage requirements:

1. Adjacency Matrix (`O(V²)` Space)

A 2D array of size V * V where matrix[i][j] = 1 indicates the presence of an edge between vertex i and j.

Advantage: Checking if an edge exists between two nodes is instant (O(1) time).
Constraint: Consumes a lot of memory, even if the graph has very few edges (sparse).

2. Adjacency List (`O(V + E)` Space)

An array of lists or vectors where index i stores a list of all vertices adjacent to vertex i.

Advantage: Highly space-efficient for sparse graphs.
Constraint: Checking if an edge exists between u and v requires iterating through the list of u (O(V) worst-case).

3. Edge List (`O(E)` Space)

A simple array containing pairs of connected vertices. Most commonly utilized in minimum spanning tree (MST) algorithms like Kruskal's.

C++ Code — Graph Representations

#include <iostream>
#include <vector>
using namespace std;

// Method 1: Adjacency Matrix
class GraphMatrix {
public:
    int V;
    vector<vector<int>> matrix;
    
    GraphMatrix(int v) {
        V = v;
        matrix.assign(V, vector<int>(V, 0));
    }
    
    void addEdge(int u, int v) {
        matrix[u][v] = 1;
        matrix[v][u] = 1;  // For undirected
    }
    
    bool hasEdge(int u, int v) {
        return matrix[u][v] == 1;
    }
    
    void print() {
        cout << "Adjacency Matrix:" << endl;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                cout << matrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

// Method 2: Adjacency List
class GraphList {
public:
    int V;
    vector<vector<int>> adj;
    
    GraphList(int v) {
        V = v;
        adj.resize(V);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void print() {
        cout << "Adjacency List:" << endl;
        for (int i = 0; i < V; i++) {
            cout << i << " -> ";
            for (int x : adj[i]) cout << x << " ";
            cout << endl;
        }
    }
};

int main() {
    // Graph: 0-1, 0-2, 1-2, 2-3
    
    GraphMatrix gm(4);
    gm.addEdge(0, 1);
    gm.addEdge(0, 2);
    gm.addEdge(1, 2);
    gm.addEdge(2, 3);
    gm.print();
    
    cout << endl;
    
    GraphList gl(4);
    gl.addEdge(0, 1);
    gl.addEdge(0, 2);
    gl.addEdge(1, 2);
    gl.addEdge(2, 3);
    gl.print();
    
    return 0;
}

BFS - Breadth First Search

Time: O(V + E) | Space: O(V)

Interactive

Loading Visualizer...

Level-by-Level Graph Traversal

Imagine dropping a pebble into a still pond. Ripples expand outward in concentric circles, hitting every point at distance 1, then distance 2, then distance 3.

Breadth-First Search (BFS) is a graph traversal algorithm that explores vertices level-by-level, starting from a source node and visiting all its immediate neighbors before going deeper.

Mechanics:

Queue-Based: Relies on a Queue (FIFO) to track which nodes to explore next.
Visited Array: Employs a boolean array to ensure no node is processed twice, avoiding infinite loops in cyclic graphs.

Important Features:

Shortest Path: BFS is guaranteed to find the shortest path (minimum number of edges) between two nodes in an unweighted graph.
Applications: Finding peer connections, peer-to-peer torrent sharing, web crawlers.

C++ Code — BFS - Breadth First Search

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;
    
    Graph(int v) : V(v) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // BFS from source vertex
    void BFS(int source) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[source] = true;
        q.push(source);
        
        cout << "BFS starting from " << source << ": ";
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            cout << curr << " ";
            
            // Visit all unvisited neighbors
            for (int neighbor : adj[curr]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
    
    // BFS to find shortest path
    void shortestPath(int source, int dest) {
        vector<int> dist(V, -1);
        vector<int> parent(V, -1);
        queue<int> q;
        
        dist[source] = 0;
        q.push(source);
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            
            for (int neighbor : adj[curr]) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[curr] + 1;
                    parent[neighbor] = curr;
                    q.push(neighbor);
                }
            }
        }
        
        if (dist[dest] == -1) {
            cout << "No path exists" << endl;
            return;
        }
        
        cout << "Shortest distance: " << dist[dest] << endl;
        
        // Print path
        vector<int> path;
        for (int v = dest; v != -1; v = parent[v]) {
            path.push_back(v);
        }
        
        cout << "Path: ";
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << path[i];
            if (i > 0) cout << " -> ";
        }
        cout << endl;
    }
};

int main() {
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 5);
    
    g.BFS(0);  // 0 1 2 3 4 5
    g.shortestPath(0, 5);  // Distance: 4, Path: 0 -> 1 -> 3 -> 4 -> 5
    
    return 0;
}

DFS - Depth First Search

Time: O(V + E) | Space: O(V)

Interactive

Loading Visualizer...

Backtracking Exploration

Imagine navigating a dark maze. You choose a path and walk as deep as possible until you hit a dead end. When blocked, you backtrack to the last intersection and try a different route.

Depth-First Search (DFS) is a traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking.

Mechanics:

Stack-Based: Can be implemented recursively (using the system call stack) or iteratively (using an explicit Stack container).
Exploration Style: Goes deep along a single path, unlike the level-by-level ripple style of BFS.

Important Features:

Path Finding: Excellent for finding if a path exists between two nodes, solving maze puzzles, and finding cycles.
Applications: Topological sorting, finding strongly connected components, maze generators.

C++ Code — DFS - Depth First Search

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;
    
    Graph(int v) : V(v) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // DFS using Recursion
    void DFSRecursive(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                DFSRecursive(neighbor, visited);
            }
        }
    }
    
    void DFS(int source) {
        vector<bool> visited(V, false);
        cout << "DFS (Recursive) from " << source << ": ";
        DFSRecursive(source, visited);
        cout << endl;
    }
    
    // DFS using Stack (Iterative)
    void DFSIterative(int source) {
        vector<bool> visited(V, false);
        stack<int> s;
        
        s.push(source);
        cout << "DFS (Iterative) from " << source << ": ";
        
        while (!s.empty()) {
            int curr = s.top();
            s.pop();
            
            if (!visited[curr]) {
                visited[curr] = true;
                cout << curr << " ";
                
                // Push neighbors (in reverse for same order as recursive)
                for (int i = adj[curr].size() - 1; i >= 0; i--) {
                    if (!visited[adj[curr][i]]) {
                        s.push(adj[curr][i]);
                    }
                }
            }
        }
        cout << endl;
    }
    
    // Check if path exists using DFS
    bool hasPath(int source, int dest) {
        vector<bool> visited(V, false);
        return hasPathHelper(source, dest, visited);
    }
    
    bool hasPathHelper(int curr, int dest, vector<bool>& visited) {
        if (curr == dest) return true;
        
        visited[curr] = true;
        
        for (int neighbor : adj[curr]) {
            if (!visited[neighbor]) {
                if (hasPathHelper(neighbor, dest, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
};

int main() {
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    
    g.DFS(0);
    g.DFSIterative(0);
    
    cout << "Path 0 to 5: " << (g.hasPath(0, 5) ? "Yes" : "No") << endl;  // Yes
    
    return 0;
}

Cycle Detection

Time: O(V + E) | Space: O(V)

Identifying Feedback Loops

A Cycle is a path that starts and ends at the same vertex. Detecting cycles is a critical safety check in many real-world systems, such as preventing circular compiler dependencies or thread deadlocks.

1. Cycle Detection in Undirected Graphs (`O(V + E)` Time)

We run DFS starting from a node. If we encounter an already visited vertex that is not the immediate parent of the current node, a cycle must exist.

2. Cycle Detection in Directed Graphs (`O(V + E)` Time)

In directed graphs, visiting a visited node does not guarantee a cycle. Instead, we must track the current recursion path (using an active path state array like inStack).

If we visit a node that is already active in our current recursion stack, we have detected a back edge (cycle).

Real-world Systems:

Build Systems: Preventing circular compile tasks (e.g., A needs B, B needs A).
Operating Systems: Resolving deadlocks where resource requirements cycle.

C++ Code — Cycle Detection

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;
    
    Graph(int v) : V(v) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v, bool directed = false) {
        adj[u].push_back(v);
        if (!directed) adj[v].push_back(u);
    }
    
    // Cycle detection in UNDIRECTED graph
    bool hasCycleUndirected(int v, int parent, vector<bool>& visited) {
        visited[v] = true;
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                if (hasCycleUndirected(neighbor, v, visited)) {
                    return true;
                }
            }
            else if (neighbor != parent) {
                // Visited vertex that's not parent = cycle
                return true;
            }
        }
        return false;
    }
    
    bool detectCycleUndirected() {
        vector<bool> visited(V, false);
        
        // Check all components
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (hasCycleUndirected(i, -1, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // Cycle detection in DIRECTED graph
    bool hasCycleDirected(int v, vector<bool>& visited, vector<bool>& inStack) {
        visited[v] = true;
        inStack[v] = true;  // In current recursion path
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                if (hasCycleDirected(neighbor, visited, inStack)) {
                    return true;
                }
            }
            else if (inStack[neighbor]) {
                // Already in current path = cycle
                return true;
            }
        }
        
        inStack[v] = false;  // Remove from current path
        return false;
    }
    
    bool detectCycleDirected() {
        vector<bool> visited(V, false);
        vector<bool> inStack(V, false);
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (hasCycleDirected(i, visited, inStack)) {
                    return true;
                }
            }
        }
        return false;
    }
};

int main() {
    // Undirected graph with cycle
    Graph g1(4);
    g1.addEdge(0, 1);
    g1.addEdge(1, 2);
    g1.addEdge(2, 0);  // Creates cycle
    g1.addEdge(2, 3);
    cout << "Undirected cycle: " << (g1.detectCycleUndirected() ? "Yes" : "No") << endl;  // Yes
    
    // Directed graph with cycle
    Graph g2(4);
    g2.addEdge(0, 1, true);
    g2.addEdge(1, 2, true);
    g2.addEdge(2, 0, true);  // Creates cycle
    g2.addEdge(2, 3, true);
    cout << "Directed cycle: " << (g2.detectCycleDirected() ? "Yes" : "No") << endl;  // Yes
    
    return 0;
}

Topological Sort

Time: O(V + E) | Space: O(V)

Interactive

Loading Visualizer...

Linear Ordering of Dependencies

Imagine getting dressed in the morning. You must put on your socks before your shoes, and your shirt before your jacket. Similarly, in a compiler, you must compile libraries before compiling applications that depend on them.

Topological Sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u appears before v in the order.

Constraints:

Only works on a DAG (Directed Acyclic Graph). If a graph contains cycles, topological ordering is mathematically impossible.

Algorithms:

Kahn's Algorithm (BFS-Based):
- Find the in-degree (incoming edge count) of all vertices.
- Enqueue all nodes with an in-degree of 0.
- Dequeue a node, add it to the topological order, and decrement the in-degree of its neighbors. If a neighbor's in-degree drops to 0, enqueue it.
DFS-Based Approach:
- Run DFS and push a node to a stack only after fully exploring all its descendants. Pop from the stack to reveal the sorted order.

C++ Code — Topological Sort

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;
    
    Graph(int v) : V(v) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);  // Directed edge
    }
    
    // Method 1: DFS based Topological Sort
    void topoDFS(int v, vector<bool>& visited, stack<int>& st) {
        visited[v] = true;
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                topoDFS(neighbor, visited, st);
            }
        }
        
        st.push(v);  // Add after all neighbors processed
    }
    
    void topologicalSortDFS() {
        vector<bool> visited(V, false);
        stack<int> st;
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topoDFS(i, visited, st);
            }
        }
        
        cout << "Topological Order (DFS): ";
        while (!st.empty()) {
            cout << st.top() << " ";
            st.pop();
        }
        cout << endl;
    }
    
    // Method 2: BFS based (Kahn's Algorithm)
    void topologicalSortBFS() {
        vector<int> inDegree(V, 0);
        
        // Calculate in-degree for each vertex
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj[i]) {
                inDegree[neighbor]++;
            }
        }
        
        queue<int> q;
        
        // Add vertices with 0 in-degree
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> result;
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            result.push_back(curr);
            
            for (int neighbor : adj[curr]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        if (result.size() != V) {
            cout << "Cycle detected! Topological sort not possible." << endl;
            return;
        }
        
        cout << "Topological Order (BFS): ";
        for (int v : result) {
            cout << v << " ";
        }
        cout << endl;
    }
};

int main() {
    // Course prerequisites example:
    // 5 -> 0, 5 -> 2, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1
    Graph g(6);
    g.addEdge(5, 0);
    g.addEdge(5, 2);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
    
    g.topologicalSortDFS();  // 5 4 2 3 1 0 (one possible order)
    g.topologicalSortBFS();  // 4 5 2 0 3 1 (one possible order)
    
    return 0;
}

#include <iostream> #include <vector> using namespace std; // Graph using Adjacency List (most common) class Graph { public: int V; // Number of vertices vector<vector<int>> adj; // Adjacency list Graph(int vertices) { V = vertices; adj.resize(V); } // Add edge (undirected) void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // Remove for directed graph } // Print graph void printGraph() { for (int i = 0; i < V; i++) { cout << "Vertex " << i << " -> "; for (int neighbor : adj[i]) { cout << neighbor << " "; } cout << endl; } } }; int main() { // Create a graph with 5 vertices Graph g(5); g.addEdge(0, 1); g.addEdge(0, 4); g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 3); g.addEdge(3, 4); g.printGraph(); return 0; }

#include <iostream> #include <vector> using namespace std; // Method 1: Adjacency Matrix class GraphMatrix { public: int V; vector<vector<int>> matrix; GraphMatrix(int v) { V = v; matrix.assign(V, vector<int>(V, 0)); } void addEdge(int u, int v) { matrix[u][v] = 1; matrix[v][u] = 1; // For undirected } bool hasEdge(int u, int v) { return matrix[u][v] == 1; } void print() { cout << "Adjacency Matrix:" << endl; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { cout << matrix[i][j] << " "; } cout << endl; } } }; // Method 2: Adjacency List class GraphList { public: int V; vector<vector<int>> adj; GraphList(int v) { V = v; adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } void print() { cout << "Adjacency List:" << endl; for (int i = 0; i < V; i++) { cout << i << " -> "; for (int x : adj[i]) cout << x << " "; cout << endl; } } }; int main() { // Graph: 0-1, 0-2, 1-2, 2-3 GraphMatrix gm(4); gm.addEdge(0, 1); gm.addEdge(0, 2); gm.addEdge(1, 2); gm.addEdge(2, 3); gm.print(); cout << endl; GraphList gl(4); gl.addEdge(0, 1); gl.addEdge(0, 2); gl.addEdge(1, 2); gl.addEdge(2, 3); gl.print(); return 0; }

#include <iostream> #include <vector> #include <queue> using namespace std; class Graph { public: int V; vector<vector<int>> adj; Graph(int v) : V(v) { adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // BFS from source vertex void BFS(int source) { vector<bool> visited(V, false); queue<int> q; visited[source] = true; q.push(source); cout << "BFS starting from " << source << ": "; while (!q.empty()) { int curr = q.front(); q.pop(); cout << curr << " "; // Visit all unvisited neighbors for (int neighbor : adj[curr]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } cout << endl; } // BFS to find shortest path void shortestPath(int source, int dest) { vector<int> dist(V, -1); vector<int> parent(V, -1); queue<int> q; dist[source] = 0; q.push(source); while (!q.empty()) { int curr = q.front(); q.pop(); for (int neighbor : adj[curr]) { if (dist[neighbor] == -1) { dist[neighbor] = dist[curr] + 1; parent[neighbor] = curr; q.push(neighbor); } } } if (dist[dest] == -1) { cout << "No path exists" << endl; return; } cout << "Shortest distance: " << dist[dest] << endl; // Print path vector<int> path; for (int v = dest; v != -1; v = parent[v]) { path.push_back(v); } cout << "Path: "; for (int i = path.size() - 1; i >= 0; i--) { cout << path[i]; if (i > 0) cout << " -> "; } cout << endl; } }; int main() { Graph g(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 3); g.addEdge(3, 4); g.addEdge(4, 5); g.BFS(0); // 0 1 2 3 4 5 g.shortestPath(0, 5); // Distance: 4, Path: 0 -> 1 -> 3 -> 4 -> 5 return 0; }

#include <iostream> #include <vector> #include <stack> using namespace std; class Graph { public: int V; vector<vector<int>> adj; Graph(int v) : V(v) { adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // DFS using Recursion void DFSRecursive(int v, vector<bool>& visited) { visited[v] = true; cout << v << " "; for (int neighbor : adj[v]) { if (!visited[neighbor]) { DFSRecursive(neighbor, visited); } } } void DFS(int source) { vector<bool> visited(V, false); cout << "DFS (Recursive) from " << source << ": "; DFSRecursive(source, visited); cout << endl; } // DFS using Stack (Iterative) void DFSIterative(int source) { vector<bool> visited(V, false); stack<int> s; s.push(source); cout << "DFS (Iterative) from " << source << ": "; while (!s.empty()) { int curr = s.top(); s.pop(); if (!visited[curr]) { visited[curr] = true; cout << curr << " "; // Push neighbors (in reverse for same order as recursive) for (int i = adj[curr].size() - 1; i >= 0; i--) { if (!visited[adj[curr][i]]) { s.push(adj[curr][i]); } } } } cout << endl; } // Check if path exists using DFS bool hasPath(int source, int dest) { vector<bool> visited(V, false); return hasPathHelper(source, dest, visited); } bool hasPathHelper(int curr, int dest, vector<bool>& visited) { if (curr == dest) return true; visited[curr] = true; for (int neighbor : adj[curr]) { if (!visited[neighbor]) { if (hasPathHelper(neighbor, dest, visited)) { return true; } } } return false; } }; int main() { Graph g(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(3, 5); g.DFS(0); g.DFSIterative(0); cout << "Path 0 to 5: " << (g.hasPath(0, 5) ? "Yes" : "No") << endl; // Yes return 0; }

#include <iostream> #include <vector> using namespace std; class Graph { public: int V; vector<vector<int>> adj; Graph(int v) : V(v) { adj.resize(V); } void addEdge(int u, int v, bool directed = false) { adj[u].push_back(v); if (!directed) adj[v].push_back(u); } // Cycle detection in UNDIRECTED graph bool hasCycleUndirected(int v, int parent, vector<bool>& visited) { visited[v] = true; for (int neighbor : adj[v]) { if (!visited[neighbor]) { if (hasCycleUndirected(neighbor, v, visited)) { return true; } } else if (neighbor != parent) { // Visited vertex that's not parent = cycle return true; } } return false; } bool detectCycleUndirected() { vector<bool> visited(V, false); // Check all components for (int i = 0; i < V; i++) { if (!visited[i]) { if (hasCycleUndirected(i, -1, visited)) { return true; } } } return false; } // Cycle detection in DIRECTED graph bool hasCycleDirected(int v, vector<bool>& visited, vector<bool>& inStack) { visited[v] = true; inStack[v] = true; // In current recursion path for (int neighbor : adj[v]) { if (!visited[neighbor]) { if (hasCycleDirected(neighbor, visited, inStack)) { return true; } } else if (inStack[neighbor]) { // Already in current path = cycle return true; } } inStack[v] = false; // Remove from current path return false; } bool detectCycleDirected() { vector<bool> visited(V, false); vector<bool> inStack(V, false); for (int i = 0; i < V; i++) { if (!visited[i]) { if (hasCycleDirected(i, visited, inStack)) { return true; } } } return false; } }; int main() { // Undirected graph with cycle Graph g1(4); g1.addEdge(0, 1); g1.addEdge(1, 2); g1.addEdge(2, 0); // Creates cycle g1.addEdge(2, 3); cout << "Undirected cycle: " << (g1.detectCycleUndirected() ? "Yes" : "No") << endl; // Yes // Directed graph with cycle Graph g2(4); g2.addEdge(0, 1, true); g2.addEdge(1, 2, true); g2.addEdge(2, 0, true); // Creates cycle g2.addEdge(2, 3, true); cout << "Directed cycle: " << (g2.detectCycleDirected() ? "Yes" : "No") << endl; // Yes return 0; }

#include <iostream> #include <vector> #include <stack> #include <queue> using namespace std; class Graph { public: int V; vector<vector<int>> adj; Graph(int v) : V(v) { adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); // Directed edge } // Method 1: DFS based Topological Sort void topoDFS(int v, vector<bool>& visited, stack<int>& st) { visited[v] = true; for (int neighbor : adj[v]) { if (!visited[neighbor]) { topoDFS(neighbor, visited, st); } } st.push(v); // Add after all neighbors processed } void topologicalSortDFS() { vector<bool> visited(V, false); stack<int> st; for (int i = 0; i < V; i++) { if (!visited[i]) { topoDFS(i, visited, st); } } cout << "Topological Order (DFS): "; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } // Method 2: BFS based (Kahn's Algorithm) void topologicalSortBFS() { vector<int> inDegree(V, 0); // Calculate in-degree for each vertex for (int i = 0; i < V; i++) { for (int neighbor : adj[i]) { inDegree[neighbor]++; } } queue<int> q; // Add vertices with 0 in-degree for (int i = 0; i < V; i++) { if (inDegree[i] == 0) { q.push(i); } } vector<int> result; while (!q.empty()) { int curr = q.front(); q.pop(); result.push_back(curr); for (int neighbor : adj[curr]) { inDegree[neighbor]--; if (inDegree[neighbor] == 0) { q.push(neighbor); } } } if (result.size() != V) { cout << "Cycle detected! Topological sort not possible." << endl; return; } cout << "Topological Order (BFS): "; for (int v : result) { cout << v << " "; } cout << endl; } }; int main() { // Course prerequisites example: // 5 -> 0, 5 -> 2, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1 Graph g(6); g.addEdge(5, 0); g.addEdge(5, 2); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); g.topologicalSortDFS(); // 5 4 2 3 1 0 (one possible order) g.topologicalSortBFS(); // 4 5 2 0 3 1 (one possible order) return 0; }

Graphs

What is a Graph?

Networked Connections

Key Terminology:

Graph Classifications:

Graph Representations

Storing Graph Topologies

1. Adjacency Matrix (O(V²) Space)

2. Adjacency List (O(V + E) Space)

3. Edge List (O(E) Space)

BFS - Breadth First Search

Level-by-Level Graph Traversal

Mechanics:

Important Features:

DFS - Depth First Search

Backtracking Exploration

Mechanics:

Important Features:

Cycle Detection

Identifying Feedback Loops

1. Cycle Detection in Undirected Graphs (O(V + E) Time)

2. Cycle Detection in Directed Graphs (O(V + E) Time)

Real-world Systems:

Topological Sort

Linear Ordering of Dependencies

Constraints:

Algorithms:

Graphs

What is a Graph?

Networked Connections

Key Terminology:

Graph Classifications:

Graph Representations

Storing Graph Topologies

1. Adjacency Matrix (O(V²) Space)

2. Adjacency List (O(V + E) Space)

3. Edge List (O(E) Space)

BFS - Breadth First Search

Level-by-Level Graph Traversal

Mechanics:

Important Features:

DFS - Depth First Search

Backtracking Exploration

Mechanics:

Important Features:

Cycle Detection

Identifying Feedback Loops

1. Cycle Detection in Undirected Graphs (O(V + E) Time)

2. Cycle Detection in Directed Graphs (O(V + E) Time)

Real-world Systems:

Topological Sort

Linear Ordering of Dependencies

Constraints:

Algorithms:

1. Adjacency Matrix (`O(V²)` Space)

2. Adjacency List (`O(V + E)` Space)

3. Edge List (`O(E)` Space)

1. Cycle Detection in Undirected Graphs (`O(V + E)` Time)

2. Cycle Detection in Directed Graphs (`O(V + E)` Time)

1. Adjacency Matrix (`O(V²)` Space)

2. Adjacency List (`O(V + E)` Space)

3. Edge List (`O(E)` Space)

1. Cycle Detection in Undirected Graphs (`O(V + E)` Time)

2. Cycle Detection in Directed Graphs (`O(V + E)` Time)