6.md

图

1. Kruskal算法
2. Prim算法
3. Dijkstra算法
4. SPFA算法
5. Dinic算法

---

　　图是一种表示点与点之间关系的逻辑结构，链表和树都可以视为特殊的图。自然，我们也可以用类似的链式结构来表示图，从而使其存储结构与逻辑结构一致。可是，在很多时候，我们确实只是关心逻辑结构，故倾向于用数组来存储图。

邻接矩阵用N×N的二维数组表示任意两点间的边，通常还会专门设置一个特殊值表示边不存在的情况。

type AdjMatrix [][]uint     //邻接矩阵

　　对于边数不多的稀疏图而言，邻接矩阵太浪费空间，于是有了邻接表。邻接表也是个二维结构，但在第二维上只记录存在的边，从而节约了空间（也意味着更低的遍历开销）。

type Path struct {
    Next   int              //边的另一端
    Weight uint
}
type AdjList [][]Path       //邻接表（也可以用数组和链表的复合）

个别情况下，我们也会直接使用一维数组表示的边的集合：

type Edge struct {
    A, B   int              //边的两端
    Weight uint
}
type EdgeSet []Edge         //边集

有向无环图（DAG）

　　当一个有向图中没有环路时，可以从中抽取出一个序列，该序列中任意元素不依赖其后面的元素。抽取这个序列的过程称为拓扑排序。

func TopologicalSort(roads [][]int) ([]int, error) {
    size := len(roads)
    list := make([]int, 0, size)
    book := make([]int, size)
    for i := 0; i < size; i++ {
        for _, next := range roads[i] {
            book[next]++                //标记存在几个上游
    }   }
    free := deque.NewQueue[int]()
    for i := 0; i < size; i++ {
        if book[i] == 0 {
            free.Push(i)                //最上游点
    }   }
    for !free.IsEmpty() {
        curr := free.Pop()
        for _, next := range roads[curr] {
            book[next]--
            if book[next] == 0 {
                free.Push(next)
        }   }
        list = append(list, curr)
    }
    if len(list) != size { return nil, errors.New("loops exist") }
    return list, nil
}

最小生成树问题

　　树是一种特殊的图，它的特殊之处在于用最少的边连通了所有的点。无向连通图中，显然能找到一棵或多棵包含所有点的树（即图的生成树），最小生成树问题就是要找到其中边权重之和最小的一棵。
　　在这个问题上，我们将讨论Kruskal算法和Prim算法。

最短路径问题

　　顾名思义，最短路径问题是寻找点与点之间，边权重之和最小的路径。
　　在这个问题上，我们将讨论Dijkstra算法和SPFA算法。

最大流问题

　　前面两个问题把边的权重看作可累加量（如距离），而在管道网络图中，边的权重往往表示流量上限。最大流问题，就是要分析管道网络中，点与点之间流量的上限。
　　在这个问题上，我们将讨论基于Ford-Fulkerson方法的Dinic算法。

---

返回　下一章　下一节