Graph Algorithms Quick Guide
A short guide to BFS, DFS, shortest paths, minimum spanning trees, and topological sort.
1. Graph Basics
A graph is a set of vertices/nodes connected by edges. Graphs model maps, networks, friendships,
web links, dependencies, and game states.
Term Meaning Example
Vertex / node A point in the graph City, person, webpage
Edge A connection between nodes Road, friendship, link
Directed edge Edge has direction One-way road
Weighted edge Edge has cost or distance Flight price, road length
Path A sequence of connected nodes A route from A to B
A graph can be stored as an adjacency list, adjacency matrix, or edge list. For most programming problems,
adjacency lists are flexible and memory-efficient.
2. Breadth-First Search and Depth-First Search
Algorithm Data structure Best for Time
BFS Queue Shortest path in unweighted graph, level order O(V + E)
DFS Stack or recursion Exploring all possibilities, components, cycle O(V + E)
checks
BFS pattern
from collections import deque
def bfs(graph, start):
visited = set([start])
q = deque([start])
while q:
node = [Link]()
for nxt in graph[node]:
if nxt not in visited:
[Link](nxt)
[Link](nxt)
return visited
DFS pattern
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
[Link](node)
for nxt in graph[node]:
if nxt not in visited:
dfs(graph, nxt, visited)
return visited
3. Shortest Path Algorithms
Computer Algorithms - Quick Guide Page 1
Algorithm Use when Handles negative Main idea
edges?
BFS shortest path Unweighted graph Not needed Each edge has cost 1
Dijkstra Weighted graph, non-negative No Always expand current cheapest
costs node
Bellman-Ford Negative edge weights may exist Yes Relax all edges repeatedly
Floyd-Warshall All-pairs shortest paths Yes, but no negative Dynamic programming over
cycles intermediate nodes
Dijkstra pattern
import heapq
def dijkstra(graph, start):
dist = {start: 0}
pq = [(0, start)]
while pq:
cost, node = [Link](pq)
if cost > [Link](node, float('inf')):
continue
for nxt, weight in graph[node]:
new_cost = cost + weight
if new_cost < [Link](nxt, float('inf')):
dist[nxt] = new_cost
[Link](pq, (new_cost, nxt))
return dist
Do not use Dijkstra if edge weights can be negative. Use Bellman-Ford instead.
4. Minimum Spanning Tree and Topological Sort
Problem Algorithm Use case
Connect all nodes with minimum Kruskal or Prim Network cables, roads, clustering
total cost
Order tasks with prerequisites Topological sort Course planning, build systems,
scheduling
Detect strongly connected groups Kosaraju or Tarjan Social networks, web graph analysis
Topological sort idea
• Only works on a directed acyclic graph (DAG).
• A cycle means the tasks cannot be ordered normally.
• Kahn method: repeatedly take nodes with zero incoming edges.
from collections import deque
def topo_sort(graph, indegree):
q = deque([node for node in graph if indegree[node] == 0])
order = []
while q:
node = [Link]()
[Link](node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
[Link](nxt)
return order
5. Practice Questions
Computer Algorithms - Quick Guide Page 2
• Which algorithm finds the shortest route in an unweighted maze?
• Which algorithm finds the cheapest route when every road has a non-negative distance?
• What does topological sort require: a general graph or a DAG?
• Why does DFS help find connected components?
• What graph algorithm could help design the cheapest set of cables connecting buildings?
Answer hints
• Unweighted maze: BFS.
• Non-negative weighted routes: Dijkstra.
• Topological sort requires a DAG.
• DFS can explore every node reachable from a starting point.
• Minimum spanning tree: Kruskal or Prim.
Computer Algorithms - Quick Guide Page 3