šøļø Graph Algorithms
Traverse, search, and optimize graph structures. Master BFS, DFS, shortest paths, and minimum spanning trees.
Overview
What are Graph Algorithms?
Key Graph Algorithms
Breadth-First Search
Level-by-level graph traversal using a queue
Depth-First Search
Explore as far as possible before backtracking
Dijkstra's Algorithm
Shortest path from source to all vertices (positive weights)
Kruskal's Algorithm
Minimum spanning tree using union-find
Topological Sort
Linear ordering of DAG vertices respecting edges
Interactive Visualizer
Graph Visualization
Breadth-First Search Graph Visualizer
Interact with nodes and edges to see how graph algorithms traverse and process graph structures.
Deep Dive: Breadth-First Search
Time Complexity
Time: O(V + E)Space Complexity
Space: O(V)Requires
GraphAlgorithm Approach
python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Represent Graph
Choose adjacency list, matrix, or edge list based on density and operations needed.
Initialize State
Set up visited set, distances, queue/stack/priority queue as needed.
Process Vertices
Follow algorithm-specific rules to explore neighbors and update state.
Return Results
Extract path, distances, ordering, or tree structure from computed state.
Real-World Applications
Social Networks
Friend recommendations, mutual connections, influence analysis
GPS Navigation
Shortest path computation for route planning and traffic optimization
Web Crawling
BFS crawls web pages level by level from a seed URL
Circuit Design
Topological sort for determining component order
Network Routing
OSPF protocol uses Dijkstra for shortest path routing
AI & Game Dev
Pathfinding (A*), game state exploration, decision trees
Interview Questions
What's the difference between BFS and DFS?
BFS uses a queue and finds shortest path in unweighted graphs. DFS uses a stack (or recursion) and uses less memory on average. BFS is better for finding closest solutions; DFS is better for exploring entire graphs.
Why doesn't Dijkstra work with negative edges?
Dijkstra assumes adding more edges always increases distance. With negative edges, a longer path might have lower total weight. Bellman-Ford handles negative edges by relaxing all edges V-1 times.
What are the tradeoffs between adjacency list and matrix?
Adjacency list: O(V+E) space, O(deg(v)) neighbor iteration. Adjacency matrix: O(VĀ²) space, O(1) edge lookup. Lists are better for sparse graphs; matrices for dense graphs.
Knowledge Check
1. What data structure does BFS use?
2. What data structure does DFS use?
3. Can Dijkstra handle negative edge weights?
4. What does Kruskal's algorithm find?
5. When can topological sort be applied?