图论——拓扑序
<mark>什么是拓扑排序?</mark>
对一个有向无环图(Directed Acyclic Graph简称DAG) G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。
<mark>拓扑排序的实现步骤</mark>
在有向图中选一个没有前驱的顶点并且输出
从图中删除该顶点和所有以它为尾的弧(白话就是:删除所有和它有关的边)
重复上述两步,直至所有顶点输出,或者当前图中不存在无前驱的顶点为止,后者代表我们的有向图是有环的,因此,也可以通过拓扑排序来判断一个图是否有环。
如果我们又如下一个有向无环图那么我们该怎么实现拓扑排序呢?
首先我们找到入度为0的节点我们很容易就会发现入度为零的节点是1和6 如果这句话伤害了你请收下膝盖
我们随机输出一个入度为0的节点这里我们选择1;接下来我们删除入度为零 的节点的所有弧;
接下来我们继续重复上一操作得到如下
反复操作
继续
相信我就快结束了
真的呢
好了到这里我们的拓扑序就结束了呢
这里选用HDU 1285做模板例题
AC 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define V 510 //最大顶点数
int G[V][V]; //图
int degree[V]; //记录各顶点的入度
void topological_sort(int n) //拓扑排序函数
{
int i, j, k;
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
if(degree[j] == 0){ //找到入度为0的顶点
printf("%d", j); //输出
degree[j]--; //将其入度减为-1
k = j; //用k记录此顶点
break;
}
}
for(j = 1; j <= n; j++){
if(G[k][j] == 1){ //找到被此顶点打败过的顶点
G[k][j] = 0; //标记
degree[j]--; //将找到的顶点的入度减一
}
}
if(i != n)
printf(" ");
else
printf("\n");
}
}
int main(void)
{
int n; //队伍的个数
int m; //每组数据后接的输入行数
while(scanf("%d%d", &n, &m) != EOF){
memset(G, 0, sizeof(G)); //图的初始化
memset(degree, 0, sizeof(degree)); //顶点入度的初始化
while(m--){
int u, v;
scanf("%d%d", &u, &v); //u打败了v
if(G[u][v] == 0){
/*去重 这里要记录的是v被多少人打败过, 而不是被打败了多少次 */
G[u][v] = 1; //u打败过v
degree[v]++; //顶点v的入度加一
}
}
topological_sort(n); //调用拓扑排序函数
}
return 0;
}