There are three different sources for specifying an input graph:
Edit Graph: You can draw a new graph or edit an example unweighted directed graph as the input graph (to draw bidirectional edge (u, v), you can draw two directed edges u → v and v → u; or click 'Include Reverse Edges' button to do this for all directed edges).
Input Graph: You can specify Edge List/Adjacency Matrix/Adjacency List information and VisuAlgo will propose a 2D graph drawing layout of that graph.
Example Graphs: You can select from the list of our selected example graphs to get you started.
Quiz: Mini pre-requisite check. What are the Pre-/In-/Post-order traversal of the binary tree shown (root = vertex 0), left and right child are as drawn?
In = 4, 2, 3, 0, 1 In = 1, 0, 3, 2, 4 Post = 1, 3, 4, 2, 0 Post = 4, 3, 2, 1, 0 Pre = 0, 1, 2, 3, 4 Pre = 0, 2, 4, 3, 1
如果DFS在顶点 u 并且它有 X 个邻居，它会选择第一个邻居V1 (通常是序号最小的那个顶点), 使用递归访问所有 V1可以到达的顶点, 最终返回顶点 u. DFS 接下来对其他的邻居做同样的事指导探索完成最后一个邻居 VX 和它所能触及到的顶点.
等下看了DFS的动画 这个冗长的解释会变得清晰起来。
5-3. 避免循环
如果一个图是圈，之前的“尝试所有”的方法可能让DFS陷入循环。所以DFS的基本形式用一个大小为 V 个顶点的数组 status[u] 来确定两种情况 分别为 u 已经被访问过了 或者没有被访问过。只有当 u 还没有被访问过的时候 DFS才可以访问顶点 u.
当DFS没有路可走的时候它会跳出当前的递归 回去 到之前的顶点 (p[u], 看下一页).
5-4. 记住这个路径
DFS 用另一个大小为 V 个顶点数组 p[u] 来记住在DFS遍历路径上每一个顶点 u 的 parent/predecessor/previous（父/祖先/前）顶点。
最开始的顶点的祖先也就是 p[s] 被设定为-1也就是说它没有祖先 (因为最低的顶点是顶点0).
从一个源顶点 s 到一个可以到达的顶点 u 所生成的路径反过来 就是 DFS 生成树. 我们给这些 树边 上 红色.
5-5. 动手实例
For now, ignore the extra status[u] = explored in the displayed pseudocode and the presence of blue and grey edges in the visualization (to be explained soon).
Without further ado, let's execute DFS(0) on the default example graph for this e-Lecture (CP4 Figure 4.1). Recap DFS Example
The basic version of DFS presented so far is already enough for most simple cases.
5-6. O(V+E) 时间复杂度
DFS 的时间复杂度是 O(V+E) ，因为：
每个节点只访问过一次，因为 DFS 将仅递归地探索节点 u 如果 status[u] = unvisited — O(V)
每次访问完一个节点，都会探索其所有 k 个邻点，因此在访问所有节点之后，我们已检查了所有 E 边 — （O(E) ，因为i每个节点的邻点总数等于 E）。
5-7. 始终是 O(V+E) ？
DFS 的he O(V+E) 时间复杂度只有当我们可以在 O(k) 时间内访问一个顶点的所有 k 个邻点时才可以实现。
Quiz: Which underlying graph data structure support that operation?
CC = 0 for all u in V, set status[u] = unvisited for all u in V if (status[u] == unvisited) CC++ // 我们可以用CC计数器的数量来作为CC的标记 DFS(u) // 或者 BFS(u), 来标记它的成员为已访问 output CC // 上面的示例图的答案是3 // CC 0 = {0,1,2,3,4}, CC 1 = {5}, CC 2 = {6,7,8}
如果你想要给每一个CC你自己的标记，你可以简单修改 DFS(u)/BFS(u) 的代码。
7-5. 等等，时间复杂性是什么？
Quiz: What is the time complexity of Counting the Number of CCs algorithm?
已探索: DFS已经访问了 u, 但是至少有一个 u 的邻居还没有被探索 (DFS会先 深度优先 式的先去探索那个顶点的邻居),
已访问: 增强版的定义：顶点 u 的所有邻居都已经被探索过了并且DFS正要从顶点 u 原路返回去顶点 p[u].
如果DFS现在在顶点 x ，同时正在在探索边 x → y 并且遇到 status[y] = explored, 我们可以确认 x → y 是一个 返回边 (我们找到了一个圈因为我们之前在顶点 y (因此 status[y] = explored), 走更深去探索 y 的邻居等等, 但是我们现在在顶点 x ，它是一个可以从 y 出发所抵达的顶点 但是顶点 x 引领我们走回了 y).
DFS类比一个只有一个人口和一个出口的迷宫。您在 入口处，想要探索迷宫到达出口。显然你不能分身。