Graph Data Structures: Algorithms & Applications

1. Graph Representations

Adjacency Matrix

Definition

Adjacency Matrix represents a graph as a 2D array where matrix[i][j] = weight of edge from vertex i to vertex j (or 1 if unweighted). It's optimal for dense graphs where V² is manageable.

How It Works

1

Initialize matrix

Create V×V matrix filled with 0 or ∞
Set diagonal to 0 for self-loops

2

Add edges

For directed: matrix[u][v] = weight
For undirected: matrix[u][v] = matrix[v][u] = weight

3

Query edges

Check matrix[u][v] for direct edge
O(1) time complexity

class GraphMatrix:
    def __init__(self, vertices, directed=False):
        self.V = vertices
        self.directed = directed
        # Initialize matrix with 0 (no edge)
        self.matrix = [[0] * vertices for _ in range(vertices)]
    
    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        if not self.directed:
            self.matrix[v][u] = weight
    
    def remove_edge(self, u, v):
        self.matrix[u][v] = 0
        if not self.directed:
            self.matrix[v][u] = 0
    
    def has_edge(self, u, v):
        return self.matrix[u][v] != 0
    
    def get_neighbors(self, u):
        neighbors = []
        for v in range(self.V):
            if self.matrix[u][v] != 0:
                neighbors.append(v)
        return neighbors
    
    def display(self):
        print("Adjacency Matrix:")
        for row in self.matrix:
            print(row)

# Example
g = GraphMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.display()

class GraphMatrix {
    constructor(vertices, directed = false) {
        this.V = vertices;
        this.directed = directed;
        this.matrix = Array(vertices).fill().map(() => Array(vertices).fill(0));
    }
    
    addEdge(u, v, weight = 1) {
        this.matrix[u][v] = weight;
        if (!this.directed) {
            this.matrix[v][u] = weight;
        }
    }
    
    removeEdge(u, v) {
        this.matrix[u][v] = 0;
        if (!this.directed) {
            this.matrix[v][u] = 0;
        }
    }
    
    hasEdge(u, v) {
        return this.matrix[u][v] !== 0;
    }
    
    getNeighbors(u) {
        const neighbors = [];
        for (let v = 0; v < this.V; v++) {
            if (this.matrix[u][v] !== 0) {
                neighbors.push(v);
            }
        }
        return neighbors;
    }
    
    display() {
        console.log("Adjacency Matrix:");
        for (const row of this.matrix) {
            console.log(row);
        }
    }
}

import java.util.*;

class GraphMatrix {
    private int[][] matrix;
    private int V;
    private boolean directed;
    
    public GraphMatrix(int vertices, boolean directed) {
        this.V = vertices;
        this.directed = directed;
        this.matrix = new int[vertices][vertices];
    }
    
    public void addEdge(int u, int v, int weight) {
        matrix[u][v] = weight;
        if (!directed) matrix[v][u] = weight;
    }
    
    public void addEdge(int u, int v) {
        addEdge(u, v, 1);
    }
    
    public boolean hasEdge(int u, int v) {
        return matrix[u][v] != 0;
    }
    
    public List<Integer> getNeighbors(int u) {
        List<Integer> neighbors = new ArrayList<>();
        for (int v = 0; v < V; v++) {
            if (matrix[u][v] != 0) neighbors.add(v);
        }
        return neighbors;
    }
}

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

class GraphMatrix {
private:
    vector<vector<int>> matrix;
    int V;
    bool directed;
    
public:
    GraphMatrix(int vertices, bool dir = false) : V(vertices), directed(dir) {
        matrix.assign(vertices, vector<int>(vertices, 0));
    }
    
    void addEdge(int u, int v, int weight = 1) {
        matrix[u][v] = weight;
        if (!directed) matrix[v][u] = weight;
    }
    
    bool hasEdge(int u, int v) {
        return matrix[u][v] != 0;
    }
    
    vector<int> getNeighbors(int u) {
        vector<int> neighbors;
        for (int v = 0; v < V; v++) {
            if (matrix[u][v] != 0) neighbors.push_back(v);
        }
        return neighbors;
    }
};

Adjacency List

class GraphList:
    def __init__(self, directed=False):
        self.adj_list = {}
        self.directed = directed
    
    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []
    
    def add_edge(self, u, v, weight=1):
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj_list[u].append((v, weight))
        if not self.directed:
            self.adj_list[v].append((u, weight))
    
    def remove_edge(self, u, v):
        if u in self.adj_list:
            self.adj_list[u] = [(node, w) for node, w in self.adj_list[u] if node != v]
        if not self.directed and v in self.adj_list:
            self.adj_list[v] = [(node, w) for node, w in self.adj_list[v] if node != u]
    
    def get_neighbors(self, u):
        return self.adj_list.get(u, [])
    
    def display(self):
        print("Adjacency List:")
        for vertex, edges in self.adj_list.items():
            print(f"{vertex}: {edges}")

# Example
g = GraphList()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.display()

class GraphList {
    constructor(directed = false) {
        this.adjList = new Map();
        this.directed = directed;
    }
    
    addVertex(vertex) {
        if (!this.adjList.has(vertex)) {
            this.adjList.set(vertex, []);
        }
    }
    
    addEdge(u, v, weight = 1) {
        this.addVertex(u);
        this.addVertex(v);
        this.adjList.get(u).push({node: v, weight});
        if (!this.directed) {
            this.adjList.get(v).push({node: u, weight});
        }
    }
    
    getNeighbors(vertex) {
        return this.adjList.get(vertex) || [];
    }
    
    display() {
        console.log("Adjacency List:");
        for (const [vertex, edges] of this.adjList) {
            console.log(`${vertex}: ${JSON.stringify(edges)}`);
        }
    }
}

import java.util.*;

class GraphList {
    private Map<Integer, List<Edge>> adjList;
    private boolean directed;
    
    static class Edge {
        int node, weight;
        Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
    
    public GraphList(boolean directed) {
        this.adjList = new HashMap<>();
        this.directed = directed;
    }
    
    public void addVertex(int v) {
        adjList.putIfAbsent(v, new ArrayList<>());
    }
    
    public void addEdge(int u, int v, int weight) {
        addVertex(u);
        addVertex(v);
        adjList.get(u).add(new Edge(v, weight));
        if (!directed) adjList.get(v).add(new Edge(u, weight));
    }
    
    public List<Edge> getNeighbors(int v) {
        return adjList.getOrDefault(v, new ArrayList<>());
    }
}

#include <unordered_map>
#include <vector>
#include <utility>
using namespace std;

class GraphList {
private:
    unordered_map<int, vector<pair<int, int>>> adjList;
    bool directed;
    
public:
    GraphList(bool dir = false) : directed(dir) {}
    
    void addVertex(int v) {
        if (adjList.find(v) == adjList.end()) {
            adjList[v] = {};
        }
    }
    
    void addEdge(int u, int v, int weight = 1) {
        addVertex(u);
        addVertex(v);
        adjList[u].push_back({v, weight});
        if (!directed) adjList[v].push_back({u, weight});
    }
    
    vector<pair<int, int>> getNeighbors(int v) {
        return adjList[v];
    }
};

2. Breadth-First Search (BFS)

BFS Traversal

Definition

Breadth-First Search (BFS) traverses graph level by level, exploring all neighbors of a vertex before moving to the next level. It uses a queue and guarantees shortest path in unweighted graphs.

How It Works

1

Initialize queue

Push start node to queue
Mark start node as visited

2

Process level by level

Dequeue front node
Process the node
Add all unvisited neighbors to queue

3

Repeat until queue empty

Continues until all reachable nodes visited
Finds shortest path in unweighted graphs

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    traversal = []
    
    while queue:
        node = queue.popleft()
        traversal.append(node)
        
        for neighbor in graph.get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return traversal

def shortest_path(graph, start, end):
    visited = set()
    queue = deque([(start, [start])])
    visited.add(start)
    
    while queue:
        node, path = queue.popleft()
        
        if node == end:
            return path
        
        for neighbor in graph.get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None

# Example
graph = GraphList()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)

print("BFS:", bfs(graph, 0))
print("Shortest path 0->3:", shortest_path(graph, 0, 3))

function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    visited.add(start);
    const traversal = [];
    
    while (queue.length > 0) {
        const node = queue.shift();
        traversal.push(node);
        
        for (const {node: neighbor} of graph.getNeighbors(node)) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    
    return traversal;
}

function shortestPath(graph, start, end) {
    const visited = new Set();
    const queue = [{node: start, path: [start]}];
    visited.add(start);
    
    while (queue.length > 0) {
        const {node, path} = queue.shift();
        
        if (node === end) return path;
        
        for (const {node: neighbor} of graph.getNeighbors(node)) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push({node: neighbor, path: [...path, neighbor]});
            }
        }
    }
    
    return null;
}

import java.util.*;

public class BFS {
    public static List<Integer> bfs(GraphList graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> traversal = new ArrayList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            traversal.add(node);
            
            for (GraphList.Edge edge : graph.getNeighbors(node)) {
                if (!visited.contains(edge.node)) {
                    visited.add(edge.node);
                    queue.offer(edge.node);
                }
            }
        }
        return traversal;
    }
}

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

vector<int> bfs(GraphList& graph, int start) {
    unordered_set<int> visited;
    queue<int> q;
    vector<int> traversal;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        traversal.push_back(node);
        
        for (auto [neighbor, weight] : graph.getNeighbors(node)) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
    
    return traversal;
}

Complexity: O(V + E) time, O(V) space
Use When: Shortest path (unweighted), level-order traversal

3. Depth-First Search (DFS)

DFS Traversal

Definition

Depth-First Search (DFS) explores as far as possible along each branch before backtracking. It uses a stack (implicit recursion) and is useful for topological sort, cycle detection, and connectivity.

How It Works

1

Recursive approach

Mark current node as visited
Process the node
Recursively visit each unvisited neighbor

2

Backtrack when done

When no more neighbors, return to previous node
Continue with remaining neighbors

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph.get_neighbors(start):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    traversal = []
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal.append(node)
            
            # Add neighbors in reverse order for original order
            neighbors = graph.get_neighbors(node)
            for neighbor in reversed(neighbors):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal

# Connected components using DFS
def connected_components(graph):
    visited = set()
    components = []
    
    for vertex in graph.get_all_vertices():
        if vertex not in visited:
            component = []
            stack = [vertex]
            
            while stack:
                node = stack.pop()
                if node not in visited:
                    visited.add(node)
                    component.append(node)
                    for neighbor in graph.get_neighbors(node):
                        if neighbor not in visited:
                            stack.append(neighbor)
            components.append(component)
    
    return components

function dfsRecursive(graph, start, visited = new Set()) {
    visited.add(start);
    console.log(start);
    
    for (const {node: neighbor} of graph.getNeighbors(start)) {
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
    
    return visited;
}

function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    const traversal = [];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (!visited.has(node)) {
            visited.add(node);
            traversal.push(node);
            
            const neighbors = graph.getNeighbors(node);
            for (let i = neighbors.length - 1; i >= 0; i--) {
                const neighbor = neighbors[i].node;
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
    
    return traversal;
}

import java.util.*;

public class DFS {
    public static void dfsRecursive(GraphList graph, int start, Set<Integer> visited) {
        visited.add(start);
        System.out.print(start + " ");
        
        for (GraphList.Edge edge : graph.getNeighbors(start)) {
            if (!visited.contains(edge.node)) {
                dfsRecursive(graph, edge.node, visited);
            }
        }
    }
    
    public static List<Integer> dfsIterative(GraphList graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        List<Integer> traversal = new ArrayList<>();
        
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int node = stack.pop();
            
            if (!visited.contains(node)) {
                visited.add(node);
                traversal.add(node);
                
                for (GraphList.Edge edge : graph.getNeighbors(node)) {
                    if (!visited.contains(edge.node)) {
                        stack.push(edge.node);
                    }
                }
            }
        }
        
        return traversal;
    }
}

#include <stack>
#include <unordered_set>
using namespace std;

void dfsRecursive(GraphList& graph, int start, unordered_set<int>& visited) {
    visited.insert(start);
    cout << start << " ";
    
    for (auto [neighbor, weight] : graph.getNeighbors(start)) {
        if (visited.find(neighbor) == visited.end()) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

vector<int> dfsIterative(GraphList& graph, int start) {
    unordered_set<int> visited;
    stack<int> st;
    vector<int> traversal;
    
    st.push(start);
    
    while (!st.empty()) {
        int node = st.top();
        st.pop();
        
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            traversal.push_back(node);
            
            for (auto [neighbor, weight] : graph.getNeighbors(node)) {
                if (visited.find(neighbor) == visited.end()) {
                    st.push(neighbor);
                }
            }
        }
    }
    
    return traversal;
}

4. Dijkstra's Shortest Path

Dijkstra's Algorithm

Definition

Dijkstra's Algorithm finds shortest paths from source to all vertices in weighted graphs with non-negative edges. It uses a priority queue to greedily select the closest unvisited vertex.

How It Works

1

Initialize distances

Set distance to source = 0, others = ∞
Add all vertices to priority queue

2

Extract minimum

Get vertex with smallest distance from queue
If distance is larger than known, skip

3

Relax edges

For each neighbor, calculate new distance
If smaller than known, update and re-add to queue

import heapq

def dijkstra(graph, start):
    distances = {v: float('inf') for v in graph.get_all_vertices()}
    distances[start] = 0
    pq = [(0, start)]
    predecessors = {v: None for v in graph.get_all_vertices()}
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        if current_dist > distances[u]:
            continue
        
        for v, weight in graph.get_neighbors(u):
            distance = current_dist + weight
            if distance < distances[v]:
                distances[v] = distance
                predecessors[v] = u
                heapq.heappush(pq, (distance, v))
    
    return distances, predecessors

def reconstruct_path(predecessors, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = predecessors[current]
    return path[::-1]

# Example usage
g = GraphList()
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 8)

distances, pred = dijkstra(g, 'A')
print(f"Distances: {distances}")
print(f"Path to D: {reconstruct_path(pred, 'D')}")

class PriorityQueue {
    constructor() {
        this.heap = [];
    }
    
    enqueue(node, priority) {
        this.heap.push({node, priority});
        this.bubbleUp(this.heap.length - 1);
    }
    
    dequeue() {
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return min;
    }
    
    isEmpty() {
        return this.heap.length === 0;
    }
    
    bubbleUp(index) {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (this.heap[parent].priority <= this.heap[index].priority) break;
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
            index = parent;
        }
    }
    
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let smallest = index;
        
        if (left < this.heap.length && this.heap[left].priority < this.heap[smallest].priority)
            smallest = left;
        if (right < this.heap.length && this.heap[right].priority < this.heap[smallest].priority)
            smallest = right;
        
        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            this.sinkDown(smallest);
        }
    }
}

function dijkstra(graph, start) {
    const distances = {};
    const predecessors = {};
    
    for (const vertex of graph.getVertices()) {
        distances[vertex] = Infinity;
        predecessors[vertex] = null;
    }
    distances[start] = 0;
    
    const pq = new PriorityQueue();
    pq.enqueue(start, 0);
    
    while (!pq.isEmpty()) {
        const {node: u, priority: currentDist} = pq.dequeue();
        
        if (currentDist > distances[u]) continue;
        
        for (const {node: v, weight} of graph.getNeighbors(u)) {
            const distance = currentDist + weight;
            if (distance < distances[v]) {
                distances[v] = distance;
                predecessors[v] = u;
                pq.enqueue(v, distance);
            }
        }
    }
    
    return {distances, predecessors};
}

import java.util.*;

public class Dijkstra {
    static class Node implements Comparable<Node> {
        int id, distance;
        Node(int id, int distance) {
            this.id = id;
            this.distance = distance;
        }
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }
    
    public static int[] dijkstra(GraphList graph, int start, int n) {
        int[] dist = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dist[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.id;
            int currentDist = current.distance;
            
            if (currentDist > dist[u]) continue;
            
            for (GraphList.Edge edge : graph.getNeighbors(u)) {
                int v = edge.node;
                int newDist = currentDist + edge.weight;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.offer(new Node(v, newDist));
                }
            }
        }
        return dist;
    }
}

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

vector<int> dijkstra(GraphList& graph, int start, int n) {
    vector<int> dist(n, INT_MAX);
    vector<int> prev(n, -1);
    dist[start] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();
        
        if (currentDist > dist[u]) continue;
        
        for (auto [v, weight] : graph.getNeighbors(u)) {
            int newDist = currentDist + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                prev[v] = u;
                pq.push({newDist, v});
            }
        }
    }
    
    return dist;
}

5. Topological Sort

Topological Sort (DFS-based)

Definition

Topological Sort orders vertices in a Directed Acyclic Graph (DAG) such that for every edge u→v, u appears before v. It's used for task scheduling and dependency resolution.

How It Works

1

DFS on each unvisited node

Perform DFS traversal
Add node to stack after processing all neighbors

2

Post-order processing

Push to stack when leaving node
Ensures dependencies come first

def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        
        for neighbor, _ in graph.get_neighbors(node):
            if neighbor not in visited:
                dfs(neighbor)
        
        stack.append(node)  # Post-order
    
    for vertex in graph.get_all_vertices():
        if vertex not in visited:
            dfs(vertex)
    
    return stack[::-1]  # Reverse for topological order

# Kahn's Algorithm (BFS-based topological sort)
from collections import deque

def topological_sort_kahn(graph):
    in_degree = {v: 0 for v in graph.get_all_vertices()}
    
    for u in graph.get_all_vertices():
        for v, _ in graph.get_neighbors(u):
            in_degree[v] += 1
    
    queue = deque([v for v in in_degree if in_degree[v] == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        for v, _ in graph.get_neighbors(u):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    if len(result) != len(in_degree):
        raise ValueError("Graph has a cycle")
    
    return result

# Example: Course prerequisites
courses = GraphList(directed=True)
courses.add_edge('C1', 'C2')
courses.add_edge('C1', 'C3')
courses.add_edge('C2', 'C4')
courses.add_edge('C3', 'C4')

print("Topological order:", topological_sort(courses))

function topologicalSort(graph) {
    const visited = new Set();
    const stack = [];
    
    function dfs(node) {
        visited.add(node);
        
        for (const {node: neighbor} of graph.getNeighbors(node)) {
            if (!visited.has(neighbor)) {
                dfs(neighbor);
            }
        }
        
        stack.push(node);
    }
    
    for (const vertex of graph.getVertices()) {
        if (!visited.has(vertex)) {
            dfs(vertex);
        }
    }
    
    return stack.reverse();
}

function topologicalSortKahn(graph) {
    const inDegree = new Map();
    
    for (const vertex of graph.getVertices()) {
        inDegree.set(vertex, 0);
    }
    
    for (const u of graph.getVertices()) {
        for (const {node: v} of graph.getNeighbors(u)) {
            inDegree.set(v, inDegree.get(v) + 1);
        }
    }
    
    const queue = [];
    for (const [v, degree] of inDegree) {
        if (degree === 0) queue.push(v);
    }
    
    const result = [];
    while (queue.length > 0) {
        const u = queue.shift();
        result.push(u);
        
        for (const {node: v} of graph.getNeighbors(u)) {
            inDegree.set(v, inDegree.get(v) - 1);
            if (inDegree.get(v) === 0) {
                queue.push(v);
            }
        }
    }
    
    return result;
}

import java.util.*;

public class TopologicalSort {
    public static List<Integer> sort(GraphList graph) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        
        for (int vertex : graph.getVertices()) {
            if (!visited.contains(vertex)) {
                dfs(vertex, graph, visited, stack);
            }
        }
        
        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }
    
    private static void dfs(int node, GraphList graph, 
                            Set<Integer> visited, Stack<Integer> stack) {
        visited.add(node);
        
        for (GraphList.Edge edge : graph.getNeighbors(node)) {
            if (!visited.contains(edge.node)) {
                dfs(edge.node, graph, visited, stack);
            }
        }
        
        stack.push(node);
    }
}

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

vector<int> topologicalSort(GraphList& graph) {
    unordered_set<int> visited;
    stack<int> st;
    
    function<void(int)> dfs = [&](int node) {
        visited.insert(node);
        
        for (auto [neighbor, weight] : graph.getNeighbors(node)) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(neighbor);
            }
        }
        
        st.push(node);
    };
    
    for (int vertex : graph.getVertices()) {
        if (visited.find(vertex) == visited.end()) {
            dfs(vertex);
        }
    }
    
    vector<int> result;
    while (!st.empty()) {
        result.push_back(st.top());
        st.pop();
    }
    return result;
}

6. Cycle Detection

Detect Cycle in Directed Graph

Definition

Cycle Detection identifies cycles in directed graphs using DFS with recursion stack tracking. For undirected graphs, tracking parent nodes suffices.

def has_cycle_directed(graph):
    visited = set()
    rec_stack = set()
    
    def dfs(node):
        if node in rec_stack:
            return True
        if node in visited:
            return False
        
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor, _ in graph.get_neighbors(node):
            if dfs(neighbor):
                return True
        
        rec_stack.remove(node)
        return False
    
    for vertex in graph.get_all_vertices():
        if dfs(vertex):
            return True
    return False

def has_cycle_undirected(graph):
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        
        for neighbor, _ in graph.get_neighbors(node):
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
    
    for vertex in graph.get_all_vertices():
        if vertex not in visited:
            if dfs(vertex, -1):
                return True
    return False

# Example with cycle
graph_cycle = GraphList(directed=True)
graph_cycle.add_edge(0, 1)
graph_cycle.add_edge(1, 2)
graph_cycle.add_edge(2, 0)  # Creates cycle

print("Has cycle:", has_cycle_directed(graph_cycle))  # True

function hasCycleDirected(graph) {
    const visited = new Set();
    const recStack = new Set();
    
    function dfs(node) {
        if (recStack.has(node)) return true;
        if (visited.has(node)) return false;
        
        visited.add(node);
        recStack.add(node);
        
        for (const {node: neighbor} of graph.getNeighbors(node)) {
            if (dfs(neighbor)) return true;
        }
        
        recStack.delete(node);
        return false;
    }
    
    for (const vertex of graph.getVertices()) {
        if (dfs(vertex)) return true;
    }
    return false;
}

public class CycleDetection {
    public static boolean hasCycleDirected(GraphList graph) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();
        
        for (int vertex : graph.getVertices()) {
            if (dfsDirected(vertex, graph, visited, recStack)) {
                return true;
            }
        }
        return false;
    }
    
    private static boolean dfsDirected(int node, GraphList graph,
                                       Set<Integer> visited, 
                                       Set<Integer> recStack) {
        if (recStack.contains(node)) return true;
        if (visited.contains(node)) return false;
        
        visited.add(node);
        recStack.add(node);
        
        for (GraphList.Edge edge : graph.getNeighbors(node)) {
            if (dfsDirected(edge.node, graph, visited, recStack)) {
                return true;
            }
        }
        
        recStack.remove(node);
        return false;
    }
}

bool hasCycleDirected(GraphList& graph) {
    unordered_set<int> visited;
    unordered_set<int> recStack;
    
    function<bool(int)> dfs = [&](int node) -> bool {
        if (recStack.count(node)) return true;
        if (visited.count(node)) return false;
        
        visited.insert(node);
        recStack.insert(node);
        
        for (auto [neighbor, weight] : graph.getNeighbors(node)) {
            if (dfs(neighbor)) return true;
        }
        
        recStack.erase(node);
        return false;
    };
    
    for (int vertex : graph.getVertices()) {
        if (dfs(vertex)) return true;
    }
    return false;
}

Problem Type	Algorithm	Time Complexity
Shortest Path (Unweighted)	BFS	O(V + E)
Shortest Path (Weighted, no negative)	Dijkstra	O(E + V log V)
Negative Weights / Cycle Detection	Bellman-Ford	O(VE)
All Pairs Shortest Path	Floyd-Warshall	O(V³)
Minimum Spanning Tree	Prim / Kruskal	O(E log V)
Topological Sort (DAG)	DFS / Kahn's	O(V + E)
Connected Components	BFS / DFS	O(V + E)
Cycle Detection	DFS with recStack / Union-Find	O(V + E)

7. Real-World Applications

Social Network Friend Suggestions

BFS on social graph: Find friends of friends

def friend_suggestions(social_graph, user, max_depth=2):
    visited = {user}
    queue = deque([(user, 0)])
    suggestions = {}
    
    while queue:
        current_user, depth = queue.popleft()
        
        if depth >= max_depth:
            continue
        
        for friend in social_graph.get_neighbors(current_user):
            if friend not in visited:
                visited.add(friend)
                suggestions[friend] = suggestions.get(friend, 0) + 1
                queue.append((friend, depth + 1))
    
    return sorted(suggestions.items(), key=lambda x: x[1], reverse=True)

function friendSuggestions(graph, user, maxDepth = 2) {
    const visited = new Set([user]);
    const queue = [{user, depth: 0}];
    const suggestions = new Map();
    
    while (queue.length > 0) {
        const {user: current, depth} = queue.shift();
        
        if (depth >= maxDepth) continue;
        
        for (const {node: friend} of graph.getNeighbors(current)) {
            if (!visited.has(friend)) {
                visited.add(friend);
                suggestions.set(friend, (suggestions.get(friend) || 0) + 1);
                queue.push({user: friend, depth: depth + 1});
            }
        }
    }
    
    return [...suggestions.entries()].sort((a, b) => b[1] - a[1]);
}

public static List<Map.Entry<Integer, Integer>> 
        friendSuggestions(GraphList graph, int user, int maxDepth) {
    Set<Integer> visited = new HashSet<>();
    Map<Integer, Integer> suggestions = new HashMap<>();
    Queue<int[]> queue = new LinkedList<>();
    
    visited.add(user);
    queue.offer(new int[]{user, 0});
    
    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int currentUser = current[0];
        int depth = current[1];
        
        if (depth >= maxDepth) continue;
        
        for (GraphList.Edge edge : graph.getNeighbors(currentUser)) {
            int friend = edge.node;
            if (!visited.contains(friend)) {
                visited.add(friend);
                suggestions.put(friend, suggestions.getOrDefault(friend, 0) + 1);
                queue.offer(new int[]{friend, depth + 1});
            }
        }
    }
    
    return suggestions.entrySet().stream()
        .sorted((a, b) -> b.getValue() - a.getValue())
        .collect(Collectors.toList());
}

vector<pair<int, int>> friendSuggestions(GraphList& graph, int user, int maxDepth) {
    unordered_set<int> visited;
    unordered_map<int, int> suggestions;
    queue<pair<int, int>> q;
    
    visited.insert(user);
    q.push({user, 0});
    
    while (!q.empty()) {
        auto [currentUser, depth] = q.front();
        q.pop();
        
        if (depth >= maxDepth) continue;
        
        for (auto [friendId, weight] : graph.getNeighbors(currentUser)) {
            if (visited.find(friendId) == visited.end()) {
                visited.insert(friendId);
                suggestions[friendId]++;
                q.push({friendId, depth + 1});
            }
        }
    }
    
    vector<pair<int, int>> result(suggestions.begin(), suggestions.end());
    sort(result.begin(), result.end(),
         [](auto& a, auto& b) { return a.second > b.second; });
    return result;
}

GPS Navigation

Dijkstra/A*: Find shortest route

def find_shortest_route(graph, start, destination):
    distances, predecessors = dijkstra(graph, start)
    
    if distances[destination] == float('inf'):
        return None
    
    path = []
    current = destination
    while current is not None:
        path.append(current)
        current = predecessors[current]
    
    return {
        'path': path[::-1],
        'distance': distances[destination]
    }

function findShortestRoute(graph, start, dest) {
    const {distances, predecessors} = dijkstra(graph, start);
    
    if (distances[dest] === Infinity) return null;
    
    const path = [];
    let current = dest;
    while (current !== null) {
        path.unshift(current);
        current = predecessors[current];
    }
    
    return {path, distance: distances[dest]};
}

public class GPS {
    public static Route findShortestRoute(GraphList graph, int start, int dest) {
        int[] distances = dijkstra(graph, start, graph.getVerticesCount());
        
        if (distances[dest] == Integer.MAX_VALUE) return null;
        
        // Reconstruct path using predecessors (not shown for brevity)
        return new Route(path, distances[dest]);
    }
}

pair<vector<int>, int> findShortestRoute(GraphList& graph, int start, int dest) {
    auto dist = dijkstra(graph, start, graph.getVerticesCount());
    return {path, dist[dest]};
}

Report Content

Graph Data Structures: Algorithms & Applications

Graph Usage in Systems (2023)

1. Graph Representations

Adjacency Matrix

Definition

How It Works

Initialize matrix

Add edges

Query edges

Adjacency List

2. Breadth-First Search (BFS)

BFS Traversal

Definition

How It Works

Initialize queue

Process level by level

Repeat until queue empty

3. Depth-First Search (DFS)

DFS Traversal

Definition

How It Works

Recursive approach

Backtrack when done

4. Dijkstra's Shortest Path

Dijkstra's Algorithm

Definition

How It Works

Initialize distances

Extract minimum

Relax edges

5. Topological Sort

Topological Sort (DFS-based)

Definition

How It Works

DFS on each unvisited node

Post-order processing

6. Cycle Detection

Detect Cycle in Directed Graph

Definition

Graph Problem-Solving Cheat Sheet

7. Real-World Applications

Social Network Friend Suggestions

GPS Navigation

Graph Implementation Checklist

Share and Join the Discussion