拓扑排序 c++代码原理详解
116 浏览量
2023-11-03
11:21:38
上传
评论
收藏 652KB PDF 举报
拓扑
排
序
有
向
⽆
环
图
⼀
定
是
拓扑
序
列
,
有
向
有
环
图
⼀
定
不
是
拓扑
序
列
。
⽆
向
图
没
有
拓扑
序
列
。
⾸
先
我
们
先
来
解
释
⼀下
什么
是有
向
⽆
环
图
：
有
向
就
是
我
们
两个
结
点
之
间
的
边
是有
⽅
向
的
，
⽆
环
的
意
思
就
是
整
个
序
列
中
没
有
⼏
个
结
点
通过边
形
成
⼀个
圆
环
。
下
图
就
是
⼀个
有
向
⽆
环
图
，
它
也
⼀
定
是
拓扑
序
列
。
下
图
就
是有
向
有
环
图
：
拓扑
序
列
：
⾸
先
我
们
引
⼊
度
的
概
念
：
对
于
有
向
图
每
个
结
点
都
有
⼊
度
和
出
度
，
⼊
度
就
是
指
向
该
结
点
的
边
数
，
出
度
就
是
该
结
点
指
向
其
他
结
点
的
边
数
。
如
第
⼀个
图
：
A
的
⼊
度
为
0
，
出
度
为
2
；
B
的
⼊
度
为
1
，
出
度
为
1
；
C
的
⼊
度
为
1
，
出
度
为
1
；
D
的
⼊
度
为
2
，
出
度
为
0
；
总
结
⼀下
拓扑
排
序
就
是
只
有
从
前
指
向后
的
边
，
没
有
从
后
指
向
前
的
边
。
如
果是
⼀个
有
向
⽆
环
图
，
那
么
⼀
定
有
⼀个
点
的
⼊
度
为
0
，
如
果
找
不
到
⼀个
⼊
度
为
0
的
点
，
这
个
图
⼀
定
是
带
环
的
。
拓扑
排
序
满
⾜
：
每
条
边
(x,y)
，
x
在
序
列
中
都
在
y
前
⾯
。
拓扑
排
序
的
思
路
：
⼀个
有
向
图
，
如
果
图
中
有
⼊
度
为
0
的
点
，
就
把
这
个
点
删
掉
，
同
时
也
删
掉
这
个
点
所
连
的
边
。
⼀
直
进
⾏
上
⾯
出
处
理
，
如
果
所
有
点
都
能
被
删
掉
，
则
这
个
图
可
以
进
⾏
拓扑
排
序
。
我
们
画
图
来
解
释
⼀下：
⾸
先
我
们
的
有
向
⽆
环
图
是
这
样
的
：
我
们
发
现
A
的
⼊
度
为
0
，
那
么
A
就
可
以作为
源
点
（不
会
有
边
在
它
前
⾯
），
然
后
删
除
A
和
A
上
所
连
的
边
，
如
下
图
：
资源评论
