算法详解之拓扑排序
2020-12-13 04:48
标签:拓扑排序 完成 数组 依次 记录 int 访问 -- ++ ·(点的)度:对于无向图,和某个点相连的边条数 ·入度:对于有向图,终点是该点的边条数 ·出度:对于有向图,起点是该点的边条数 ·(两点间)路径:从起点点依次沿着边移动到下一个点,直到终点所经过的点和/或边若未有向图要求只能从边的起点移动到边的终点 ·圈:从一个点出发到自己的路径,常常被称作环 ·有向无环图(DAG):不含有环的有向图 ·和数组的排序没什么关系 ·对DAG的顶点进行排序,结果要求 每个顶点出现且仅出现一次 对于顶点对(u,v),若排序后u在v前,则不存在v到u的路径 ·可以理解为,能够到达某个顶点u的所有点都在u前面出现的一种访问顺序 ·一般是随着排序过程处理节点的信息,不需要显式得出结果 ·先在建图时记录每个点的入度 ·建立一个队列,把接下来需要访问的点加入队列 ·最开始时所有入度为0的点都可以访问,加入队列 ·依次从队列中取出每个点u,枚举其出边,边的终点设为v ·此处进行各种u->v的信息更新 ·因为u信息已经计算过了,相当于从图中删去u,将其v入度-1 ·此时v若入度为0则说明前置信息处理完成,加入队列 代码: 算法详解之拓扑排序 标签:拓扑排序 完成 数组 依次 记录 int 访问 -- ++ 原文地址:https://www.cnblogs.com/hulean/p/11123024.html名词解释
拓扑排序
算法流程
int ind[MAXN];
int d[MAXN];
int q[MAXN], qhead = 0, qtail = 0;
void topo() {
for (int i = 1; i