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; // 图中没有环 }
|