检测有向图中的循环

在一个有向图中，我们将检查图是否包含环。有向图是一组通过边连接的顶点或节点，每条边都关联着某个方向。

考虑下面的有向图来检测环。

现在，我们将使用DFS技术来检测有向图中的环。由于我们使用DFS技术，因此我们将使用栈数据结构进行实现。在这里，我们将使用一个标志变量，它包含三个值，即0、1和-1。其中，0表示节点已被访问并在栈中可用，-1表示节点未被访问，1表示节点已被访问并已从栈中弹出。

最初，所有顶点都标记为-1，因为它们都未被访问。

步骤1：首先，我们将访问顶点A并将其标记为0。由于节点A已被访问，因此它将被标记为0，并且节点A被推入栈中，如下所示

已访问集合包含节点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（创建环）