前置芝士
BFS ,别告诉我连这个都不会。
算法介绍
定义
数学上的:
将DAG中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。
通俗一点:
用宽搜一层层把图切开。
前提:图是一个DAG(有向无环图)
解决什么问题
假设有一些工作,完成某个工作的前提需要完成另某个工作,称为准备工作,至少一个工作不需要任何准备工作,至少一个工作不是任何工作的准备工作。
表示这种关系的图称为AOV网。用topo排序解决此类问题。
算法思路
文字思路
将入度为0的点扔进队 遍历这些点,将每个点所连的边炸掉,相当于所通向的点入度-1 如果发现有点入度变为0则扔进队 队列为空,算法结束,每次从队中取出元素的顺序就是一个合法的拓扑序伪代码展示
int n; vector<int>gragh[maxn]; int in[maxn]; for(int i=1;i<=n;i++){ if(!in[i])q.push(i); } while(!q.empty()){ int now=q.front();q.pop(); printf("%d\n",now); for(int i=0;i<gragh[now].size();i++){ in[gragh[now][i]]--; if(!in[gragh[now][i]]){ q.push(gragh[now][i]); } } }
声明:本文来自网络,不代表【好得很程序员自学网】立场,转载请注明出处:http://www.haodehen.cn/did238134