拓扑排序

 我来答
一袭可爱风1718
2022-06-28 · TA获得超过1.2万个赞
知道大有可为答主
回答量:6413
采纳率:99%
帮助的人:35.8万
展开全部

对一个 有向无环图 (Directed Acyclic Graph简称 DAG )G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个 偏序 得到该集合上的一个 全序 ,这个操作称之为拓扑排序。

一个较大的工程往往被划分成许多子工程,工程之间相互存在依赖关系,比如工程A 、B、C,A工程开始依赖B完成, B开始又依赖C的完成,想要完成工程的话则需要按C->B-A顺序执行。
但是一旦增加 C依赖A 的条件后,则工程之间形成环形结构 C->B-A->C,导致无法完成。

拓扑排序可将有向图转换成线性有向图,以便直观的查看有向图是否存在环结构

入度 :一个顶点的入度是以这个顶点为 终点 的有向边的数量
出度 :一个顶点的入度是以这个顶点为 起点 的有向边的数量
例如:
A->B,B的入度+1,A的出度+1

若整个课程安排图是有向无环图(即可以安排),则所有节点一定都入队并出队过,即完成拓扑排序。换个角度说,若有向图中存在环,一定有节点的入度始终不为 0。
因此,拓扑排序出队次数等于节点个数,返回 num == 0 判断课程是否可以成功安排。

这里利用网上找到的一组图说明:

入度表遍历过程中,经常使用 邻接表 邻接矩阵 存储、任意两个顶点之间的连通关系,以便查找常数时间内找到当前节点对应的临界节点,以及当前节点和邻接节点之间的入度、出度数

借助一个标志列表 flags,用于判断每个节点 i (课程)的状态:

对 num个节点依次执行 DFS,判断每个节点起步 DFS 是否存在环,若存在环直接返回 False。DFS 流程;

具体案例可以参考这里: 课程表

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式