拓扑排序[理论]

什么是拓扑序列
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：
若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。
设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。

比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。
注意：
①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
②若图中存在有向环，则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。
一般应用
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。
实现的基本方法
拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

拓扑序列 C++核心代码

bool TopologicalSort(int a[][101]) //可以完成拓扑排序则返回True
{
    int n = a[0][0], i, j;
    int into[101], ans[101];
    memset(into, 0, sizeof(into));
    memset(ans, 0, sizeof(ans));
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (a[i][j] > 0)//邻接矩阵
            into[j]++;//统计入度
        }
    }
    into[0] = 1;
    for (i = 1; i <= n; i++)
    {
        j = 0;
        while (into[j] != 0)//遍历,直到找到一个入度为零的点
        {
            j++;
            if (j > n)
                return false;
        }
        ans[i] = j;//该点已排序
        into[j] = -1;//删除该点
        for (int k = 1; k <= n; k++)
        {
            if (a[j][k] > 0)
            into[k]--;//删除与之相连的边进入的点的入度
        }
    }
    for (i = 1; i <= n; i++)
    {
        cout << ans[i] << " ";
    }
    cout << endl;
    return true;
}

补充：软件开发 , C++ ,