更多优质内容
请关注公众号

算法小白的入门日记(二二)图的排序——拓扑排序-张柏沛IT博客

正文内容

算法小白的入门日记(二二)图的排序——拓扑排序

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-23 18:52 浏览量:222
本系列文章目录
展开/收起

拓扑排序是针对有向无环图的一种广度优先遍历顶点的算法,可以将图中所有顶点按照要求的先后顺序排序。当然,拓扑排序本质不是一种排序算法,而是一种遍历图的算法。

在如果存在顶点 u 和顶点 v,要想到达顶点 v,则必须要到达顶点 u 。那么在拓扑排序中,顶点 u 必须处于顶点 v 的前面。


课程表的规划是拓扑排序的经典应用。


· 拓扑排序算法原理

图中的每个顶点都有入度和出度两个属性,入度是指该顶点被多少个顶点指向,出度指该顶点指向了多少个顶点。


1、创建一个队列,队列里存放所有入度为0的节点。

2、每次从队列中弹出一个节点A,记录为已访问。将A的未访问过的相邻节点的入度-1(但这些节点未访问),并将新的入度为0的节点放入队列。

3、重复步骤2,直到队列为空。


不能完成拓扑排序的情况:

1、如果初始状态下,所有节点的入度都为0,说明图中所有顶点都成环,无法完成拓扑排序;

2、如果队列为空后,图中仍存在未访问的节点,说明图中部分顶点成环,无法完成拓扑排序。


拓扑算法本质是广度优先遍历 + 贪心算法,假设最终解为res数组,存储拓扑排序后顶点的顺序。每一个局部最优解是入度为0的顶点,优先访问掉这些顶点放入res中,并生成新的入度为0的未访问顶点,再进入下一个局部状态。


代码实现如下:

// 拓扑排序, 参数是邻接表形式,要学习 g[i] 的课程,必须先学习 i
func KahnSort(g [][]int) []int{
	queue := list.New()		// 存储入度为0的队列
	level := make(map[int]int)	// 存储所有顶点的入度,可理解为学习某课程的难度
	visited := make(map[int]struct{})	// 存储所有已访问过的节点
	res := make([]int, 0, len(g))

	// 统计所有顶点的入度
	for vext, neibors := range(g){
		if _, ok := level[vext]; !ok{
			level[vext] = 0
		}
		for _, neibor := range(neibors){
			level[neibor] += 1
		}
	}

	for vext, lv := range(level){
		if lv == 0{
			queue.PushBack(vext)
		}
	}

	for queue.Len() > 0{
		node := queue.Front()
		queue.Remove(node)
		vext := node.Value.(int)

		visited[vext] = struct{}{}
		res = append(res, vext)
		for _, neibor := range(g[vext]){
			if _, ok := visited[neibor]; ok{
				continue
			}
			level[neibor]--		// 访问neibor顶点的困难-1
			if level[neibor] == 0{	// 如果访问neibor的难度为0则假如队列
				queue.PushBack(neibor)
			}
		}
	}

	// 判断是否存在还没有访问的顶点
	if len(visited) < len(g){
		return []int{}
	}
	return res
}


测试用例如下:


func TestKahnSort(t *testing.T){
	g := [][]int{
		{6,8},
		{3, 5},
		{5},
		{6},
		{6},
		{8},
		{8},
		{2,4,0},
		{},
		{1,2},
	}
	fmt.Println(KahnSort(g))  // [7 9 4 0 1 2 3 5 6 8]
}





更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(二二)图的排序——拓扑排序

热门推荐
推荐新闻