Graph/Searching Algs

Breadth-First Search (BFS)

traverses the graph level by level using a queue

BFS Runtime

O(V + E) using adjacency list

BFS Uses

shortest paths in unweighted graphs

Depth-First Search (DFS)

traverses the graph as deep as possible using stack or recursion

DFS Runtime

O(V + E) using adjacency list

DFS Uses

cycle detection

Dijkstra’s Algorithm

finds shortest paths from a source vertex in a weighted graph with non-negative weights using a min-priority queue

Dijkstra Runtime

O(E log V) using binary heap

Dijkstra Uses

single-source shortest path in weighted graphs

Prim’s Algorithm

finds Minimum Spanning Tree by starting at a node and growing the MST one minimum-weight edge at a time using a priority queue

Prim Runtime

O(E log V) using binary heap

Prim Uses

constructing Minimum Spanning Tree for weighted graphs

Kruskal’s Algorithm

finds Minimum Spanning Tree by sorting all edges by weight and adding edges that do not create a cycle using Disjoint Set Union

Kruskal Runtime

O(E log V)

Kruskal Uses

constructing Minimum Spanning Tree for weighted graphs

Disjoint Set Union (Union-Find)

maintains disjoint sets of elements

DSU Runtime

nearly O(1) per operation (inverse Ackermann)

DSU Uses

cycle detection in Kruskal’s Algorithm

Graph Representation - Adjacency List

stores for each vertex a list of neighbors

Adjacency List Runtime

O(V + E) to traverse all vertices and edges

Graph Representation - Adjacency Matrix

stores a VxV matrix with edge weights or 0/1 for edges

Adjacency Matrix Runtime

O(V^2) to traverse all edges