2021-04-24：手写代码：拓扑排序。

福大大 答案2021-04-24：

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
}

执行结果如下：

左神java代码