小编给大家分享一下leetcode中拓扑排序的示例分析，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！
创新互联公司IDC提供业务:成都移动机房托管,成都服务器租用,成都移动机房托管,重庆服务器租用等四川省内主机托管与主机租用业务;数据中心含:双线机房,BGP机房,电信机房,移动机房,联通机房。
本质上是一个top排序问题，top排序问题其实是有向图的遍历问题，因此可以dfs和bfs进行解。
选课问题
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
相关知识
通过 DFS 进行拓扑排序 - 一个关于 Coursera 的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
DFS解题思路：
1，将边缘列表转换成逆邻接矩阵的形式，
inverse_adj[i] 的slice表示，i的所有前缀节点
2，题目可以抽象为判断有向图是否可以拓扑排序（是否有环）
3，循环从每一个顶点开始深度优先遍历
A，当前节点标记为2（正在遍历）
B，如果该节点没有前缀节点（入度为0，则标记为1）
C，如果该节点有前缀节点，深度优先遍历
D，如果该节点的所有前缀节点都标记为1，则该节点标记为1
E，如果前缀节点中有正在遍历的节点（2），说明有环，返回。
func canFinish(numCourses int, prerequisites [][]int) bool { inverse_adj:=make([][]int,numCourses) for i:=0;i inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0]) } /* # 深度优先遍历，判断结点是否访问过 # 这里要设置 3 个状态 # 0 就对应 False ，表示结点没有访问过 # 1 就对应 True ，表示结点已经访问过，在深度优先遍历结束以后才置为 1 # 2 表示当前正在遍历的结点，如果在深度优先遍历的过程中， # 有遇到状态为 2 的结点，就表示这个图中存在环 */ nodes:=make([]int,numCourses) for i:=0;i //在遍历的过程中，如果发现有环，就退出 if DFS(i,inverse_adj,nodes){ return false } } return true}
func DFS(i int,inverse_adj [][]int,nodes []int)bool{ /* 注意：这个递归方法的返回值是返回是否有环 :param i: 结点的索引 :param inverse_adj: 逆邻接表，记录的是当前结点的前驱结点的集合 :param nodes: 记录了结点是否被访问过，2 表示当前正在 DFS 这个结点 :return: 是否有环 */ if nodes[i]==2{ // 2 表示这个结点正在访问,说明有环 return true } if nodes[i]==1{ return false } nodes[i]=2 for _,precursor:=range(inverse_adj[i]){ // 如果有环，就返回 True 表示有环 if DFS(precursor,inverse_adj,nodes){ return true } } // # 1 表示访问结束 nodes[i] = 1 return false}
BFS解题思路
解题思路：
对课程排序是，前一篇的递进，有向图的top排序，采用广度优先搜索（BFS）
首先将边缘列表转化成逆邻接矩阵，并记录每个前缀课程的入度
入度为0 的课程没有依赖，可以先上，放入队列
一次从队列中取节点
A. 放入返回数据
B. 将依赖此节点的所有邻接节点的入度减一（删除此节点后，邻接节点的依赖减少）
C. 将修正后入度为0 的节点放入队列
D. 循环直至队列为空
返回数据如果长度等于课程长度，说明没有环，否则有环
func findOrder(numCourses int, prerequisites [][]int) []int { inverse_adj:=make([][]int,numCourses) out_degree:=make([]int,numCourses) //入度 for i:=0;i //将边缘列表转换成逆邻接矩阵的形式 out_degree[prerequisites[i][0]]++ inverse_adj[prerequisites[i][1]]=append(inverse_adj[prerequisites[i][1]],prerequisites[i][0]) } r:=BFS(inverse_adj,out_degree) if len(r)==numCourses{ return r } return nil}
func BFS(inverse_adj [][]int,out_degree []int)(r []int){ var q queue for i:=0;i if out_degree[i]==0{ //入度为0，可以作为终点 q.push(i) } } for !q.empty(){ top:=q.pop() r=append([]int{top},r...) for _,precursor:=range(inverse_adj[top]){ //将当前节点移除，所有前驱节点的出度减1 out_degree[precursor]-- if out_degree[precursor]==0{ q.push(precursor) } } } return r}
type queue struct{ data []int}
func(q*queue)empty()bool{ return len(q.data)==0}
func(q*queue)push(i int){ q.data=append(q.data,i)}
func(q*queue)pop()int{ r:=q.data[len(q.data)-1] q.data=q.data[:len(q.data)-1] return r}
看完了这篇文章，相信你对“leetcode中拓扑排序的示例分析”有了一定的了解，如果想了解更多相关知识，欢迎关注创新互联行业资讯频道，感谢各位的阅读！
网页标题：leetcode中拓扑排序的示例分析
分享链接：
http://bzwzjz.com/article/jhejgj.html
