有向图成环判断——改进DFS实现

一、访问状态定义

• 未开始：**还未访问到**该结点。
• 未完成：相关的**后代正在被访问。**
• 已完成：所有后代结点**已经被访问完成**。

以上图为例，深度优先搜索顺序为：ABDHIEFG。刚完成对结点【I】的访问。**

• 【D】【H】【I】三个结点的所有后代都访问完成。状态为1。
• 【A】【B】结点还有可达的后代未访问完成。状态为-1。
• 【C】【E】【F】【G】结点还未开始访问。状态为0。

二、原始DFS过程与访问状态的结合

1. 原始DFS过程

1) 描述

当遍历到某个结点时，

• 首先访问该结点；
• 找到它指向的相关结点，逐个深度优先访问。

2) 部分代码

private void dfs(MyGraph g, int v) {
    // 访问并标记访问状态
    visit(g.getVertices()[v]);
    visited.put(g.getVertices()[v], VertexVisitStateEnum.VisitedOnce);
    // 对每个结点深度优先搜索
    // 获取【直接后代】列表
    for (Vertex<?> vertex : g.getRelatedVertices(v)) {
        if (VertexVisitStateEnum.Unvisited.equals(visited.get(g.getVertices()[vertex.getIndex()]))) {
            dfs(g, vertex.getIndex());
        }
    }
    visited.put(g.getVertices()[v], VertexVisitStateEnum.AllSubNodesVisited);
}

2. 与访问状态的结合

若某个结点后代未完成，但是通过后代指向了该状态的结点，则说明该有向图存在环。

1) 过程描述

改进遍历过程：

• 访问到了结点[I]，状态【未开始】
  • 更改状态**【未开始 ==> 未完成】**
  • 找到直接后代列表**[B, E]，逐个深度优先搜索。**

判断到【结点B】的状态【未完成**】：

• 对于【有向无环图】一个直接后代对象，初始状态一定是未开始。
• 【结点I】是B的直接或间接后代。
• 若通过直接或间接后代，找到了一个【未完成】的结点，那么，两个结点互为后代，一定存在环。

2) 部分代码

private void improvedDfs(MyGraph g, int v, Stack<Vertex<?>> visitStack) {
    Vertex<?> currentVertex = g.getVertices()[v];
    // 用于存：当前节点的所有流出节点的迭代
    Vertex<?> currentRelatedVertex;
    // 执行访问，则执行压栈，更新访问状态
    visit(currentVertex);
    visitStack.push(currentVertex);
    visited.put(currentVertex, VertexVisitStateEnum.VisitedOnce);
    // 获取到下标对应的顶点相连的顶点集合，对每个结点深度优先搜索
    for (Vertex<?> vertex : g.getRelatedVertices(v)) {
        currentRelatedVertex = g.getVertices()[vertex.getIndex()];
        // 判断到环
        if (VertexVisitStateEnum.VisitedOnce.equals(visited.get(currentRelatedVertex))) {
            visitStack.push(vertex);
            // 设置环路径访问栈，返回
            withCircle = new VisitStackAndCircle(true, visitStack);
            return;
        } else if (VertexVisitStateEnum.Unvisited.equals(visited.get(currentRelatedVertex))) {
            improvedDfs(g, vertex.getIndex(), visitStack);
        }
    }
    // 访问完毕，出栈
    visited.put(g.getVertices()[v], VertexVisitStateEnum.AllSubNodesVisited);
    visitStack.pop();
}