Graph Theory Examples

Math for CS · Axiom Academy

EXAMPLE Graph Theory Worked Problems 5 fully worked examples covering traversal, shortest paths, and graph properties An unweighted undirected graph has vertices and edges . Find the shortest path from vertex 1 to vertex 6. Level 1: 2, 3 (neighbors of 1) Level 2: 4, 5 (neighbors of 2 and 3 not yet visited) Level 3: 6 (neighbor of 4 or 5) Vertex 6 is first reached at level 3, so the shortest path has 3 edges . Following parent pointers: , giving the path . (Note: and are also shortest paths.) Example 2: DFS Cycle Detection A directed graph has edges . Does it contain a cycle? Trace DFS from A. Visit D (GRAY). Explore edge . B is GRAY (still on the recursion stack). An edge to a GRAY vertex is a back edge , which indicates a cycle. The cycle is , a cycle of length 3. Key rule: In DFS on a directed graph, a back edge (to a GRAY ancestor) always means a cycle exists. Find a topological ordering of the DAG with edges: . Run DFS (starting alphabetically) and record finish times: DFS(A): visit A → C → E. E finishes (time 1), C finishes (2). Then A → D, but D has unvisited neighbor E (already finished). D finishes (3). A finishes (4). DFS(B): visit B → D (already finished). B finishes (5). Finish times: E=1, C=2, D=3, A=4, B=5. Topological order = decreasing finish time: B, A, D, C, E . Verification: Every edge goes from left to right in this ordering: (ok), (ok), (ok), (ok), (ok). Example 4: Dijkstra's Algorithm

This is the written version of the interactive lesson above. See the full Math for CS course.