Graphs: Representation, BFS and DFS
Graphs: the adjacency list, depth- and breadth-first search, connected components and shortest paths.
A graph is vertices connected by edges: cities and roads, people and friendships, states and transitions. A huge class of problems is naturally phrased in graph language.
Storage: the adjacency list — for every vertex, a list of its neighbors. A vector of vectors g, where g[v] holds the neighbors of vertex v. The n×n adjacency matrix only suits small n.
The two basic traversals:
• DFS (depth-first): follow an edge as far as you can, then backtrack. Naturally written with recursion. Uses: connected components, cycle detection, topological sort.
• BFS (breadth-first): traverse in "waves" using a queue. Gives shortest distances in an unweighted graph.
DFS: the number of connected components. Enter: 6 3, then the edges: 1 2, 2 3, 4 5
In the example the vertices {1,2,3}, {4,5} and the lone {6} — three components.
BFS puts the start vertex into the queue, then repeats: take out a vertex — add all its unvisited neighbors. Vertices are processed in order of distance from the start, so dist is computed correctly.
BFS: distances from vertex 1. Enter: 5 4, then the edges: 1 2, 2 3, 3 4, 1 5
Both traversals are O(V + E): every vertex and every edge is processed once.
The rakes everyone steps on:
1. A forgotten visited mark — an infinite loop.
2. Recursive DFS on a chain of 10⁵+ vertices can overflow the call stack — write an iterative version with your own stack or raise the limit.
3. dist is initialized to -1 ("not visited"), and that same value is a ready answer for unreachable vertices.
Task: a maze n×m of dots and hashes — find the shortest path from the entrance to the exit (BFS over cells: the neighbors are the four sides).
Mark the lesson as completed.