1）在图中找到所有入度为0的点输出。
2）把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始。
3）图的所有点都被删除后，依次输出的顺序就是拓扑排序。
要求：有向图且其中没有环。
应用：事件安排、编译顺序。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
matrix := [][]int{
{0, 1, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0}}
graph := NewGraph(matrix)
ret := sortedTopology(graph)
for i := 0; i < len(ret); i++ {
fmt.Print(ret[i].Val, "\t")
}
}
// directed graph and no loop
func sortedTopology(graph *Graph) []*Node {
// key 某个节点 value 剩余的入度
inMap := make(map[*Node]int)
// 只有剩余入度为0的点，才进入这个队列
zeroInQueue := make([]*Node, 0)
for _, node := range graph.Nodes {
inMap[node] = node.In
if node.In == 0 {
zeroInQueue = append(zeroInQueue, node)
}
}
result := make([]*Node, 0)
for len(zeroInQueue) > 0 {
cur := zeroInQueue[len(zeroInQueue)-1]
zeroInQueue = zeroInQueue[0 : len(zeroInQueue)-1]
result = append(result, cur)
for _, next := range cur.Nexts {
inMap[next] = inMap[next] - 1
if inMap[next] == 0 {
zeroInQueue = append(zeroInQueue, next)
}
}
}
return result
}
type Edge struct {
Weight int
From *Node
To *Node
}
// 点结构的描述
type Node struct {
Val int
In int
Out int
Nexts []*Node
Edges []*Edge
}
type Graph struct {
Nodes map[int]*Node
Edges map[*Edge]struct{}
}
//二维数组转成边
func NewGraph(matrix [][]int) *Graph {
graph := &Graph{}
graph.Nodes = make(map[int]*Node)
graph.Edges = make(map[*Edge]struct{})
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[0]); j++ {
// 拿到每一条边， matrix[i]
weight := matrix[i][j]
if weight > 0 {
from := i
to := j
if _, ok := graph.Nodes[from]; !ok {
graph.Nodes[from] = &Node{Val: from}
}
if _, ok := graph.Nodes[to]; !ok {
graph.Nodes[to] = &Node{Val: to}
}
fromNode := graph.Nodes[from]
toNode := graph.Nodes[to]
newEdge := &Edge{Weight: weight, From: fromNode, To: toNode}
fromNode.Nexts = append(fromNode.Nexts, toNode)
fromNode.Out++
toNode.In++
fromNode.Edges = append(fromNode.Edges, newEdge)
graph.Edges[newEdge] = struct{}{}
}
}
}
return graph
}执行结果如下：
