拓扑排序主要用来解决有向图中的依赖解析（dependency resolution）问题
拓扑排序可以用来创建任务列表
用来检测有向图是不是有环
拓扑排序用到.png
上图如果要做B必须先A
从排序的角度就是A-B的顺序
网络路由是不是就这样啊
排序的有向图我们还是用https://www.jianshu.com/p/4d02b69e54e0这和里面的
有向图BFS用.png
从拓扑排序的原理来说顺序可以使0-1-2-3-4、0-1-3-2-4等等
首先放入的就是没有前向节点的0
0放入然后斩断与1、2、3的连接之后 这样1,2,3都可以插入了因为他们也没前向节点了1、2、3顺序无关
4必须在1、2、3之后
如何去做斩断操作呢？我们用一个数组记录所有节点的前项节点的个数比如
0-0
1-1
2-1
3-1
4-3
前面是key值后面是是个数
下面的代码和其他的文章有重复、主要为了避免去重复看另一个文章
队列的代码
// 队列
/*
队列的特性较为单一，基本操作即初始化、获取大小、添加元素、移除元素等。
最重要的特性就是满足先进先出
*/
type linkNode struct {
value MapParent
next *linkNode
}
type linkedList struct {
head *linkNode
tail *linkNode
count int
}
func NewLinkList() *linkedList {
return &linkedList{head: nil, tail: nil, count: 0}
}
func (this *linkedList) IsEmpty() bool {
return this.count == 0
}
func (this *linkedList) Add(value MapParent) {
node := new(linkNode)
node.value = value
this.count++
if this.tail == nil {
this.head = node
this.tail = node
node.next = nil
return
}
this.tail.next = node
node.next = nil
this.tail = node
}
func (this *linkedList) Delete() *linkNode {
if this.head == nil {
return nil
}
this.count--
if this.head == this.tail {
node := this.head
this.head = nil
this.tail = nil
return node
}
node := this.head
this.head = this.head.next
return node
}
type Queue struct {
link *linkedList
}
func NewQueue() *Queue {
return &Queue{link: NewLinkList()}
}
//加入队列
func (this *Queue) Put(value MapParent) {
this.link.Add(value)
}
//pop出队列
func (this *Queue) Pop() *linkNode {
return this.link.Delete()
}
//获得队列的长度
func (this *Queue) GetSize() int {
return this.link.count
}
func (this *Queue) IsEmpty() bool {
return this.GetSize() == 0
}
图的代码
package main
import (
"fmt"
"strconv"
)
// 逻辑不是很严谨 越界的没考虑-- scanf
// 边节点结构
type EdgeTableNode struct {
index int // 顶点索引
weight int // 权重
edgeTableNode *EdgeTableNode // 下一个临界点的指针
}
// 顶点的数据信息
type VertInfo struct {
value int
name string
}
// 顶点节点
type VertNode struct {
vertInfo VertInfo // 定点的数据信息
edgeTableNode *EdgeTableNode
}
type Graph struct {
vertNum int
grapType uint8
edgeNum int
hasCircle bool
allCircle [][]int
visted []int
vertNode []*VertNode
}
var arrayList []int
func NewGraph(vertNum int, edgeNum int, grapType uint8) *Graph {
return &Graph{vertNum: vertNum, hasCircle: false, allCircle: [][]int{},
visted: make([]int, vertNum), grapType: grapType,
edgeNum: edgeNum, vertNode: []*VertNode{}}
}
// 只做了有向图的初始化
// 没考虑无向图
func (this *Graph) InitGrap() {
// 顶点初始化
for i := 0; i < this.vertNum; i++ {
vert := &VertNode{}
vert.vertInfo.value = i
vert.vertInfo.name = "V" + strconv.Itoa(i)
fmt.Println(*vert)
this.vertNode = append(this.vertNode, vert)
}
// 边初始化
var startVert int
var endVert int
var weight int
var n int
for i := 0; i < this.edgeNum; i++ {
n, _ = fmt.Scanf("%d %d %d", &startVert, &endVert, &weight)
fmt.Printf("%d %d %d\n", startVert, endVert, n)
var edgeNode = this.vertNode[startVert].edgeTableNode
if edgeNode == nil {
tempNode := new(EdgeTableNode)
tempNode.weight = weight
tempNode.index = endVert
tempNode.edgeTableNode = nil
this.vertNode[startVert].edgeTableNode = tempNode
continue
}
for edgeNode != nil {
// 单链表尾插节点
if edgeNode.edgeTableNode == nil {
tempNode := new(EdgeTableNode)
tempNode.weight = weight
tempNode.index = endVert
tempNode.edgeTableNode = nil
edgeNode.edgeTableNode = tempNode
break
}
edgeNode = edgeNode.edgeTableNode
}
}
}
// 初始化队列
var queue *Queue = NewQueue()
type MapParent struct {
parent int
son int
}
// 拓扑排序
func (this *Graph) TuoPuSort() ([]int, bool) {
mapQianXIang := make(map[int]int)
sortList := []int{}
for i := 0; i < this.vertNum; i++ {
node := this.vertNode[i]
if node == nil {
continue
}
// 获取邻接链表
edgeNode := node.edgeTableNode
// 记录每个子节点的被指向的次数
for edgeNode != nil {
mapQianXIang[edgeNode.index]++
edgeNode = edgeNode.edgeTableNode
}
}
// 拓扑排序就是把没有前项节点的先放入队列中
for i := 0; i < this.vertNum; i++ {
if mapQianXIang[i] == 0 {
queue.Put(MapParent{parent: -1, son: i})
}
}
for !queue.IsEmpty() {
node := queue.Pop()
sortList = append(sortList, node.value.son)
// 获取邻接链表
edgeNode := this.vertNode[node.value.son].edgeTableNode
// 递减指向次数 其实就是斩断的过程
for edgeNode != nil {
mapQianXIang[edgeNode.index]--
if mapQianXIang[edgeNode.index] == 0 {
// 忽略parent 我们son
queue.Put(MapParent{parent: -1, son: edgeNode.index})
}
edgeNode = edgeNode.edgeTableNode
}
}
fmt.Println(sortList, " ", len(sortList) != this.vertNum)
// bool 表示有没有环
return sortList, len(sortList) != this.vertNum
}
func GrapTuoPuSort() {
var grap = NewGraph(5, 6, 1)
grap.InitGrap()
grap.TuoPuSort()
}
func main() {
//GrapDfs()
GrapTuoPuSort()
//GrapBfs()
}
时间复杂度： O(n + e)，其中n为图中的结点数目，e为图中的边的数目
空间复杂度：O(n)--队列的额外空间
