Formula Sheets: Graph Based Algorithms

 Page 1


Graph Based Algorithms
Graph Searc h Algorithms
Breadth-First Searc h (BFS)
• Time Complexit y: O(V +E) , where V is v ertices, E is edges (adjacency list).
• Space Complexit y: O(V ) for queue and visited arra y .
Depth-First Searc h (DFS)
• Time Complexit y: O(V +E) (adjacency list).
• Space C omplexit y: O(V ) for recursion stac k and visited arra y .
T op ological Sorting
T op ological Sor t (D A G)
• Using DFS: Pro ce ss v ertices in decreasing order of finish time.
• Using Kahn’s Algorith m: Remo v e v ertices with in-degree 0.
• Time C omplexit y: O(V +E) .
• Space Comple xit y: O(V ) for stac k or queue.
Shortest P ath Algorithms
Dijkstra’s A lgorithm
• Time Comple xit y: O((V +E)logV ) with binary heap, O(V
2
) with arra y .
• Space Complexit y: O(V ) for distance arra y and heap.
Bellman-F ord A lgorithm
• Time Comple xit y: O(V ·E) .
• Space Complexit y: O(V ) for distance arra y .
Flo yd-W arshall Al gorithm
• Time Comple xit y: O(V
3
) .
• Space Complexit y: O(V
2
) for distance matrix.
Minim um Spanning T ree
Kruskal’s Algori thm
• Time Comple xit y: O(E logE) (sorting edges + Union-Find).
• Space Complexit y: O(V +E) .
Prim’s A lgorithm
• Time Com plexit y: O((V +E)logV ) with binary heap.
• Space Comple xit y: O(V ) for heap and visited arra y .
Connectivit y Algorithms
K osara ju’s Algori thm (Strongly Connected Comp onen ts)
• Time Comple xit y: O(V +E) (t w o DFS passes).
• Space Complexit y: O(V ) for stac k and visited arra y .
Bridges in a Graph
1
Page 2


Graph Based Algorithms
Graph Searc h Algorithms
Breadth-First Searc h (BFS)
• Time Complexit y: O(V +E) , where V is v ertices, E is edges (adjacency list).
• Space Complexit y: O(V ) for queue and visited arra y .
Depth-First Searc h (DFS)
• Time Complexit y: O(V +E) (adjacency list).
• Space C omplexit y: O(V ) for recursion stac k and visited arra y .
T op ological Sorting
T op ological Sor t (D A G)
• Using DFS: Pro ce ss v ertices in decreasing order of finish time.
• Using Kahn’s Algorith m: Remo v e v ertices with in-degree 0.
• Time C omplexit y: O(V +E) .
• Space Comple xit y: O(V ) for stac k or queue.
Shortest P ath Algorithms
Dijkstra’s A lgorithm
• Time Comple xit y: O((V +E)logV ) with binary heap, O(V
2
) with arra y .
• Space Complexit y: O(V ) for distance arra y and heap.
Bellman-F ord A lgorithm
• Time Comple xit y: O(V ·E) .
• Space Complexit y: O(V ) for distance arra y .
Flo yd-W arshall Al gorithm
• Time Comple xit y: O(V
3
) .
• Space Complexit y: O(V
2
) for distance matrix.
Minim um Spanning T ree
Kruskal’s Algori thm
• Time Comple xit y: O(E logE) (sorting edges + Union-Find).
• Space Complexit y: O(V +E) .
Prim’s A lgorithm
• Time Com plexit y: O((V +E)logV ) with binary heap.
• Space Comple xit y: O(V ) for heap and visited arra y .
Connectivit y Algorithms
K osara ju’s Algori thm (Strongly Connected Comp onen ts)
• Time Comple xit y: O(V +E) (t w o DFS passes).
• Space Complexit y: O(V ) for stac k and visited arra y .
Bridges in a Graph
1
• Using DFS: Edge (u,v) is a bridge if low[v] > disc[u] , where low[v] is lo w est disco v ery time reac hable,
disc[u] is disco v ery time.
• Time Complexit y: O(V +E) .
• Spac e Complexit y: O(V ) for disco v ery and lo w arra ys.
T ransitiv e Closure (Flo yd-W arshall)
• Tim e Complexit y: O(V
3
) .
• Space C omplexit y: O(V
2
) for reac habilit y matrix.
2