- Path: is there a path between s and t?
- Shortest Path: what is the hsortest path between s and t?
- Cycle: is there a cycle in the graph? Short circuit detection for instance
- Euler tour: is there a cycle that uses each edge exactly once?
- Hamilton tour: is there a cycle that uses each vertax exactly once?
-
Connectivity: is there a way to connect all of the vertices?
-
MST (minimal spanning tree): What is the best way to connect the verticies
-
Biconnectivity: is there a vertex whose removal discconects the graph?
-
For topological sort, we look at a Digraph and DFS. In general, the "reverse dfs postorder of a DAG (diacyclic graph, directed graph with no cycles) is topological order". Reverse postorder means that you get the deepest node in a dfs and put it on a stack once there are no other unvisited nodes to explore.
- Planarity: Can you draw the graph in the plane with no crossing edges?
- Graph isopmorphism: Do two adjacency lists represent the same graph?
- We'll use adjacency-list representation for storage
- dfs also computed connected components for O(1) lookup
Depth-first Search 0 | Search 1 | | Search 2 | | | Search 8 | | | | Search 9 | | | | | Search 10 | | | | | | Search 11 | | | | | | | Search 17 | | | | | | 17 = 11 | | | | | | | Search 12 | | | | | | | | Search 13 | | | | | | | | | Search 14 | | | | | | | | | | Search 15 | | | | | | | | | | | Search 16 | | | | | | | | | | 16 = 15 | | | | | | | | | 15 = 14 | | | | | | | | 14 = 13 | | | | | | | 13 = 12 | | | | | | 12 = 11 | | | | | 11 = 10 | | | | 10 = 9 | | | 9 = 8 | | 8 = 2 | | | Search 6 | | | | Search 7 | | | 7 = 6 | | 6 = 2 | | | Search 3 | | | | Search 4 | | | | | Search 5 | | | | 5 = 4 | | | 4 = 3 | | 3 = 2 | 2 = 1 1 = 0 Search 18 | Search 19 19 = 18 17 -> 11 -> 10 -> 9 -> 8 -> 2 -> 1 -> 0 0 -> 19? false 0 -> 17? false connected [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1] unvisited [] Breadth-first Search 0 Search 1 Search 11 Search 2 Search 12 Search 17 Search 8 Search 6 Search 3 Search 13 Search 9 Search 7 Search 4 Search 14 Search 10 Search 5 Search 15 Search 16 17 -> 11 -> 0 unvisited [18, 19] Reverse postorder (topological sort) [18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]