|
检测有向图中的环在有向图中，我们将检查图是否包含环。有向图是由边连接的一组顶点或节点，每条边都与某个方向相关联。 考虑下面的有向图来检测周期。  现在，我们将使用DFS在有向图中检测循环的技术。由于我们正在使用DFS技术，所以我们将使用堆栈数据结构为实现。这里，我们将使用包含三个值的标志变量，即0、1和-1。这里，0表示节点已被访问并且在堆栈中可用，-1表示节点未被访问，1表示节点已被访问并且已从堆栈中弹出。 最初，所有顶点都标记为-1，因为它们都没有被访问。 步骤1:首先，我们访问顶点A，标记为0。由于节点A已经被访问过，所以它将被标记为0，节点A被压入堆栈，如下所示:   访问集包含节点A，如下所示: 访问设置:一个 父映射表如下:  由于访问了节点A，因此节点A位于顶点列下，父列留空，因为节点A是源顶点。 步骤2:下一个顶点是B，现在，我们将访问顶点B，它将被标记为0。由于节点B已经被访问过，所以它将被标记为0，节点B被压入堆栈，如下所示:   访问节点包含如下所示的节点A和节点B: 访问设置:A、B 父映射表如下所示:  因为节点B已经被访问过，所以B在顶点列下，A在父列下，因为B来自节点A。 步骤3:B的相邻顶点是C和D，这意味着我们可以访问C或D。假设我们访问了顶点C，那么顶点C将被标记为0，节点C被推入堆栈，如下所示:   现在，访问集包含节点A、B、C，如下图所示: 参观组:A, B, C 父映射表如下所示:  因为访问过节点C，所以C在顶点列下，B在父列下。 步骤4:从C开始没有需要访问的其他顶点，所以我们将执行回溯。为了执行回溯，我们将弹出节点。首先，我们将从堆栈中弹出节点C。由于节点C已经弹出，所以我们将节点C标记为1，如下图所示:  堆栈中下一个最顶层的节点是B，所以我们将回溯到顶点B，如下所示: 步骤5:现在，我们来看看是否还有相邻的点可以访问。我们可以在上图中观察到顶点D是未访问的。那么，现在我们将从顶点B移动到顶点D。顶点D的标志值现在变为0，并且顶点D被压入堆栈，如下所示:   现在访问的集合包含节点A, B, C, D 父映射表如下所示:  因为已经访问了节点D，所以它位于顶点列下，而节点D是从顶点B到达的，所以顶点B位于父列下。 步骤6:节点D的相邻顶点是未访问的节点E。现在我们将访问顶点E，并将其标志值标记为0。节点E被推入堆叠，如下图所示:   现在，访问集包含节点A, B, C, D, E。 父映射表如下所示:  由于访问了节点E，它位于顶点列下，而节点E是从顶点D到达的，因此D位于父列下。 条件 有一个条件决定图是否包含循环。如果任何顶点的相邻顶点的标志值为0，则表示该图包含一个循环。 上图中，E的相邻顶点为B，其标志值为0;因此，图中包含一个循环。 现在我们将确定在图中创建一个循环的节点。 E的邻顶点是B; E - B > E的父母是D。 D - > E - > B D的父结点是B， B->D->E->B(形成循环)
下一个话题
最优二叉搜索树
|
视频加入我们的Youtube频道:现在加入
反馈
- 将你的意见发送至(电子邮件保护)
帮助别人，请分享
