Graph Algorithms

Master algorithms for analyzing networks, relationships, and connected data. From basic traversals to advanced pathfinding and network optimization algorithms.

Graph Traversal

Systematically visit all vertices and edges

BFS • DFS

Shortest Path

Find optimal paths between vertices

Dijkstra • Bellman-Ford • Floyd-Warshall

Minimum Spanning Tree

Connect all vertices with minimum total weight

Kruskal • Prim

Graph Properties

Analyze structural properties of graphs

Topological Sort • SCC • Cycle Detection

Essential Graph Algorithms

Breadth-First Search (BFS)

Explores graph level by level, finding shortest path in unweighted graphs

• Finds shortest path
• Explores systematically

Cons:

• Uses more memory

Use Cases:

• Shortest path in unweighted graphs

Depth-First Search (DFS)

Explores as far as possible along each branch before backtracking

• Memory efficient
• Can detect cycles

Cons:

• May get stuck in deep paths

Use Cases:

• Topological sorting

Dijkstra's Algorithm

Finds shortest path from source to all vertices in weighted graphs

• Optimal for non-negative weights
• Widely applicable

Cons:

• Cannot handle negative weights

Use Cases:

• GPS navigation

Bellman-Ford Algorithm

Finds shortest paths and detects negative weight cycles

• Handles negative weights
• Detects negative cycles

Cons:

• Slower than Dijkstra

Use Cases:

• Currency exchange

Floyd-Warshall Algorithm

Finds shortest paths between all pairs of vertices

• All pairs shortest path
• Handles negative weights

Cons:

• High time complexity

Use Cases:

• Distance matrices

Kruskal's Algorithm

Finds minimum spanning tree by selecting edges in ascending order

• Simple greedy approach
• Works well for sparse graphs

Cons:

• Requires edge sorting

Use Cases:

• Network design

Prim's Algorithm

Builds minimum spanning tree by growing tree from starting vertex

• Good for dense graphs
• Can start from any vertex

Cons:

• More complex than Kruskal

Use Cases:

• Network infrastructure

Topological Sort

Linear ordering of vertices in directed acyclic graph (DAG)

• Essential for DAG problems
• Multiple algorithms available

Cons:

• Only works on DAGs

Use Cases:

• Task scheduling

Strongly Connected Components

Finds maximal strongly connected subgraphs using algorithms like Tarjan or Kosaraju

• Important graph property
• Linear time algorithms

Cons:

• Complex implementation

Use Cases:

• Social network analysis

Graph Representations

Adjacency Matrix

2D array where matrix[i][j] = 1 if edge exists between vertex i and j

Time Complexity: O(1) edge lookup, O(V²) space

Best for: Dense graphs, frequent edge queries

Cons: High space usage, inefficient for sparse graphs

Adjacency List

Array of lists where list[i] contains all neighbors of vertex i

Time Complexity: O(degree) edge lookup, O(V + E) space

Best for: Sparse graphs, memory efficiency

Cons: Slower edge existence check

When to Use Each Algorithm

Graph Exploration

Use BFS for shortest path in unweighted graphs, DFS for cycle detection and topological sorting

Single-Source Shortest Path

Use Dijkstra for non-negative weights, Bellman-Ford when negative edges exist

All-Pairs Shortest Path

Use Floyd-Warshall for small dense graphs, run Dijkstra from each vertex for sparse graphs

Minimum Spanning Tree

Use Kruskal for sparse graphs, Prim for dense graphs or when starting vertex matters

Task Scheduling

Use Topological Sort for dependency resolution and ordering problems

Network Analysis

Use SCC algorithms to identify clusters and strongly connected components

Time Complexity Summary

Algorithm	Time Complexity	Space Complexity	Graph Type
BFS / DFS	O(V + E)	O(V)	Any
Dijkstra	O((V + E) log V)	O(V)	Non-negative weights
Bellman-Ford	O(V × E)	O(V)	Any weighted
Floyd-Warshall	O(V³)	O(V²)	Any weighted
Kruskal	O(E log E)	O(V)	Undirected weighted
Prim	O(E log V)	O(V)	Undirected weighted

Explore Graph Algorithms

Visualize networks and see algorithms work on real graph structures

Start with BFS

Back to Searching Next: Dynamic Programming