课程表

Note swift algorithm leetcode BFS

Word count: 874Reading time: 3 min

 2021/09/08 

Leetcode no.207课程表。初见以为思路是哈希表，后来以为是动态规划，最后发现原来是BFS…

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

需要注意的是，prerequisites数组给出的并不总是从0到numCourses-1的所有课程，可能会有一些课程不出现在该数组中，但这些课程是默认可以选修的。一开始思路的大滑坡就是因为没有理解这一点，解题前还是要理清题目再动手coding…

那么现在思路就明朗了。prerequisites是一个二维数组，我们使用一个二维数组来记录学完某一个课程，可以解锁的其他所有课程；另外再用一个一维数组，来记录学习某门课程总共需要学的先行课程的数量。
转化成图，便是一个有向图。当一个节点不存在环，即入度（学习该门课程所需要学的先行课程）为0时，该课程即可学习。即，在图中没有边指向该节点

显然，在prerequisites数组中没有出现过的0到numCourses-1中的课程，入度始终为0，这些课程便可以先学。同时我们并不关心他们学习的先后顺序。使用一个队列存储可以学习的课程，在课程的学习中再使其解锁的对应课程的入度减少1，即减去学习的课程跟解锁的课程中间的边。如果被解锁的课程入度为0，即代表该课程可以学习了，加入队列中。

当队列中不再有元素了，则学习结束，此时若学习的课程数小于numCourses，则无法学完全部课程。

以下为代码实现：

func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var arr = [[Int]](repeating: [], count: numCourses) // 第n门课学后就能学的课
        var indeg = [Int](repeating: 0, count: numCourses) // 第n门课要学前所需要学的课的数量
        for item in prerequisites {
            arr[item[1]].append(item[0])
            indeg[item[0]] += 1
        }
        var queue = [Int]()
        
        // 找到可以学习的节点
        for i in 0..<numCourses {
            if indeg[i] == 0 {
                queue.append(i)
            }
        }
        var res = 0
        
        while !queue.isEmpty {
            var first = queue.removeFirst() // 学了第first门课
            res += 1
            
            for aim in arr[first] { // 可以解锁的课程
                indeg[aim] -= 1
                if indeg[aim] == 0 {
                    queue.append(aim)
                }
            }
        }
        return res == numCourses
    }

BFS算法在此题的应用是通过图中一个可以学习的节点，找到与他有边相连的节点，并减去这条有向边（此条边指的是 学习i节点后即可学习j节点），直至访问完所有可学习的节点。

总结

这道题是BFS的一个综合应用，且题目描述比较隐晦，不像其他很明显是使用BFS的题。做题前还是要理清题目的关键信息，确定好解题的思路和方法再动手。

Next Post

App性能优化
Previous Post

一道经典的BFS

CATALOG

1. 总结