FC13-判断有向图的拓扑排序是否唯一（邻接矩阵）¶

代码实现¶

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

    // st数组：存储入度为0的顶点（栈结构）
    int st[G.numver];
    int top = -1;  // 栈顶指针，-1表示空栈
    int n = 0;     // 已处理的顶点数

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

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

    // 如果初始时有多个入度为0的顶点，说明拓扑排序不唯一
    if (top > 0) {
        return false;
    }

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

        // 更新与顶点v相邻的顶点的入度
        for (int i = 0; i < G.numver; i++) {
            if (G.Edge[v][i] != 0 && (--inres[i] == 0)) {
                st[++top] = i;  // 入度变为0的顶点入栈
            }
        }

        // 如果栈中有多个顶点，说明拓扑排序不唯一
        if (top > 0) {
            return false;
        }
    }

    // 步骤4：判断结果
    if (n == G.numver) {
        return true;   // 无环且拓扑排序唯一
    } else {
        return false;  // 有环（存在无法处理的顶点）
    }
}

代码逻辑解析¶

1. 拓扑排序唯一性的判断原理¶

唯一性条件：在拓扑排序的每一步中，入度为0的顶点都只有1个
不唯一情况：某一步中存在多个入度为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) {  // 存在边 j->i
            inres[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

    // 更新相邻顶点的入度
    for (int i = 0; i < G.numver; i++) {
        if (G.Edge[v][i] != 0) {  // 存在边 v->i
            inres[i]--;           // 顶点i入度减1
            if (inres[i] == 0) {  // 如果入度变为0
                st[++top] = i;    // 入栈
            }
        }
    }
}

步骤4：唯一性判断¶

C
// 关键判断：每一步栈中都只能有1个元素
if (top > 0) return false;  // 栈中有多个元素，不唯一

时间复杂度分析¶

1. 计算入度¶

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

2. 初始化栈¶

循环次数：O(V)
每次操作：O(1)
总时间：O(V)

3. 拓扑排序主循环¶

每个顶点被处理一次：O(V)
对每个顶点检查所有邻接顶点：O(V)
总时间：O(V²)

4. 总体时间复杂度¶

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

空间复杂度分析¶

1. 额外数组空间¶

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

2. 局部变量¶

常量级别的额外空间

3. 总体空间复杂度¶

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

较难理解部分的说明¶

1. 拓扑排序唯一性的核心判断¶

C
// 关键判断逻辑
if (top > 0) return false;

// 解释：
// top = -1：栈为空
// top = 0：栈中有一个元素
// top > 0：栈中有多个元素（拓扑排序不唯一）

图解说明：¶

唯一拓扑排序示例：

Text Only

有向图：1 -> 2 -> 3 -> 4

入度计算：
顶点1：入度 = 0
顶点2：入度 = 1
顶点3：入度 = 1  
顶点4：入度 = 1

拓扑排序过程：
步骤1：只有顶点1入度为0 → 唯一选择
步骤2：只有顶点2入度为0 → 唯一选择
步骤3：只有顶点3入度为0 → 唯一选择
步骤4：只有顶点4入度为0 → 唯一选择

结果：拓扑排序唯一：1, 2, 3, 4

不唯一拓扑排序示例：

Text Only

有向图：
1 -> 2
1 -> 3
2 -> 4
3 -> 4

入度计算：
顶点1：入度 = 0
顶点2：入度 = 1
顶点3：入度 = 1
顶点4：入度 = 2

拓扑排序过程：
步骤1：只有顶点1入度为0 → 唯一选择
步骤2：顶点2和顶点3入度都为0 → 可选择2或3（不唯一）

2. 算法正确性分析¶

为什么栈中元素个数能判断唯一性？¶

拓扑排序每一步都需要选择一个入度为0的顶点
如果某一步有多个入度为0的顶点，可以选择任意一个
这导致最终的拓扑排序结果不唯一

有环图的处理：¶

C
// 有环情况示例：1 -> 2 -> 3 -> 1
// 最终n = 0 < G.numver = 3
// 返回false，正确识别有环图

延伸知识点¶

1. 标准拓扑排序算法¶

C
// 标准拓扑排序（不判断唯一性）
bool standardTopSort(MGraph G, int result[]) {
    int inDegree[G.numver] = {0};
    int queue[G.numver], front = 0, rear = 0;
    int count = 0;

    // 计算入度
    for (int i = 0; i < G.numver; i++) {
        for (int j = 0; j < G.numver; j++) {
            if (G.Edge[j][i] != 0) {
                inDegree[i]++;
            }
        }
    }

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

    // 拓扑排序
    while (front < rear) {
        int v = queue[front++];
        result[count++] = v;

        for (int i = 0; i < G.numver; i++) {
            if (G.Edge[v][i] != 0 && (--inDegree[i] == 0)) {
                queue[rear++] = i;
            }
        }
    }

    return (count == G.numver); // 返回是否有环
}

2. 优化版本 - 邻接表存储¶

C
// 使用邻接表的优化版本，时间复杂度 O(V + E)
bool tpsortOptimized(ALGraph G) {
    int inDegree[G.numver] = {0};
    int stack[G.numver], top = -1;
    int processed = 0;

    // 计算入度（利用邻接表）
    for (int i = 0; i < G.numver; i++) {
        ArcNode* p = G.vertices[i].firstarc;
        while (p != NULL) {
            inDegree[p->adjvex]++;
            p = p->nextarc;
        }
    }

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

    if (top > 0) return false; // 初始不唯一

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

        ArcNode* p = G.vertices[v].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            if (--inDegree[w] == 0) {
                stack[++top] = w;
            }
            p = p->nextarc;
        }

        if (top > 0) return false; // 中间步骤不唯一
    }

    return (processed == G.numver);
}

3. 实际应用场景¶

任务调度：判断任务执行顺序是否唯一
编译依赖：判断模块编译顺序是否唯一
课程安排：判断课程学习路径是否唯一
项目管理：判断项目活动执行顺序是否唯一
数据处理：判断数据处理流程是否唯一

4. 相关算法问题¶

C
// 找出所有可能的拓扑排序
void findAllTopSort(MGraph G) {
    // 使用回溯法生成所有可能的拓扑排序
    // 当某一步有多个入度为0的顶点时，尝试每一种选择
}

// 最小字典序拓扑排序
vector<int> lexicographicTopSort(MGraph G) {
    // 使用优先队列（最小堆）总是选择编号最小的入度为0的顶点
    priority_queue<int, vector<int>, greater<int>> pq;
    // ... 实现略
}

5. 理论扩展¶

拓扑排序唯一性的充要条件： 1. 图是无环的（DAG） 2. 拓扑排序过程中每一步都只有一个入度为0的顶点

数学性质： - 唯一拓扑排序的图在某种意义上是"线性"的 - 可以通过图的结构特征来判断唯一性

这种方法体现了图论算法和贪心策略的结合，通过巧妙地利用拓扑排序过程中的状态来判断唯一性，是图论算法中的精巧设计。