做钓鱼网站论坛,哪个网站可以做医学基础知识题,部门网站建设和维护,网络营销的多种形式和特点拓扑序列
定义
是一个有向无环图#xff08;DAG, Directed Acyclic Graph#xff09;的所有顶点的线性序列。 且该序列必须满足下面两个条件#xff1a; 每个顶点出现且只出现一次。 若存在一条从顶点A 到顶点B 的路径#xff0c;那么在序列中顶点A 出现在顶点B 的前面。…拓扑序列
定义
是一个有向无环图DAG, Directed Acyclic Graph的所有顶点的线性序列。 且该序列必须满足下面两个条件 每个顶点出现且只出现一次。 若存在一条从顶点A 到顶点B 的路径那么在序列中顶点A 出现在顶点B 的前面。
并不是所有的图都存在拓扑序。有向无环图一定存在拓扑序有向无环图又被称为拓扑图。
基本概念
入度
一个点有多少条边指向自己
出度
由该点出发的有几条边
应用范围
有向无环图
作用
判断该图中有无环。
形成
只要有一个环就无法形成拓扑序因为环上每个点的入度都不为0。
有向无环图一定存在一个拓扑序有向无环图也被称为拓扑图。
一个有向无环图一定至少存在一个入度为0的点。
如何求拓扑序
构造算法思路
因为进行一个排序保证满足拓扑定义。而有向无环图中是一定有一个或多个点入度为0的这些点只可能在拓朴排序前面所以以他们中的一个为起点进行排序。
以某点为起始点的边的另一个节点在序列中只可能在该边起始点后面由于边与边之间可能会链接所以为保证拓扑序列的正确性每次将入度为0的点作为基点进行相关边的探查当存在边所关联的另一点只有这一条边的时候该点应该为拓扑序列的下一批点中的一个【上一批可能有多个点度为零】。所以进行拓扑序列的构造应该进行以下操作。
将所有入度为0的点入队列当队列非空时每次取出队列头元素top依次遍历所有以top为起始点的有向边。将对应边的另一点入度减一【表示去掉以t为起始点的这条边】将这些点中入度为0的点输出并加入队列。此时这些点已然在拓扑序列之中。之后做同样的操作。
所有入度为0的点【没有任何一条边指向该点】都可以作为起点都可以排在当前最前面的位置。
出队的顺序是拓扑序拓扑序可能不唯一。
实现
其实就是使用BFS
在使用邻接链表存储边时记录结束节点的入度。之后将入度为0的入队然后进行bfs。
每次记录队头后出队以队头为起点的边的终点的入度减1看能不能为0为零入队。以此类推
queue ——所有入度为0的点 将所有入度为0的点入队
//宽搜
while(queue 不空){
t—每一次取队头
枚举t的所有出边t—j
删掉t—jd[j]--(j的入度减1)
if(d[j]0){
queue ——j 将j入队
}
}
若存在环环上所有点的入度都不为0环上所有点都无法入队。
//主函数
//主函数输入所有边时要更新入度
for (int i 0;i m;i) {int a, b;cin a b;add(a, b);d[b];//更新入度}
//拓扑序函数
bool topsort() {int hh 0, tt -1;for (int i 1;i n;i) {//将所有入度为0的点入队if (!d[i])q[tt] i;}while (hh tt) {int t q[hh];//取队头for (int i h[t];i ! -1;i ne[i]) {//拓展队头int j e[i];d[j]--;if (d[j] 0) q[tt] j;}}return tt n - 1;//判断是否所有点都进入过队列如果ttn-1说明n个点全部进入过队列
}
//出队的顺序是拓扑序答案可能不一致
例题——有向图的拓扑序
给定一个n个点m条边的有向图图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列如果拓扑序列不存在则输出-1。
若一个由图中所有点构成的序列A满足对于图中的每条边(x, y)x在A中都出现在y之前则称A是该图的一个拓扑序列。
输入格式 第一行包含两个整数n和m
接下来m行每行包含两个整数x和y表示存在一条从点x到点y的有向边(x, y)。
输出格式 共一行如果存在拓扑序列则输出拓扑序列。
否则输出-1
数据范围
1≤n,m≤10^5
输入样例
3 3
1 2
2 3
1 3
输出样例
1 2 3
代码
#includeiostream
#includecstring
using namespace std;
const int N 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];//q是队列d是入度
void add(int a, int b) {e[idx] b;ne[idx] h[a];h[a] idx;
}
bool topsort() {int hh 0, tt -1;for (int i 1;i n;i) {if (!d[i])q[tt] i;}while (hh tt) {int t q[hh];for (int i h[t];i ! -1;i ne[i]) {int j e[i];d[j]--;if (d[j] 0) q[tt] j;}}return tt n - 1;//判断是否所有点都进入过队列如果ttn-1说明n个点全部进入过队列
}
int main() {cin n m;memset(h, -1, sizeof h);for (int i 0;i m;i) {int a, b;cin a b;add(a, b);d[b];//更新入度}if (topsort()) {for (int i 0;i n;i)printf(%d , q[i]);puts();}else puts(-1);
}
