leetcode中拓扑排序的示例分析

发布时间:2021-12-16 09:25:16 作者:小新
来源:亿速云 阅读:100

小编给大家分享一下leetcode中拓扑排序的示例分析,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!

本质上是一个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<len(prerequisites);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<numCourses;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<len(prerequisites);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<len(out_degree);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中拓扑排序的示例分析”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

推荐阅读:
  1. leetCode中回文数的示例分析
  2. LeetCode中两数之和的示例分析

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:如何解析K8s中的Etcd

下一篇:Linux sftp命令的用法是怎样的

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》