Depth-First Search
Depth First Search Algorithm:
- follow path until you get stuck
- backtrack along breadcrumbs(面包屑…) until reach unexplored neighbor
- recursively explore
- careful not to repeat a vertex
Pseudo codes are as follows:
Note that DFS and DFS-visit are two things. DFS is the top level of DFS-visit and it makes sure that all the vertex will be visited.
Edge Classification
- tree edges (parent pointer): visit new vertex via edge
- forward edges: node -> descendant in tree
- backward edges: node -> ancestor in tree
- cross edges: other edges (from one tree to another) between two non-ancestor-related subtrees
To compute this classification (back or not), mark nodes for duration they are “on the stack” - only tree and back edges in undirected graph
Analysis
- DFS-visit gets called with a vertex s only once (because then parent[s] set)
- ⇒ time in DFS-visit = $\sum_{s∈V}|Adj[s]| = O(E)$
- DFS outer loop adds just $O(V)$
- ⇒ $O(V + E)$ time (linear time)
Cycle Testing
For directed graph:
- DFS can be used to detect a cycle in a Graph.
- DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph.
- For a disconnected graph, get the DFS forest as output. To detect cycle, we can check for a cycle in individual trees by checking back edges.
Topological Sort
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.
- The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).
- We can modify DFS to find Topological Sorting of a graph.
- In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices.
- In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
Reference:
https://www.geeksforgeeks.org/topological-sorting/
https://www.geeksforgeeks.org/detect-cycle-in-a-graph/