拓扑排序

AOV网（Activity On Vertex NetWork）：用顶点表示活动，弧表示活动间的优先关系的有向图。

【问题描述】有 N 项活动，用AOV网表示出来，A→B指A必须在B之前完成。请输出一个合理的活动顺序。 AOV网中不能存在有向环。如果存在环，则无法拓扑排序。所以，拓扑排序可用来检查有向图中是否有环。

(1) DFS!  [邻接矩阵]

对于每个顶点，都先搜索并输出它的前趋。使用时调用topsort。

int vis[N];     // 结点访问情况：0表示未访问，1表示正在访问，2表示已访问。 int a[N], a_top;    // 结果保存在数组a中 bool DFS(int v) {  vis[v]=1;   for (int i=0; i<n; i++)   if (G[v]!=INF)    // 找到前趋   {    if (vis==1)    // 这个点进入两次，说明出现了环     return false;    else if (vis==0)     if (!DFS(i)) return false;   } // 处理点v  vis[v]=2;  a[a_top++]=v;  return true; }  bool topsort() {  memset(visited, 0, sizeof(visited));  a_top=0;   for (int i=0;i<n;i++)   if (!visited)     if (!DFS(i)) return false;  return true; }

(2) 模拟堆栈#  [邻接矩阵]

注意：下面代码不能把所有带环的情况都检查出来！

int cnt[N];     // cnt表示结点i的入度 int a[N], a_top;    // 结果保存在数组a中 bool topsort() {  int i, top = -1;  a_top=0; memset(cnt,0,sizeof(cnt));  for (i=0; i<n; i++)     if (cnt==0)   //  下标模拟堆栈    cnt = top, top = i;

for (i=0; i<n; i++)  if (top == -1)

   return false;    // 存在回路

  else

  {

   int j = top;    top = cnt[top];    a[a_top++]=j;    for (int k=0; k < n; ++k)      if (G[j][k] && ((--cnt[k]) == 0))      cnt[k] = top, top = k;

  }

return true;

}

(3) 使用辅助队列!  [邻接矩阵]

① 记录每个结点入度。

② 将入度为零的点加入队列。

③ 依次对入度为零的点进行删边操作，同时将新得到的入度为零的点加入队列。

④ 继续对队列中未进行操作的点进行操作。

queue<int> q; int cnt[N];     // cnt表示结点i的入度 int a[N], a_top;    // 结果保存在数组a中 bool topsort() { memset(cnt,0,sizeof(cnt)); // 记录每个结点的入度。 for (int i=0; i<n; i++)   for (int j=0; j<n; j++)    if (G[j]<INF) cnt[j]++; // 将入度为零的点加入队列。  for (int i=0;i<n;i++)   if (cnt==0) q.push(i);   while (!q.empty()) {   int i=q.front(); q.pop();   a[a_top++]=i;        // 记录结点   for (int j=0;j<n;j++)   {    if (G[j]<INF)    {     cnt[j]--;       // 依次对入度为零的点进行删边操作     if (cnt[j]==0) q.push(j);  // 将新得到的入度为零的点加入队列

  }

}

}

// 如果排序结束，但存在入度不为0的点，就说明有环。

for (int i=0;i<n;i++) if (cnt!=0) return false;

return true;        // 图中没有环

}