Go语言实现拓扑排序

package main

import (
	"fmt"
)

var (
	s       [][]int
	visited []bool
	p       []int
	Ind     []int
	count   int
)

func Init(n, m int) { //初始化
	var a, b int
	p = make([]int, 0, n)
	Ind = make([]int, n)

	for i := 0; i < n; i++ { //初始化访问数组
		visited = append(visited, false)
	}

	for i := 0; i < n; i++ {
		s1 := make([]int, 0, n)
		s = append(s, s1)
	}

	for i := 0; i < m; i++ {
		fmt.Scanln(&a, &b)
		s[a] = append(s[a], b)
		Ind[b]++
	}
}

func Topolopy_Sort(n int) bool { //拓扑排序
	count := 0
	var count1 int
	flag := true
	for {
		if count < n {
			count1 = count
			for i := 0; i < n; i++ {
				if visited[i] == false && Ind[i] == 0 {
					p = append(p, i)
					visited[i] = true
					count++
					fmt.Println(count)
					length := len(s[i])
					for j := 0; j < length; j++ {
						Ind[s[i][j]]--
					}
				}
			}
		} else {
			break
		}
		if count1 == count && count != n-1 {
			flag = false
			break
		}
	}

	return flag
}

func main() {
	var n, m int
	fmt.Println("请输入节点的个数和边数：")
	fmt.Scanln(&n, &m)
	Init(n, m)
	if Topolopy_Sort(n) {
		fmt.Println(p)
	} else {
		fmt.Println("Error")
	}

}

/*
6 8
0 1
0 2
1 3
2 4
1 4
2 3
3 5
4 5
*/

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/coolsunxu/article/details/78477414
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2019-10-27 00:00:04
阅读 ( 1021 )
分类：Go

Go语言实现拓扑排序

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看