Graph Algorithms Cheat Sheet

Graph algorithms are fundamental for solving various computational problems involving networks, connectivity, and paths. This cheat sheet covers the most common graph algorithms, their steps, examples, time complexities, and practical applications.

1. Breadth-First Search (BFS)

Description: BFS is a traversal algorithm that explores all vertices at the present depth level before moving on to the next depth level.

Steps:

  1. Start at the root (or any arbitrary node) and mark it as visited.
  2. Explore all its neighboring nodes.
  3. For each neighboring node, add it to a queue.
  4. Dequeue a node from the front of the queue and repeat the process until the queue is empty.

Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.

BFS Example:

Graph:
1 - 2
|   |
3 - 4

BFS starting from node 1:
Visit order: 1 -> 2 -> 3 -> 4

2. Depth-First Search (DFS)

Description: DFS is a traversal algorithm that explores as far as possible along each branch before backtracking.

Steps:

  1. Start at the root (or any arbitrary node) and mark it as visited.
  2. Explore each branch fully before moving on to the next branch.
  3. Use a stack (or recursion) to backtrack when you reach a node with no unvisited neighbors.

Time Complexity: O(V + E)

DFS Example:

Graph:
1 - 2
|   |
3 - 4

DFS starting from node 1:
Visit order: 1 -> 2 -> 4 -> 3

3. Dijkstra's Algorithm

Description: Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph.

Steps:

  1. Initialize the distance to the source node as 0 and all other nodes as infinity.
  2. Set the source node as the current node and explore all its neighbors.
  3. For each neighboring node, calculate the tentative distance and update it if it's smaller than the current known distance.
  4. Once all neighbors are processed, mark the current node as visited and move to the next unvisited node with the smallest tentative distance.
  5. Repeat the process until all nodes are visited.

Time Complexity: O(V^2) with an adjacency matrix, O((V + E) log V) with a priority queue.

Dijkstra's Algorithm Example:

Graph (with edge weights):
1 -2- 2
|     |
3     1
|     |
3 -4- 4

Shortest paths from node 1:
1 -> 2 (distance 2)
1 -> 3 (distance 3)
1 -> 4 (distance 6)

4. A* Search Algorithm

Description: A* is an informed search algorithm that finds the shortest path using heuristics to estimate the distance to the goal.

Steps:

  1. Initialize the open list with the start node and calculate its f-score (g + h), where g is the cost from the start node and h is the heuristic estimate to the goal.
  2. While the open list is not empty, pick the node with the lowest f-score and explore its neighbors.
  3. For each neighbor, calculate the g-score and update it if it's lower than the current known g-score. Also, update the f-score.
  4. If the goal node is reached, reconstruct the path.

Time Complexity: O(E), where E is the number of edges.

A* Search Example:

Graph (with heuristic estimates):
1 -2- 2
|     |
3     1
|     |
3 -4- 4

Shortest path from 1 to 4 using A*:
Path: 1 -> 2 -> 4

5. Prim's Algorithm

Description: Prim's algorithm finds a minimum spanning tree for a weighted undirected graph, meaning it connects all vertices with the minimum possible total edge weight.

Steps:

  1. Start with any vertex and mark it as part of the MST (Minimum Spanning Tree).
  2. Find the minimum weight edge connecting a vertex in the MST to a vertex outside the MST and add it to the MST.
  3. Repeat the process until all vertices are included in the MST.

Time Complexity: O(V^2) with an adjacency matrix, O(E log V) with a priority queue.

Prim's Algorithm Example:

Graph (with edge weights):
1 -2- 2
|     |
3     1
|     |
3 -4- 4

Minimum Spanning Tree (MST):
Edges: (1-2), (2-4), (1-3)

6. Kruskal's Algorithm

Description: Kruskal's algorithm is another method to find the minimum spanning tree by adding edges in increasing order of weight, ensuring no cycles are formed.

Steps:

  1. Sort all edges in the graph by their weights.
  2. Start with an empty MST and add edges in the sorted order.
  3. Only add edges that do not form a cycle with the edges already in the MST.
  4. Repeat until the MST contains V-1 edges.

Time Complexity: O(E log E)

Kruskal's Algorithm Example:

Graph (with edge weights):
1 -2- 2
|     |
3     1
|     |
3 -4- 4

Minimum Spanning Tree (MST):
Edges: (1-2), (2-4), (1-3)

7. Bellman-Ford Algorithm

Description: The Bellman-Ford algorithm computes the shortest paths from a single source vertex to all other vertices in a weighted graph, handling graphs with negative weights.

Steps:

  1. Initialize the distance to the source node as 0 and all other nodes as infinity.
  2. Relax all edges V-1 times, where V is the number of vertices.
  3. Check for negative-weight cycles by checking if further relaxation is possible.

Time Complexity: O(VE)

Bellman-Ford Algorithm Example:

Graph (with edge weights):
1 -2- 2
|    -3
3     |
|     |
3 -4- 4

Shortest paths from node 1:
1 -> 2 (distance 2)
1 -> 3 (distance 3)
1 -> 4 (distance 6)

8. Floyd-Warshall Algorithm

Description: Floyd-Warshall is an all-pairs shortest path algorithm that computes the shortest paths between all pairs of vertices in a weighted graph.

Steps:

  1. Create a distance matrix initialized with edge weights and infinity for non-connected vertices.
  2. For each vertex k, update the distance matrix by considering paths that go through k.
  3. Repeat for all vertices to get the shortest paths.

Time Complexity: O(V^3)

Floyd-Warshall Algorithm Example:

Graph (with edge weights):
1 -2- 2
|     |
3    -1
|     |
3 -4- 4

Shortest paths between all pairs:
1 -> 2 (distance 2)
1 -> 3 (distance 3)
1 -> 4 (distance 5)
2 -> 4 (distance 3)

9. Topological Sorting

Description: Topological sorting of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering.

Steps:

  1. Perform DFS on the graph, keeping track of the order of vertices.
  2. Push vertices onto a stack after exploring all their neighbors.
  3. The stack contains the topological order when the DFS is complete.

Time Complexity: O(V + E)

Topological Sorting Example:

Graph:
1 -> 2 -> 4
|         
3 -> 4

Topological order:
1 -> 3 -> 2 -> 4

10. Tarjan's Algorithm

Description: Tarjan's algorithm finds all strongly connected components in a directed graph using DFS.

Steps:

  1. Perform DFS, tracking the discovery time and lowest reachable vertex.
  2. If a node has the same discovery and lowest reachable vertex, it's the root of a strongly connected component.
  3. Push nodes onto a stack and pop them when a strongly connected component is found.

Time Complexity: O(V + E)

Tarjan's Algorithm Example:

Graph:
1 -> 2
^    |
|    v
4 <- 3

Strongly connected components:
{1}, {2, 3, 4}

Conclusion

Understanding graph algorithms is essential for tackling complex problems in computer science. This cheat sheet provides a comprehensive overview of key algorithms, helping you master graph theory and its applications.