排课程

排课程

  Leetcode上有这样一道题，给定N个课程，但是有的课再学习之前，需要先学完别的某一个课程。就像我们在大学里面学专业之前要先学会高数才行。

  题目链接 https://leetcode.com/problems/course-schedule/，描述如下：

  There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

  Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

  Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

如上面的描述，给定课程数N，以及prerequisites [[0, 1]]，表示我们在学课程0之前要先把课程1学了，请我们计算最终是否能学完全部的课程。

整个问题梳理一下就是我们要先学一部分课程，然后再去学另一部分课程。但是存在一些特例，假如requisites=[[0, 1], [1, 0]]，第一个表示我们在学课程0之前要把课程1学完，第二个表示我们在学课程1之前把课程0学完。这样就形成了循环依赖，不能学完所有的课程。

  最初我的想法是构建链表，即利用链表构建每一个门课程之间的关系，但是链表是一一连接的，而课程之间可以存在一对多连接，比如学完课程1我可以学课程2 3，[[2,1],[3,1]]这种情况。因此我们就不能用链表来表示这种结构，后来看到网友的提示可以用图来表示。因此考虑用图来表示，我们将每一门课程表示一个顶点，若某课程B需要先学课程A才可以学，则在AB之间连接一条线，同时记录该课程B的连接数(出度)，我们要优先处理那些出度为0(不需要依赖其它课程)的课程，学完出度为0的课程之后，对于那些与其连接的课程出度要减一，表示我所依赖的课程数少了一个，若当前所依赖的课程为0，则将该课程加入待学的课程队列。最后，若仍然存在出度不为0的课程，表示不可以完成这些课，所所有的课程出度都为0，则可以完成这些课程。BFS的做法：

package main

import "fmt"

func canFinish(numCourses int, prerequisites [][]int) bool {
	if numCourses == 1 {
		return true
	}
	graph := make(map[int][]int, len(prerequisites)) // 建立图 
	in := make([]int, numCourses)  // 记录出度
	var queue []int
	for _, a := range prerequisites {
		graph[a[1]] = append(graph[a[1]], a[0]) // key为先学的课程
		in[a[0]]++
	}
	for i := 0; i < numCourses; i++ { // 出度为0的课程加入队列
		if in[i] == 0 {
			queue = append(queue, i)
		}
	}
	for len(queue) > 0 {
		front := queue[0]
		queue = queue[1:]
		for _, next := range graph[front] { // 与其相关课程的出度减一
			in[next]--
			if in[next] == 0 { // 若出度为0，加入队列
				queue = append(queue, next)
			}
		}
	}
	for _, pre := range in {
		if pre != 0 {
			return false
		}
	}
	return true
}

func main() {
	numCourses := 2
	prerequisite := [][]int{{1, 0}}
	fmt.Println(canFinish(numCourses, prerequisite))
}

此题还有一个延伸，若能学完所有的课程，返回课程的学习顺序。https://leetcode.com/problems/course-schedule-ii/，其实我们只需要在上面的for循环中，没出现一个出度为0的课程，将其加入到结果中即可

func findOrder(numCourses int, prerequisites [][]int) []int {
	if numCourses == 1 {
		return []int{0}
	}

	graph := make(map[int][]int, len(prerequisites))
	in := make([]int, numCourses)
	for _, pre := range prerequisites {
		graph[pre[1]] = append(graph[pre[1]], pre[0])
		in[pre[0]]++
	}

	var queue []int
	for i := 0; i < numCourses; i++ {
		if in[i] == 0 {
			queue = append(queue, i)
		}
	}
	var res []int
	for len(queue) > 0 {
		front := queue[0]
		queue = queue[1:]
		res = append(res, front) // 将课程编号加入到结果中
		for _, next := range graph[front] {
			in[next]--
			if in[next] == 0 {
				queue = append(queue, next)
			}
		}
	}

	if len(res) == numCourses {
		return res
	} else {
		return []int{}
	}
}

另外还有一种基于DFS的做法：

package main

import "fmt"

func findOrder1(numCourses int, prerequisites [][]int) []int {
	if numCourses == 1 {
		return []int{0}
	}

	graph := make(map[int][]int, len(prerequisites))
	for _, pre := range prerequisites {
		graph[pre[0]] = append(graph[pre[0]], pre[1]) // key为后学的课程
	}
	visited := make([]int, numCourses)
	var res []int
	for i := 0; i < numCourses; i++ {
		if !dfsFindOrder(graph, &visited, i, &res) {
			return []int{}
		}
	}
	return res
}

func dfsFindOrder(graph map[int][]int, visited *[]int, i int, res *[]int) bool {
	if (*visited)[i] == 0 {
		(*visited)[i] = 1
		for k := 0; k < len(graph[i]); k++ {
			if !dfsFindOrder(graph, visited, graph[i][k], res) {
				return false
			}
		}
		(*visited)[i] = 2
	} else if (*visited)[i] == 1 {
		return false
	} else {
		return true
	}
	*res = append(*res, i)
	return true
}

func main() {
	numCourse := 4
	prerequisites := [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}}
	fmt.Println(findOrder(numCourse, prerequisites))
	fmt.Println(findOrder1(numCourse, prerequisites))
}

上述的做法是基于DFS，首先还是建立一个图，然后利用visited记录每一个课程的状态，0:未学，1:正在学，2:学完。DFS的图和BFS的图不一样，graph中的key是不同的。在BFS中key是要先学的课程，DFS中的key是要后学的课程。DFS的做法，有一种倒序DFS的意思，即遍历每一门课程，若该课程的状态是0，则先置为1，然后去找它所依赖的其它课程，若依赖的课程为0，则置为1，继续向前找，找到所有依赖的课程都是未学，则表示这条路是可行的，至少没有循环依赖，则把这些课全部置为2已学。若先前着的过程中某个课是学完的，则表示这条路也是可行的，继续找其它分支的依赖的课程，若都是学完的，则把这条路经过的课程置为2已学。若向前找的过程中某个课程是正在学的，表示存在循环依赖，不可行，直接返回。