通过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: 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