它是如何工作的?
Coddy 深度优先搜索:图算法 课程的第 3 课,共 9 课。
DFS 会为每个顶点保留一个 visited 标记,并维护一个用于待处理顶点的 stack。
分步过程:
- 将起始顶点压入栈中。
- 弹出一个顶点。如果它已经访问过,就跳过。否则,将它标记为已访问,并按访问顺序记录下来。
- 将它尚未访问过的邻居压入栈中。若要按升序访问它们,就按从大到小的顺序压入,这样最小的顶点会先弹出。
- 重复以上步骤,直到栈为空。
以顶点 0..3 和边 [0,1, 0,2, 1,3, 2,3] 为例,从 0 开始:
- 访问 0,然后访问它最小的邻居 1,再访问 1 的邻居 3,最后访问 3 的邻居 2。
- 访问顺序:[0, 1, 3, 2]。
只会访问从起始顶点可达的顶点。
亲手试试
这节课没有代码挑战。
这节课包含一个小测验。开始学习即可作答,并记录你的进度。
深度优先搜索:图算法中的所有课
自己练习: C 在线编译器