Menu
CoddyTech

它是如何工作的?

Coddy 深度优先搜索:图算法 课程的第 3 课,共 9 课。

DFS 会为每个顶点保留一个 visited 标记,并维护一个用于待处理顶点的 stack。

分步过程:

  1. 将起始顶点压入栈中。
  2. 弹出一个顶点。如果它已经访问过,就跳过。否则,将它标记为已访问,并按访问顺序记录下来。
  3. 将它尚未访问过的邻居压入栈中。若要按升序访问它们,就按从大到小的顺序压入,这样最小的顶点会先弹出。
  4. 重复以上步骤,直到栈为空。

以顶点 0..3 和边 [0,1, 0,2, 1,3, 2,3] 为例,从 0 开始:

  • 访问 0,然后访问它最小的邻居 1,再访问 1 的邻居 3,最后访问 3 的邻居 2。
  • 访问顺序:[0, 1, 3, 2]。

只会访问从起始顶点可达的顶点。

亲手试试

这节课没有代码挑战。

quiz icon自我测试

这节课包含一个小测验。开始学习即可作答,并记录你的进度。

深度优先搜索:图算法中的所有课

自己练习: C 在线编译器