Graphs
1. What Is Breadth-First Search? Core idea: expand level by level Breadth-first search (BFS) is the other classic graph traversal algorithm. Starting from a source vertex, it first visits all of its immediate neighbors — these form the first level. Then it visits, in order, all not-yet-visited neighbors of the first-level nodes — these form the second level. The process resembles the ripples spreading out when a stone is dropped into water: it expands outward one level at a time until every reachable node has been visited. Key data structure: the queue BFS makes perfect use of a queue’s first-in, first-out (FIFO) property to guarantee level-by-level traversal order.
Read note →1. What Is a Graph? Concept: From Trees to Graphs A graph can be understood as an extension and generalization of the tree structure. In fact, a tree is just a special kind of graph. A graph consists of a set of vertices and a set of edges. Each edge connects a pair of vertices in the graph. Graphs can model more complex real-world relationships, and are no longer restricted to the hierarchical relationships of a tree. Applications of Graphs Social networks: individuals or organizations are vertices; the social connections between them are edges. Maps and navigation: key locations (intersections, landmarks) are vertices; roads are edges. Computer networks: computers or routers are vertices; network connections are edges. 2. Key Terminology Undirected Graph Edges have no direction. If there is an edge between vertices A and B, we can travel from A to B and also from B to A.
Read note →1. DFS: From Trees to Graphs Core idea recap: follow one path to the end The core idea of depth-first search (DFS) — explore a branch as deeply as possible, then backtrack when you hit a dead end — carries over to graphs unchanged.
The new challenge: cycles Trees are acyclic. We move from a parent node to its children and never “walk back” to the parent. (For unrooted trees, this is avoided by passing the parent node as a parameter.) General graphs contain cycles. If we travel from u to v, v may well reach back to u along some other path. If this is not handled, DFS will fall into an infinite loop when it hits a cycle, causing a stack overflow. The solution: mark visited nodes We need an auxiliary data structure — typically a boolean array visited — to record which nodes have already been visited. Before visiting a new node, check whether it has been visited already.
Read note →Union-Find (Disjoint Set Union) Problem Definition Given N mutually disjoint sets, we need to support two operations:
Merge: Union two sets together Query: Determine whether two elements belong to the same set Example Operation Sequence Elements: a, b, c, d, e, f
Operations: Merge(a,b), Merge(b,e), Merge(c,f), Merge(b,f)
Approach 1: Naive Label-Based Assign each element a set ID. To merge, update all elements of one set to the other’s ID.
Operation a b c d e f Init 1 2 3 4 5 6 Merge(a,b) 1 1 3 4 5 6 Merge(b,e) 1 1 3 4 1 6 Merge(c,f) 1 1 3 4 1 3 Merge(b,f) 1 1 1 4 1 1 Complexity: Query: O(1) | Merge: O(n)
Read note →