FC12-使用拓扑排序判断有向图是否有环（邻接矩阵）¶

代码实现¶

C
// 函数 tpsort：使用拓扑排序判断有向图是否有环
// 参数：G - 图的邻接矩阵表示
bool tpsort(MGraph G) {
    // inres数组：存储每个顶点的入度
    int inres[maxsize] = {0};

    // st数组：用作栈，存储入度为0的顶点
    int st[G.numver];
    int top = -1;  // 栈顶指针，初始为空栈
    int n = 0;     // 记录已处理的顶点数

    // 步骤1：计算每个顶点的入度
    for (int i = 0; i < G.numver; i++) {
        for (int j = 0; j < G.numver; j++) {
            // 如果存在从顶点j到顶点i的边，则顶点i的入度加1
            if (G.Edge[j][i] != 0) {
                inres[i]++;
            }
        }
    }

    // 步骤2：将所有入度为0的顶点入栈
    for (int i = 0; i < G.numver; ++i) {
        if (inres[i] == 0) {
            st[++top] = i;  // 入度为0的顶点入栈
        }
    }

    // 步骤3：拓扑排序过程
    while (top != -1) {
        int v = st[top--];  // 弹出一个入度为0的顶点
        n++;                // 已处理顶点数加1

        // 遍历顶点v的所有邻接顶点
        for (int i = 0; i < G.numver; i++) {
            // 如果存在从v到i的边
            if (G.Edge[v][i] != 0) {
                // 将顶点i的入度减1
                inres[i]--;
                // 如果顶点i的入度变为0，则将其入栈
                if (inres[i] == 0) {
                    st[++top] = i;
                }
            }
        }
    }

    // 步骤4：判断是否有环
    if (n == G.numver) {
        return false;  // 所有顶点都被处理，无环
    } else {
        return true;   // 有顶点未被处理，存在环
    }
}

代码逻辑解析¶

1. 拓扑排序基本原理¶

有向无环图（DAG）：可以进行拓扑排序
有向有环图：无法进行拓扑排序
拓扑排序的核心思想：不断选择入度为0的顶点

2. 算法步骤详解¶

步骤1：计算入度¶

C
// 对每个顶点i，统计有多少条边指向它
for (int i = 0; i < G.numver; i++) {
    for (int j = 0; j < G.numver; j++) {
        if (G.Edge[j][i] != 0) {
            inres[i]++;  // 顶点j指向顶点i，i的入度加1
        }
    }
}

步骤2：初始化栈¶

C
// 将所有入度为0的顶点入栈，作为拓扑排序的起点
for (int i = 0; i < G.numver; ++i) {
    if (inres[i] == 0) {
        st[++top] = i;
    }
}

步骤3：拓扑排序主循环¶

C
while (top != -1) {
    int v = st[top--];  // 取出一个入度为0的顶点
    n++;                // 处理顶点数加1

    // 更新v的所有邻接顶点的入度
    for (int i = 0; i < G.numver; i++) {
        if (G.Edge[v][i] != 0) {
            inres[i]--;           // 删除边(v,i)，i的入度减1
            if (inres[i] == 0) {  // 如果i的入度变为0
                st[++top] = i;    // 将i入栈
            }
        }
    }
}

步骤4：环检测¶

C
// 如果所有顶点都被处理，说明图中无环
// 如果有顶点未被处理，说明图中存在环
if (n == G.numver) {
    return false;  // 无环
} else {
    return true;   // 有环
}

时间复杂度分析¶

1. 计算入度¶

外层循环：O(V)
内层循环：O(V)
总时间：O(V²)

2. 初始化栈¶

循环：O(V)

3. 拓扑排序主循环¶

每个顶点最多入栈和出栈一次：O(V)
对于每个顶点，遍历所有邻接顶点：O(V)
总时间：O(V²)

4. 总体时间复杂度¶

O(V²)，其中 V 是顶点数

空间复杂度分析¶

1. 额外数组空间¶

inres[]：O(V) - 存储入度
st[]：O(V) - 栈空间

2. 局部变量¶

常量级别的额外空间

3. 总体空间复杂度¶

O(V)

较难理解部分的说明¶

1. 为什么入度为0的顶点可以被处理？¶

在有向无环图中： - 入度为0的顶点表示没有其他顶点指向它 - 这样的顶点可以作为拓扑排序的起点 - 处理完这个顶点后，删除从它出发的所有边 - 这可能导致其他顶点的入度变为0

2. 图解说明¶

假设有一个有向图：

Text Only
1 2 3	`1 → 2 ↓ ↓ 3 → 4`

邻接矩阵表示：

Text Only
1 2 3 4 5	`1 2 3 4 1 0 1 1 0 2 0 0 0 1 3 0 0 0 1 4 0 0 0 0`

拓扑排序过程：

Text Only

初始状态：
入度：inres = [0, 1, 1, 2] (顶点编号0,1,2,3)
栈：st = [0] (只有顶点0入度为0)
n = 0

第1轮：处理顶点0
弹出顶点0，n = 1
更新邻接顶点：顶点1和2的入度各减1
入度：inres = [0, 0, 0, 2]
栈：st = [2, 1] (顶点1和2入度变为0)

第2轮：处理顶点1  
弹出顶点1，n = 2
更新邻接顶点：顶点4的入度减1
入度：inres = [0, 0, 0, 1]
栈：st = [2]

第3轮：处理顶点2
弹出顶点2，n = 3  
更新邻接顶点：顶点4的入度减1
入度：inres = [0, 0, 0, 0]
栈：st = [4] (顶点4入度变为0)

第4轮：处理顶点4
弹出顶点4，n = 4
无邻接顶点
栈：st = []

结束：n = 4 = G.numver，无环

3. 有环情况示例¶

假设有一个有环图：

Text Only
1 2 3	`1 → 2 → 3 ↑ ↓ └───────4`

拓扑排序过程：

Text Only

初始状态：
入度：inres = [1, 1, 1, 1] (所有顶点入度都为1)
栈：st = [] (没有入度为0的顶点)
n = 0

主循环无法执行，因为栈为空
结束：n = 0 ≠ G.numver，有环

延伸知识点¶

1. 邻接表优化版本¶

C
// 使用邻接表的优化版本，时间复杂度 O(V + E)
bool tpsortOptimized(ALGraph G) {
    vector<int> inDegree(G.numver, 0);
    queue<int> zeroInDegree;
    int processed = 0;

    // 计算入度
    for (int i = 0; i < G.numver; i++) {
        for (auto& edge : G.adjList[i]) {
            inDegree[edge.dest]++;
        }
    }

    // 入度为0的顶点入队
    for (int i = 0; i < G.numver; i++) {
        if (inDegree[i] == 0) {
            zeroInDegree.push(i);
        }
    }

    // 拓扑排序
    while (!zeroInDegree.empty()) {
        int u = zeroInDegree.front();
        zeroInDegree.pop();
        processed++;

        // 更新邻接顶点的入度
        for (auto& edge : G.adjList[u]) {
            int v = edge.dest;
            inDegree[v]--;
            if (inDegree[v] == 0) {
                zeroInDegree.push(v);
            }
        }
    }

    return (processed != G.numver); // true表示有环
}

2. DFS检测环¶

C
// 使用DFS检测有向图中的环
bool hasCycleDFS(MGraph G) {
    vector<int> color(G.numver, 0); // 0=未访问, 1=正在访问, 2=已完成

    function<bool(int)> dfs = [&](int u) -> bool {
        if (color[u] == 1) return true; // 发现后向边，有环
        if (color[u] == 2) return false; // 已完成的顶点

        color[u] = 1; // 标记为正在访问

        for (int v = 0; v < G.numver; v++) {
            if (G.Edge[u][v] != 0 && dfs(v)) {
                return true;
            }
        }

        color[u] = 2; // 标记为已完成
        return false;
    };

    for (int i = 0; i < G.numver; i++) {
        if (color[i] == 0 && dfs(i)) {
            return true; // 有环
        }
    }

    return false; // 无环
}

3. 实际应用场景¶

任务调度：检测任务依赖关系中是否存在循环依赖
课程安排：检测课程先修关系中是否存在冲突
软件工程：检测模块依赖关系中的循环依赖
编译系统：检测源文件包含关系中的循环包含
项目管理：检测项目任务间的循环依赖

4. 拓扑排序的其他应用¶

C
// 完整的拓扑排序结果输出
vector<int> topologicalSort(MGraph G) {
    // ... (与环检测相同的过程)
    vector<int> result;

    // 在处理每个顶点时将其加入结果
    while (top != -1) {
        int v = st[top--];
        result.push_back(v); // 添加到拓扑排序结果中

        for (int i = 0; i < G.numver; i++) {
            if (G.Edge[v][i] != 0 && (--inres[i] == 0)) {
                st[++top] = i;
            }
        }
    }

    if (result.size() == G.numver) {
        return result; // 返回拓扑排序结果
    } else {
        return {}; // 图中有环，无法进行拓扑排序
    }
}

这种方法体现了图论中环检测的经典思想，通过拓扑排序的可行性来判断图中是否存在环，是处理有向图问题的重要工具。