学习总结---拓扑排序

拓扑排序什么是拓扑序列
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：
若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。
设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。
比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。
注意：
①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
②若图中存在有向环，则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。

昨天花了一天的时间研究了下拓扑排序，觉得学到很多，所以写一下总结。

<1>有向图的表示方式可以分成邻接矩阵和邻接表两种。

邻接矩阵是指用一个n*n的数组，下标为i,j的位置记录点i和点j的关系。（适用与稀疏矩阵，对内存空间要求要比较高）

邻接表是单纯记录关系的数组，比如 i和 j 有关系，就将 j 放在 [i][k]的位置（k为当前与i有关系的点数），这种表示法适用于关系较少的时候，但是引用进STL中的vector以后，好像数据量的大小对其就没有什么太大的影响了。

<2>拓扑排序：每次找到入度为0 的点，并将其出度清空（可以用DFS或BFS），跟据表示的方法不同，操作也会有所差别。

<3>给出有向图之后，会有存在拓扑排序和不存在拓扑排序之分，如果图中存在有向环，则不存在拓扑排序（就是在遍历的过程中直接和间接的相互指向），在处理上只要记录每个点的访问状态就可以了，是正在访问（不满足的情况），还是未访问，或是已经访问过（DFS)。

如果存在了拓扑排序，也会有拓扑排序唯不唯一的问题（如果没有要求考虑这点，用DFS会号做一些），这点其实也好处理，只要每次入度为0的点只有一个才可以（BFS）。

DFS + 邻接表

DFS + 邻接矩阵。  
int vis[MAXN]; 
int topo[MAXN], cnt; 
bool DFS(int u){ 
    vis[u] = -1;    //表示当前正在访问，如果再次访问说明不存在topo排序。  
    for (int i = 0; i < n; i++){ 
        if (G[u][i]){ 
            if (vis[i] < 0) 
                return false;   //存在有向环，失败退出。  
            else if (!vis[i] && !DFS(i)) 
                return false; 
        } 
    } 
    vis[u] = 1; 
    topo[--cnt] = u; 
    return true;    // 成功记录，返回true 。  
} 
 
bool toposort(){ 
    cnt = n; 
    memset(vis, 0, sizeof(vis));    // 如果要考虑排序是否唯一，这边每次都需将所有点遍历过一遍，且每次只可有一点的入度为0。  
    for (int u = 0; u < n; u++) 
        if (!DFS(u)) 
            return false; 
    return true; 
} 

//  DFS + 邻接矩阵。
int vis[MAXN];
int topo[MAXN], cnt;
bool DFS(int u){
 vis[u] = -1; //表示当前正在访问，如果再次访问说明不存在topo排序。
 for (int i = 0; i < n; i++){
  if (G[u][i]){
   if (vis[i] < 0)
    return false; //存在有向环，失败退出。
   else if (!vis[i] && !DFS(i))
    return false;
  }
 }
 vis[u] = 1;
 topo[--cnt] = u;
 return true; // 成功记录，返回true 。
}

bool toposort(){
 cnt = n;
 memset(vis, 0, sizeof(vis)); // 如果要考虑排序是否唯一，这边每次都需将所有点遍历过一遍，且每次只可有一点的入度为0。
 for (int u = 0; u < n; u++)
  if (!DFS(u))
   return false;
 return true;
}BFS(借助STL-queue) + 邻接表（借助STL-vector)

// BFS + 邻接表。  
vector<int> G[MAXN];  // 邻接表。  
int son[MAXN];          // 入度数。  
 
void topo(){ 
    queue<int> que; 
    int ok = 0; 
    for (int i = 0; i < n; i++) 
        if (!son[i]) 
            que.push(i);    // 入度为0时入队。  
 
    while (!que.empty()){ 
        if (que.size() > 1) 
            ok = 1;         // 当队列中个数超多1时，表示有不唯一解。  
        int t = que.front(); 
        que.pop(); 
        cnt--;          //  如果队列为空后，计数器> 0， 说明存在环结构。  
        for (int i = 0; i < G[t].size(); i++) 
            if (--son[G[t][i]] == 0) // 判断减掉当前点的关系后，点的入度是否为0。  
                que.push(G[t][i]); 
    } 
}

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