欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

通过LeetCode 210课程表 II学习图

程序员文章站 2022-06-22 16:38:15
通过LeetCode 210课程表 II学习图用python实现图python的图可以通过dict很简单的实现, 例如下面这张图可以这样表示:Map = {}Map['s'] = ['a', 'd']Map['a'] = ['s', 'c', 'b']Map['b'] = ['a', 't']···这样可以很轻易的知道每个元素相连的元素代码实现class Solution: def findOrder(self, numCourses: int, prerequisites...

通过LeetCode 210课程表 II学习图

用python实现图

python的图可以通过dict很简单的实现, 例如下面这张图
通过LeetCode 210课程表 II学习图
可以这样表示:

Map = {}
Map['s'] = ['a', 'd']
Map['a'] = ['s', 'c', 'b']
Map['b'] = ['a', 't']
···

这样可以很轻易的知道每个元素相连的元素

代码实现

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        #制图
        l = {}
        for i in prerequisites:
            if i[0] in l:
                l[i[0]].append(i[1])
            else:
                l[i[0]] = [i[1]]

		#判断是否有重复
        T= True
        def check(ed, n):
            global T
            if n in l:
                for i in l[n]:
                    if i in ed:
                        T=False
                        return
                    else:
                        check(ed+[n], i)
    
        for i in range(numCourses):
            check([], i)
        if not T:
            return []

		#得到一个排序
        already = {}
        rl = []    
        def get_next_lesson(n):
            if n in already:
                return
            if n in l:
                for i in l[n]:
                    get_next_lesson(i)
            rl.append(n)
            already[n] = 1

        for i in range(numCourses):
            get_next_lesson(i)

        return rl

运用图的时候要注意:
1.查找过的元素不需要使用第二次
2.使用前先确定这个元素是否存在
这其实概括了dict的作用:查找重复, 缓存, 映射

其实我感觉check和get_next_lesson可以合在一起,而且纯深度优先算法感觉也不太好

本文地址:https://blog.csdn.net/albert_fifth/article/details/110491395