golang 闭包实现拓扑排序

使用闭包实现拓扑排序

，考虑这样一个问题：给定一些计算机课程，每个课程都有前置课程，只有完成了前置课程才可以开始当前课程的学习；我们的目标是选择出一组课程，这组课程必须确保按顺序学习时，能全部被完成。每个课程的前置课程如下：

// prereqs记录了每个课程的前置课程
var prereqs = map[string][]string{
	"algorithms": {"data structures"},
	"calculus": {"linear algebra"},
	"compilers": {
		"data structures",
		"formal languages",
		"computer organization",
	},
	"data structures":       {"discrete math"},
	"databases":             {"data structures"},
	"discrete math":         {"intro to programming"},
	"formal languages":      {"discrete math"},
	"networks":              {"operating systems"},
	"operating systems":     {"data structures", "computer organization"},
	"programming languages": {"data structures", "computer organization"},
}

使用dfs，但是golang的dfs实现有点不一样，如果使用闭包的话。

import (
	"fmt"
	"sort"
)

func f(p map[string][]string) {
	for i,c :=range topoSort(p){
		fmt.Printf("%d:	%s
", i+1, c)
	}
}

//拓扑排序
func topoSort(m map[string][]string) []string  {
	var order []string
	visited := make(map[string]bool)

	//其实并没有运行，只是定义声明了visitAll函数而已
	var visitAll  func(items []string)
	visitAll = func(items []string){
		for _,item := range items{
			if !visited[item] {
				visited[item] = true
				visitAll(m[item])
				//递归入栈
				order = append(order,item)
			}
		}
	}

	//topo排序真正的流程
	var keys []string
	for key:=range m{
		keys = append(keys,key)
	}
	//保证输出顺序固定
	sort.Strings(keys)
	visitAll(keys)
	return order
}