拓扑排序（C++实现）

拓扑排序过程：

①先将所有入度为0的节点加入队列。
②从队列中取出节点，将它加入到sortedOrder数组中，并将它的邻接节点的入度减1。
③如果某个邻接节点的入度减为0，则将其加入队列。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXV 6

typedef struct MGraph {                // 图的类型定义
    int numVertices, numEdges;  // 图的顶点数和有向边数
    char VerticesList[MAXV];    // 顶点表，MAXV已定义为常量
    int Edge[MAXV][MAXV];       // 邻接矩阵
};

bool topologicalSort(MGraph graph, vector<int>& sortedOrder)
{
    vector<int> inDegreeVec(graph.numVertices, 0);

    // 首先统计所有节点的入度
    for (int j = 0; j < graph.numVertices; j++) {
        for (int i = 0; i < graph.numVertices; i++) {
            if (graph.Edge[i][j] == 1) {
                inDegreeVec[j]++;  // 统计入度
            }
        }
    }

    // 找到入度为0的节点
    queue<int> que;
    for (int i = 0; i < graph.numVertices; i++) {
        if (inDegreeVec[i] == 0) {
            que.push(i);
        }
    }

    while (!que.empty()) {
        if (que.size() > 1) {
            // 拓扑排序的不唯一情况（如果需要的话处理）
        }

        int start = que.front();
        que.pop();
        sortedOrder.push_back(start);  // 将节点加入排序结果

        // 遍历当前节点的邻接节点
        for (int neighbor = 0; neighbor < graph.numVertices; neighbor++) {
            if (graph.Edge[start][neighbor] == 1) {                         // 如果存在从start到neighbor的边
                inDegreeVec[neighbor]--;                                    // 将邻接节点的入度减1
                if (inDegreeVec[neighbor] == 0) {
                    que.push(neighbor);                                     // 入度为0的节点加入队列
                }
            }
        }
    }

    // 判断是否存在环路
    if (sortedOrder.size() < graph.numVertices) {
        return false;
    }
    return true;
}

int main(int argc, const char* argv[])
{
    MGraph graph;
    graph.numVertices = 6;  // 6个节点
    graph.numEdges = 6;     // 6条边

    // 假设顶点为A, B, C, D, E, F
    graph.VerticesList[0] = 'A';
    graph.VerticesList[1] = 'B';
    graph.VerticesList[2] = 'C';
    graph.VerticesList[3] = 'D';
    graph.VerticesList[4] = 'E';
    graph.VerticesList[5] = 'F';

    // 初始化邻接矩阵
    for (int i = 0; i < graph.numVertices; i++) {
        for (int j = 0; j < graph.numVertices; j++) {
            graph.Edge[i][j] = 0;  // 没有边
        }
    }

    // 构建图的边
    // A -> D
    // F -> B
    // B -> D
    // F -> A
    // D -> C
    // E -> A
    graph.Edge[0][3] = 1;  // A -> D
    graph.Edge[5][1] = 1;  // F -> B
    graph.Edge[1][3] = 1;  // B -> D
    graph.Edge[5][0] = 1;  // F -> A
    graph.Edge[3][2] = 1;  // D -> C
    graph.Edge[4][0] = 1;  // E -> A

    vector<int> sortedOrder;
    bool res = topologicalSort(graph, sortedOrder);

    // 输出拓扑排序结果
    cout << "拓扑排序结果: ";
    for (int node : sortedOrder) {
        cout << (char)(node + 'A') << " ";  // 输出节点的字符表示
    }
    cout << endl;

    if (res) {
        cout << "拓扑排序成功!" << endl;
    }
    else {
        cout << "拓扑排序失败，图中存在环路。" << endl;
    }

    return 0;
}