1. Graph Basics
A graph is a collection of vertices (nodes) connected by edges (links). Graphs can be:
- Directed Graph (Digraph): Edges have a direction.
- Undirected Graph: Edges do not have a direction.
- Weighted Graph: Edges have weights (costs).
- Unweighted Graph: Edges have no weights.
Graph Representation:
- Adjacency Matrix: 2D array where
matrix[i][j]represents the edge between nodeiand nodej. - Adjacency List: Array of lists where each list represents the nodes connected to a particular node.
2. Depth-First Search (DFS)
Description:
DFS explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack.
Steps:
Given Graph:
1 / \ 2 3 / \ 4 5
Starting from Node 1:
1 → 2 → 4 → 5 → 3
Time Complexity:
- O(V + E) (V = vertices, E = edges)
Space Complexity:
- O(V) (for recursion stack or explicit stack)
Applications:
- Pathfinding
- Cycle detection
- Topological sorting
3. Breadth-First Search (BFS)
Description:
BFS explores all neighbors of a node before moving to their neighbors. It uses a queue for implementation.
Steps:
Given Graph:
1 / \ 2 3 / \ 4 5
Starting from Node 1:
1 → 2 → 3 → 4 → 5
Time Complexity:
- O(V + E)
Space Complexity:
- O(V) (for the queue)
Applications:
- Shortest path (unweighted graphs)
- Connected components
- Peer-to-peer networks
4. Dijkstra’s Algorithm
Description:
Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative weights.
Steps:
Given Graph:
1
/ | \
2 3 4
\ | /
5
Starting from Node 1:
- Initialize distances to all nodes as infinity (except the source).
- Set distance of source to 0.
- Visit the nearest unvisited node, update its neighbors.
- Repeat until all nodes are visited.
Time Complexity:
- O((V + E) log V) (using a priority queue)
Space Complexity:
- O(V) (for distance storage)
Applications:
- Shortest path in maps
- Network routing
5. Bellman-Ford Algorithm
Description:
Bellman-Ford finds the shortest path from a source to all vertices in a graph, even if it contains negative weights.
Steps:
- Initialize distances from the source to all vertices as infinity.
- Relax all edges
V-1times (update if a shorter path is found). - Check for negative cycles by trying to relax once more.
Time Complexity:
- O(V * E)
Space Complexity:
- O(V)
Applications:
- Graphs with negative weights
- Currency arbitrage detection
6. Floyd-Warshall Algorithm
Description:
Floyd-Warshall finds the shortest path between all pairs of vertices.
Steps:
- Create a distance matrix.
- For each intermediate node, update shortest paths.
Time Complexity:
- O(V³)
Space Complexity:
- O(V²)
Applications:
- All-pairs shortest paths
- Network analysis
7. Prim’s Algorithm
Description:
Prim’s algorithm finds the Minimum Spanning Tree (MST) by growing the tree from an arbitrary starting node.
Steps:
- Select an arbitrary node as the starting point.
- Grow the MST by adding the smallest edge connecting the tree to a new vertex.
Time Complexity:
- O((V + E) log V) (using a priority queue)
Space Complexity:
- O(V + E)
Applications:
- Network design
- Cable layout
8. Kruskal’s Algorithm
Description:
Kruskal’s algorithm finds the Minimum Spanning Tree by sorting all edges and adding them one by one.
Steps:
- Sort all edges by weight.
- Add the smallest edge to the MST if it doesn’t form a cycle (using a Union-Find structure).
Time Complexity:
- O(E log E)
Space Complexity:
- O(V)
Applications:
- Network optimization
9. Topological Sorting
Description:
Topological sorting orders vertices in a Directed Acyclic Graph (DAG) such that for any directed edge u → v, u appears before v.
Steps:
- Perform DFS and record the finishing order.
- Reverse the finishing order.
Time Complexity:
- O(V + E)
Space Complexity:
- O(V)
Applications:
- Task scheduling
- Dependency resolution
10. Comparison of Graph Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Use Case |
|---|---|---|---|---|
| DFS | O(V + E) | O(V + E) | O(V + E) | Pathfinding, Cycle Detection |
| BFS | O(V + E) | O(V + E) | O(V + E) | Shortest path (unweighted) |
| Dijkstra | O((V + E) log V) | O((V + E) log V) | O((V + E) log V) | Shortest path (non-negative) |
| Bellman-Ford | O(V * E) | O(V * E) | O(V * E) | Negative weights detection |
| Floyd-Warshall | O(V³) | O(V³) | O(V³) | All-pairs shortest path |
| Prim’s Algorithm | O((V + E) log V) | O((V + E) log V) | O((V + E) log V) | Minimum Spanning Tree |
| Kruskal’s Algorithm | O(E log E) | O(E log E) | O(E log E) | Minimum Spanning Tree |
| Topological Sort | O(V + E) | O(V + E) | O(V + E) | DAG task scheduling |
Which Graph Algorithm to Use?
- DFS/BFS: For exploring, searching, and connected components.
- Dijkstra: For shortest paths with non-negative weights.
- Bellman-Ford: For graphs with negative weights.
- Floyd-Warshall: For all-pairs shortest paths.
- Prim/Kruskal: For Minimum Spanning Trees.
- Topological Sort: For task scheduling in DAGs.