【算法】拓扑排序
文章目录
- 有向无环图(`DAG`图)
- 顶点活动图(`AOV`网)
- 拓扑排序
- 实现拓扑排序
- 实现拓扑排序
- 建表
- 代码实现
- 拓扑排序
- 代码实现
有向无环图(DAG
图)
- 入度:有多少条边指向该节点
- 出度:该节点有多少边指向其它节点
- 有向:
- 无环:
顶点活动图(AOV
网)
在有向无环图中,用顶点来表示一个活动,用边来表示活动的先后顺序的图结构
这里我们举一个例子来解释:
如下就是一个青椒炒肉的炒菜流程:
找到做事情的先后顺序:
拓扑排序
找到做事情的先后顺序,拓扑排序的结果可能不是唯一的.
如何进行排序:
- 先找到入度为
0
的点,然后输出 - 删除与该点连接的边
- 重复
1
和2
的操作,直到图中没有点或者没有入度为0
的点为止注意:这里为什么还有一个入度为
0
的点的限定条件?
原因在于:我们的图不一定是一个有向无环图,在有向有环图中到最终的状态一定会存在没有入度为0
的点的情况存在.
所以:拓扑排序的重要应用就是判断有向图中是否有环
实现拓扑排序
借助队列,来一次BFS
-
初始化:把所有入度为
0
的点加入到队列中 -
当队列不为空的时候:
- 拿出队头元素,加到最终结果中
- 删除与该元素相连的边;
- 判断:与删除边相连的点,是否入度为
0
,如果入度为0
,加入到队列中 - 循环上述过程
实现拓扑排序
建表
这里我们使用邻接表来进行建表的工作.
邻接表:采用链表的形式,记录每一个与哪些节点相连.
举例说明:
实现该图的邻接表,就是:
那么我们如何使用代码,实现这个邻接表结构
- 可以使用的容器:
List<List<Integer>> edges
:Map<Integer,List<Integer>> edges
- 如何统计入度:
int[] in=new int[n]
代码实现
//1.准备工作int[] in=new int[n];//入度数组Map<Integer,List<Integer>> edges=new HashMap<>();//邻接表//2.建表for(int i=0;i<p.length;i++){//b->aint a=p[i][0],b=p[i][1];if(!edges.containsKey(b)){edges.put(b,new ArrayList<>());}edges.get(b).add(a);in[a]++;//入度+1}
拓扑排序
采用队列+bfs
形式进行拓扑排序
- 将入度为
0
的节点全部放入队列中 - 遍历队列,队列中的每一个节点,指向的入度为
0
节点,加入到队列中 - 最后遍历入度数组,如果入度数组中存在不为
0
的元素,那么就说明该图是一个有向有环图.
代码实现
//(2)bfswhile(!queue.isEmpty()){int t=queue.poll();//遍历该节点到达的所有节点for(int e:edges.getOrDefault(t,new ArrayList<>())){in[e]--;if(in[e]==0) queue.add(e);}}//(3)判断是否有环for(int i:in){if(i!=0) return false;}return true;