FC11-使用拓扑排序判断图中是否有环（邻接表）

代码实现

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

    // st数组：作为栈存储入度为0的顶点
    int st[maxsize];
    int top = -1;  // 栈顶指针，-1表示空栈
    int n = 0;     // 记录已处理的顶点数

    // 步骤1：计算每个顶点的入度
    for (int i = 0; i < G.numver; i++) {
        Node p = G.adjlist[i].firstarc; // 获取顶点i的第一个邻接点
        // 遍历顶点i的所有邻接点
        for (; p != NULL; p = p->nextarc) {
            inres[p->adjvex]++; // 增加邻接点的入度
        }
    }

    // 步骤2：将初始入度为0的顶点入栈
    for (int i = 0; i < G.numver; i++) {
        if (inres[i] == 0) { // 对于有向图，入度为0
            // if (inres[i] == 1) // 对于无向图，度数为1（注释部分）
            st[++top] = i; // 顶点i入栈
        }
    }

    // 步骤3：拓扑排序主循环
    while (top != -1) { // 当栈不为空时
        int v = st[top--]; // 弹出栈顶顶点
        n++; // 已处理顶点数加1

        // 遍历顶点v的所有邻接点
        Node p = G.adjlist[v].firstarc;
        for (; p != NULL; p = p->nextarc) {
            // 将邻接点的入度减1
            if (--inres[p->adjvex] == 0) { // 如果入度变为0
                // if (--inres[p->adjvex] == 1) // 对于无向图，度数为1（注释部分）
                st[++top] = p->adjvex; // 将该邻接点入栈
            }
        }
    }

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

---

代码逻辑解析

1. 拓扑排序基本原理

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

2. 算法步骤详解

步骤1：计算入度

// 遍历每个顶点的邻接表
for (int i = 0; i < G.numver; i++) {
    Node p = G.adjlist[i].firstarc;
    for (; p != NULL; p = p->nextarc) {
        inres[p->adjvex]++; // 被指向的顶点入度加1
    }
}

步骤2：初始化栈

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

步骤3：拓扑排序过程

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

    // 更新其邻接点的入度
    for (每个邻接点) {
        if (--入度 == 0) {
            入栈; // 新的入度为0的顶点入栈
        }
    }
}

步骤4：环检测

if (n == G.numver) {
    return false; // 成功处理所有顶点，无环
} else {
    return true;  // 有顶点未处理，存在环
}

---

时间复杂度分析

1. 计算入度阶段

• 遍历所有顶点：O(V)
• 遍历所有边：O(E)
• 总时间：O(V + E)

2. 初始化栈阶段

• 遍历所有顶点：O(V)

3. 拓扑排序阶段

• 每个顶点最多入栈和出栈一次：O(V)
• 每条边最多被处理一次：O(E)
• 总时间：O(V + E)

4. 总体时间复杂度

O(V + E)，其中 V 是顶点数，E 是边数

---

空间复杂度分析

1. 额外数组空间

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

2. 局部变量

• 常量级别的额外空间

3. 总体空间复杂度

O(V)

---

较难理解部分的说明

1. 有向图与无向图的区别

有向图：

• 使用入度概念
• 入度为0的顶点可以作为拓扑排序的起点

无向图：

• 使用度数概念（注释部分）
• 度数为1的顶点可以作为起点（类似于树的叶子节点）

2. 图解说明

有向无环图示例：

    1 → 2 → 3
    ↓   ↓
    4 → 5

邻接表表示：

顶点1: 2 → 4
顶点2: 3 → 5  
顶点3: 
顶点4: 5
顶点5:

入度计算：

inres[1]=0, inres[2]=1, inres[3]=1, inres[4]=1, inres[5]=2

拓扑排序过程：

初始：栈=[1], n=0
第1轮：处理1, 栈=[2,4], n=1
第2轮：处理2, 栈=[4,3,5], n=2
第3轮：处理4, 栈=[3,5], n=3
第4轮：处理3, 栈=[5], n=4
第5轮：处理5, 栈=[], n=5
结果：n=5=G.numver → 无环

有向有环图示例：

    1 → 2
    ↑   ↓
    4 ← 3

邻接表表示：

顶点1: 2
顶点2: 3
顶点3: 4
顶点4: 1

入度计算：

inres[1]=1, inres[2]=1, inres[3]=1, inres[4]=1

拓扑排序过程：

初始：栈=[], n=0
结果：n=0≠G.numver=4 → 有环

---

延伸知识点

1. 完整的拓扑排序算法

// 返回拓扑排序结果
int* topologicalSort(Graph G, int* resultSize) {
    int* result = (int*)malloc(G.numver * sizeof(int));
    int inres[maxsize] = {0};
    int st[maxsize], top = -1, n = 0;

    // 计算入度
    for (int i = 0; i < G.numver; i++) {
        Node p = G.adjlist[i].firstarc;
        for (; p != NULL; p = p->nextarc) {
            inres[p->adjvex]++;
        }
    }

    // 初始化栈
    for (int i = 0; i < G.numver; i++) {
        if (inres[i] == 0) {
            st[++top] = i;
        }
    }

    // 拓扑排序
    while (top != -1) {
        int v = st[top--];
        result[n++] = v;

        Node p = G.adjlist[v].firstarc;
        for (; p != NULL; p = p->nextarc) {
            if (--inres[p->adjvex] == 0) {
                st[++top] = p->adjvex;
            }
        }
    }

    if (n == G.numver) {
        *resultSize = n;
        return result; // 返回拓扑排序结果
    } else {
        free(result);
        *resultSize = 0;
        return NULL; // 存在环，无法拓扑排序
    }
}

2. DFS方法检测环

// 使用DFS检测有向图中的环
bool hasCycleDFS(Graph G) {
    int color[maxsize] = {0}; // 0=未访问, 1=正在访问, 2=已完成

    for (int i = 0; i < G.numver; i++) {
        if (color[i] == 0) {
            if (dfsVisit(G, i, color)) {
                return true; // 发现环
            }
        }
    }
    return false; // 无环
}

bool dfsVisit(Graph G, int u, int color[]) {
    color[u] = 1; // 标记为正在访问

    Node p = G.adjlist[u].firstarc;
    while (p != NULL) {
        int v = p->adjvex;
        if (color[v] == 1) {
            return true; // 发现后向边，存在环
        }
        if (color[v] == 0 && dfsVisit(G, v, color)) {
            return true; // 递归发现环
        }
        p = p->nextarc;
    }

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

3. 实际应用场景

• 任务调度：项目管理中的任务依赖关系
• 编译依赖：程序模块的编译顺序
• 课程安排：先修课程的依赖关系
• 数据处理：流水线作业的执行顺序
• 软件工程：模块间的依赖关系

4. 性能优化

// 使用队列优化的拓扑排序（Kahn算法）
bool tpsortOptimized(Graph G) {
    queue<int> q;
    int inres[maxsize] = {0};
    int n = 0;

    // 计算入度
    for (int i = 0; i < G.numver; i++) {
        Node p = G.adjlist[i].firstarc;
        while (p != NULL) {
            inres[p->adjvex]++;
            p = p->nextarc;
        }
    }

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

    // 拓扑排序
    while (!q.empty()) {
        int v = q.front(); q.pop();
        n++;

        Node p = G.adjlist[v].firstarc;
        while (p != NULL) {
            if (--inres[p->adjvex] == 0) {
                q.push(p->adjvex);
            }
            p = p->nextarc;
        }
    }

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

5. 相关图论算法

// 强连通分量检测（用于有向图）
void findSCC(Graph G) {
    // 使用Tarjan算法或Kosaraju算法
    // 可以找出图中的所有强连通分量
}

// 关键路径算法（AOE网络）
void criticalPath(Graph G) {
    // 在AOE网络中找出关键路径
    // 用于项目管理中的关键任务识别
}

这种方法体现了图论中经典算法的应用，通过入度的概念巧妙地检测图中是否存在环，是解决图相关问题的重要工具。