代码之家 › 专栏 › 技术社区 › 101ldaniels

DFS发现和完成时间

depth-first-search tree graph algorithm

101ldaniels · 技术社区 · 9 年前

假设我们通过遵守以下规则对该图执行DFS:

在每个顶点,按id的升序处理其外邻居。

身份证件

显示结果DFS林。此外,对于每个顶点,指示其发现时间和完成时间。同时#/=发现和35;/#=完成

dfs树如下所示:

               6
               |
1--2--7--3--4--5--8

问题是让我展示生成的森林,但我只生产了一棵树,我做错了什么?

2 回复 | 直到 9 年前

Paul 9 年前

你什么都没错过。森林是一组图,因此甚至允许包含0个图。因此,结果中的图forst是绝对有效的。有些讲师倾向于使用他们自己的定义,所以我建议用你的脚本再检查一遍。对于DFS遍历,显示存在从1到的路径是非常有效和非常简单的任何树中的节点

Ankit Kumar 5 年前

发现时间跟踪第一次遇到顶点之前算法中的步骤数。

推荐文章

root · 计数算法

3 年前

Ash · 递归列表拆分和索引

4 年前

Someone · 如何实际删除节点?

4 年前

bb ef · 如何使用递归从列表中删除某些内容?python

8 年前

Linkmaster · 在用于BST的类中是否可能有类成员变量BST?

8 年前

Adam Morad · 方案更改树值

8 年前

A Akshat · 如何为函数中的结构分配动态内存插槽,该结构可以从程序中的任何位置访问

8 年前

johnny 5 · 角度将ViewChild绑定到类中的属性

8 年前

user2467011 · 为什么给定的二叉树是用空节点构造的?

8 年前

Yuki.kuroshita · 从二叉树中删除节点及其所有子节点,而不使用树数据结构

8 年前