数据结构与算法总结——图

基本概念

• 图(Graph)：一组顶点和一组能够将两个顶点相连的边的集合
• 顶点(Vertex)：图中的数据元素。线性表中我们把数据元素叫元素，树中将数据元素叫结点
• 边(Edge)：两个顶点之间的连接
• 无向边：若一个顶点到另一个顶点之间的边没有方向，则称这条边为无向边
• 无向图：图中任意两个顶点之间的边都是无向边
• 有向边：若一个顶点到另一个顶点之间的边有方向，则称这条边为有向边，也称弧
• 有向图：图中任意两个顶点之间的边都是有向边
• 简单图：图中不存在顶点到其自身的边，且不存在重复边
• 无向完全图：无向图中，任意两个顶点之间都存在边
• 有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧
• 权：与图的边或弧相关的数据
• 网：带权的图
• 度：在无向图中，与某一顶点直接相连的变的数目；在有向图中，某个顶点的度是入度和出度的和
• 入度：在有向图中，表示其他顶点直接指向某个顶点的边的数目
• 出度：在有向图中，表示从某个顶点出发指向其他顶点的边的数目
• 路径：路径是由边顺序连接的一系列顶点
• 简单路径：一条没有重复顶点的路径
• 路径长度：一条路径上的边的数量
• 环：一条至少含有一条边且起点和终点相同的路径
• 简单环：一条（除了起点和终点必须相同之外）不含有重复顶点和边的环
• 自环：一条连接一个顶点和自身的边
• 平行边：连接同一对顶点的两条边
• 路径长度：路径所包含的边数
• 连通图：从任意一个顶点都存在一条路径到达另一个任意顶点的图
• 极大连通图：一幅非连通图的每个最大连通部分都是一幅极大连通图
• 无环图：不包含环的图
• 树：无环连通图
• 森林：互不相连的树组成的集合
• 生成树：连通图中包含所有顶点的一棵树
• 生成树森林：一幅图的所有连通子图的生成树的集合
• 密度：图中已经被连接的顶点对占所有可能被连接的顶点对的比例
• 稀疏图：被连接的顶点对比例很低的图
• 稠密图：被连接的顶点对比例很高的图
• 二分图：能够将所有顶点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同部分

树与图的关系

当且仅当一幅含有V个顶点的图G满足下列5个条件之一时，它就是一棵树：

1. G有V-1条边且不含环
2. G有V-1条边且是连通的
3. G是连通的，但删除任意一条边都会使得它不再连通
4. G是无环图，但添加任意一条边都会产生一条环
5. G中的任意一对顶点之间仅存在一条简单路径

图的表示方式

图在程序中的表示一般有三种方式：

邻接矩阵

• 使用一个VxV的数组作为矩阵
• 在无权图中，使用bool数组类型，矩阵坐标中每个位置值为true代表两个点是相连的，false表示两点是不相连的
• 在有权图中，使用int数组类型，矩阵坐标中每个位置值代表该两点之间的权重，0 表示该两点不相连
• 在无向图中，邻接矩阵关于对角线相等

邻接表

• 使用一个以顶点为索引的列表数组，数组中每个元素都是和该顶点相邻的顶点列表
• 在有权图中，仍然使用一个以顶点为索引的列表数组，但数组储存的是与该顶点直接连接的边，边的实例中带有边的权重大小

边的数组

• 使用一个边类，里面储存着两个顶点和边的权重
• 图只需要储存该图的所有边实例即可

邻接矩阵和邻接表的对比

• 邻接矩阵查找比较快，但是没有相连的边也占有空间，对于稀疏图会浪费大量空间，适合用于稠密图
• 邻接表对于查找某个点连接的边需要遍历，查找较慢，但不像邻接矩阵那样浪费内容，适合用于稀疏图
• 边的数组略微比链接表省空间，但是查找需要遍历每条边，比较耗时

总的来说，邻接表是一个比较广泛适用的方案，本文后续给出的实现都是基于这个方式

图的数据结构实现

public class Graph
{
    private int verts;
    private int edges;
    private LinkedList<int>[] adj;

    public Graph(int verts)
    {
        this.verts = verts;
        adj = new LinkedList<int>[verts];
        for (int i = 0; i < verts; i++)
        {
            adj[i] = new LinkedList<int>();
        }
    }

    public int Verts => verts;

    public int Edges => edges;

    /// <summary>
    /// 添加顶点v到顶点w的一条边
    /// </summary>
    /// <param name="v"></param>
    /// <param name="w"></param>
    public void AddEdge(int v, int w)
    {
        adj[v].AddLast(w);
        adj[w].AddLast(v);//有向图不需要这一行
        edges++;
    }

    /// <summary>
    /// 和v相邻的所有顶点
    /// </summary>
    /// <param name="v"></param>
    /// <returns></returns>
    public IEnumerable<int> Adj(int v)
    {
        return adj[v];
    }
}

1. 用链表数组表示一幅图，每个链表代表一个点，链表保存的是与该点直接相连的点
2. 对于有向图表示顶点v到顶点w连通，只需要在v链表添加w顶点即可。无向图因为边是两边连通的，添加顶点v到顶点w的一条边，需要对顶点v的链表插入顶点w，再对顶点w插入顶点v。
3. 获取和某个顶点相邻的所有顶点，返回该顶点的链表即可

图的遍历

深度优先搜索（DFS）

void DFS(int v)
{
    visited[v] = true;// bool[] vistied
    foreach (var item in graph.Adj(v))
    {
        if (!visited[item])
            DFS(item);
    }
}

visited是一个bool数组，记录所有顶点的访问状态，深度优先搜索过程如下：

1. 以图中其中一个顶点作为入口进行访问
2. 把访问到的顶点标记为已访问状态
3. 递归地访问这个顶点的未被标记为已访问状态的邻接顶点

如果图是连通的，那么遍历结束后每一个顶点都会被标记。

广度优先搜索（BFS）

void BFS(int v)
{
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(v);
    while (queue.Count > 0)
    {
        int w = queue.Dequeue();
        foreach (var item in graph.Adj(w))
        {
            if (!visited[item])// bool[] vistied
            {
                visited[item] = true;
                queue.Enqueue(w);
            }
        }
    }
}

visited是一个bool数组，记录所有顶点的访问状态，广度优先搜索过程如下：

1. 取图中其中一个顶点作为起点，加入队列
2. 取出队列的顶点，标记为已访问过
3. 把这个顶点的未被标记为已访问状态的邻接顶点加入队列
4. 重复2-3步骤直到整个队列为空

深度优先搜索和广度优先搜索的区别

如果把一幅图比如成一个迷宫，而DFS和BFS是两个人在迷宫中行走的话

• DFS每次碰到分支路口，就会按策略选择其中一个分支去走，直到走到这个分支的尽头，也就是最后访问到的顶点，已经没有未被访问过的邻接点时，会直接回退到上一个分支，再按策略选择第二条分支去走。
• BFS每次碰到分支路口，会“分身”成多个人，每个人各自走一条未被访问过的路

在实现上：

• DFS用栈（有人可能有疑问DFS哪里用到栈，其实是因为DFS递归实现本身借助了系统栈）
• BFS用队列

在应用上主要是以下区别：

• BFS更适合于求最优解问题。BFS第n步到达的点，其实就是达到该点的最少可能步数，BFS用在无权图在能直接求出最短路径。对于一些最优解问题，更适合用BFS，BFS找到最优解后可以提前结束，无需继续搜索。
• DFS更适合于求任意一个解、解的存在性问题。DFS在找到一个解时，他递归树访问经过的节点就是最终路径，BFS的访问则像雷达一样向四周所有可能路径进行扫描。

时间复杂度

-	邻接矩阵	邻接表
DFS	O(V^2^)	O(V+E)
BFS	O(V^2^)	O(V+E)

• V为图的顶点数，E为图的边数
• 从遍历完图的角度出发，DFS和BFS时间复杂度没有区别，只是访问节点的顺序有区别
• 时间复杂度与构建图的数据结构有关

图的可达性与路径搜索

基于深度优先搜索的实现

class DepthFirstPaths
{
    private Graph graph;//图
    private bool[] visited;//已访问过的顶点
    private int[] edgeTo;//回溯路径
    private int start;//起点
    //传入图和起点
    public DepthFirstPaths(Graph graph, int s)
    {
        this.graph = graph;
        this.start = s;
        visited = new bool[graph.Verts];
        edgeTo = new int[graph.Verts];
        DFS(s);//从起点开始DFS
    }

    private void DFS(int v)
    {
        visited[v] = true;
        foreach (var item in graph.Adj(v))
        {
            if (!visited[item])
            {
                edgeTo[item] = v;//记录回溯路径
                DFS(v);
            }
        }
    }
    //是否能从起点到达指定点
    public bool HasPathTo(int v)
    {
        return visited[v];
    }
    //起点到指定点的路径
    public IEnumerable<int> PathTo(int v)
    {
        if (!HasPathTo(v))
            return null;

        Stack<int> result = new Stack<int>();//回溯路径反转就是顺序路径
        for (int x = v; x != start; x = edgeTo[x])
        {
            result.Push(x);
        }
        result.Push(start);
        return result;
    }
}

基于广度优先搜索的实现

class BreathFirstPaths
{
    private Graph graph;//图
    private bool[] visited;//已访问过的顶点
    private int[] edgeTo;//回溯路径
    private int start;//起点
    //传入图和起点
    public BreathFirstPaths(Graph graph, int s)
    {
        this.graph = graph;
        visited = new bool[graph.Verts];
        edgeTo = new int[graph.Verts];
        this.start = s;
        BFS(s);//从起点开始BFS
    }

    private void BFS(int v)
    {
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(v);
        while (queue.Count > 0)
        {
            int w = queue.Dequeue();
            foreach (var item in graph.Adj(w))
            {
                if (!visited[item])
                {
                    visited[item] = true;
                    edgeTo[item] = w;//记录回溯路径
                    queue.Enqueue(w);
                }
            }
        }
    }
    //是否能从起点到达指定点
    public bool HasPathTo(int v)
    {
        return visited[v];
    }
    //起点到指定点的路径
    public IEnumerable<int> PathTo(int v)
    {
        Stack<int> result = new Stack<int>();
        for (int x = v; x != start; x = edgeTo[x])//回溯路径反转就是顺序路径
        {
            result.Push(x);
        }
        result.Push(start);
        return result;
    }
}

两者区别

广度优先搜索找到的路径是点与点之间的最短路径

二分图（二部图）

实现

class TwoColor
{
    private Graph graph;
    private bool[] marked;
    private bool[] colors;
    private bool isTwoColorGrap = true;

    public TwoColor(Graph g)
    {
        this.graph = g;
        marked = new bool[g.Verts];
        colors = new bool[g.Verts];
        for (int i = 0; i < g.Verts; i++)
        {
            if (!marked[i])
                DFS(i);
        }
    }

    private void DFS(int v)
    {
        marked[v] = true;

        foreach (var item in graph.Adj(v))
        {
            if (!marked[item])
            {
                colors[item] = !colors[v];//标记邻接点颜色是当前节点的反色
                DFS(item);
            }
            else if (colors[item] == colors[v])//如果邻接点已经访问过，且颜色和当前节点相同，则不是二分图
                isTwoColorGrap = false;
        }
    }
    //是否为二分图
    public bool IsTwoColorGraph()
    {
        return isTwoColorGrap;
    }

}

图的环问题

环是指一条至少含有一条边且起点和终点相同的路径

无向图是否存在环

class Cycle
{
    private Graph graph;
    private bool[] visited;
    private bool hasCycle;

    public Cycle(Graph g)
    {
        this.graph = g;
        visited = new bool[g.Verts];//已访问标记，大小为图的顶点数
        //考虑一个图有多个连通分量，需要对每个没访问到的点都分别进行DFS才能保证访问到所有顶点
        for (int i = 0; i < g.Verts; i++)
        {
            if (!visited[i])
                DFS(i, i);
        }

    }

    private void DFS(int v, int w)
    {
        //参数v是当前访问顶点，w是上一个访问顶点
        visited[v] = true;
        foreach (var item in graph.Adj(v))
        {
            if (!visited[item])
                DFS(item, v);
            else if (item != w)//如果一个顶点已经被访问过，且不是这个顶点不是上一个访问顶点，则有环
                hasCycle = true;
        }
    }

    public bool HasCycle()
    {
        return hasCycle;
    }
}

不考虑有自环和平行边

若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边)，则必定存在环

从树的角度很容易理解上面的代码，树就是一个无环图，而树的前中后序遍历就是DFS，我们从根节点开始进行DFS，对于树中任意一个节点，只与他的父节点以及他的子节点连通，基于DFS的回溯方式，实际上不会访问到父节点外的重复节点，若遇到已访问的节点且不是该点的“父节点”，则树不成立，而是一个有环图。

有向图是否存在环

class DirectedCycle
{
    private DiGraph diGraph;
    private bool[] visited;
    private int[] edgeTo;//edgeTo[v]=w表示w指向v，用于回溯路径
    private Stack<int> cycle;
    private bool[] onStack;//用于保存递归调用期间栈上的所有顶点

    public DirectedCycle(DiGraph g)
    {
        this.diGraph = g;
        visited = new bool[g.Verts];
        edgeTo = new int[g.Verts];
        onStack = new bool[g.Verts];
        for (int i = 0; i < g.Verts; i++)
        {
            DFS(i);
        }
    }

    private void DFS(int v)
    {
        visited[v] = true;
        onStack[v] = true;//进栈
        foreach (var item in diGraph.Adj(v))
        {
            if (HasCycle())//已有环就直接中断
                return;
            if (!visited[item])
            {
                edgeTo[item] = v;
                DFS(item);
            }
            else if (onStack[item])//如果某个顶点已被访问过，且已经处于调用栈上，则有环
            {
                cycle = new Stack<int>();//用一个stack保存环路径
                for (int x = v; x != item; x = edgeTo[x])//从进环前一个顶点，回溯入栈，直到进环后一个点
                {
                    cycle.Push(x);
                }
                cycle.Push(item);//环交点入栈
                cycle.Push(v);//
            }
        }
        onStack[v] = false;//出栈
    }

    public bool HasCycle()//是否有环
    {
        return cycle != null;
    }

    public IEnumerable<int> Cycle()//环路径
    {
        return cycle;
    }

}

有向图的环检测仍然是DFS，但与无向图的检测方式有略微的区别，举个简单的例子，对于A->B,A->C,C->B，如果按这个关系来构建无向图，这无疑是一个有环无向图，但如果是这样构建一个有向图，这却不是一个有环有向图，因为无论从A、B、C出发都不能回到自身，但如果套用无向图的DFS判断环方式却判断为有环，例如从A点开始DFS，会有A->B，A->C->B这样的访问路径，当前访问到C，而B是C的下一个邻接点，这时候B已经被访问过，但又不是C的上一个节点A，会被判定为有环。

对于有向图的环检测，我们在DFS的基础上添加一个bool数组来保存在递归调用期间栈上的所有顶点，若遇到一个顶点已被访问过而且还在调用栈上，则视为有环。这样的实现方式，在上面的例子中，先搜索A->B，此时A和B处于栈中，B由于没有邻接点，就回溯到A，此时B出栈，再搜索C->B，此时B虽然已经被访问过，但是之前已经出栈没有在栈中，所以不会被误判为有环。

上面代码还给出了获取环路径的实现。

应用

对于有向图的拓扑排序，必须经过环检测，只有无环的有向图能进行拓扑排序

有向图基于深度优先搜索的顶点排序

class DepthFirstOrder
{
    private DiGraph diGraph;//有向图
    private bool[] visited;
    private Queue<int> pre;//前序队列
    private Queue<int> post;//后续队列
    private Stack<int> reversePost;//逆后序栈

    public DepthFirstOrder(DiGraph g)
    {
        this.diGraph = g;
        visited = new bool[g.Verts];
        pre = new Queue<int>();
        post = new Queue<int>();
        reversePost = new Stack<int>();
        for (int i = 0; i < g.Verts; i++)
        {
            if (!visited[i])
                DFS(i);
        }
    }

    private void DFS(int v)
    {
        visited[v] = true;
        pre.Enqueue(v);//递归前入队，是前序
        foreach (var item in diGraph.Adj(v))
        {
            if (!visited[item])
                DFS(item);
        }
        post.Enqueue(v);//递归后入队，是前序
        reversePost.Push(v);//递归后入栈，利用栈反转，是逆后虚
    }
    //获取顶点的前序排列
    public IEnumerable<int> Pre()
    {
        return pre;
    }
    //获取顶点的后序排列
    public IEnumerable<int> Post()
    {
        return post;
    }
    //获取顶点的逆后序排列
    public IEnumerable<int> ReversePost()
    {
        return reversePost;
    }
}

此类允许用例用各种顺序遍历深度优先搜索经过的所有顶点，这在高级的有向图处理算法中非常有用，如拓扑排序、Kosaraju算法等。

拓扑排序

给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者说明无法做到这一点）。

当且仅当一幅有向图是无环图时，它才能进行拓扑排序

基于的深度优先搜索实现的拓扑排序

class Topological
{
    private IEnumerable<int> order;//拓扑排序序列

    public Topological(DiGraph g)
    {
        DirectedCycle directedCycle = new DirectedCycle(g);//有向图环检测
        if (!directedCycle.HasCycle())//如果没有环，就进行拓扑排序
        {
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(g);//基于DFS排序
            order = depthFirstOrder.ReversePost();//DFS的逆后序就是拓扑排序
        }
    }
    //获取拓扑排序序列
    public IEnumerable<int> Order()
    {
        return order;
    }
    //是否为有环有向图
    public bool IsDAG()
    {
        return order != null;
    }
}

上面代码利用到有向图的环检测以及有向图基于深度优先搜索的顶点排序的实现，在有向图无环的情况下，他的DFS的逆后序就是拓扑排序。

为什么DFS的逆后序就是拓扑排序

对于图中点A、B存在路径A->B，因为能进行拓扑排序的有向图是无环的，所以肯定不存在B->A的路径，逆序我们会先访问到B再访问到A，而逆后序便是A->B，也就是拓扑排序所要求的从排名较前的顶点是指向排名靠后的顶点的。

逆后序和前序有什么区别

例如图A->B-D,A->C-D,前序遍历结果是ABDC或ACDB，前序会从一个节点选择一个分支一直往深处访问，不会考虑他另外的分支也会访问到同一个点，显然拓扑顺序D应该在B和C之后，前序无法做到，而后序遍历结果则是DBCA或DCBA，会先访问最后的交汇点D，然后访问分支B、C，最后才回到出发点A，而后序倒过来就是ABCD或ACBD，显然是拓扑序列。

拓扑排序的应用

拓扑排序常常应用于任务有依赖优先级的调度问题，如课程安排，在学课程A之前，学生必须先学课程B，而课程B又有前置课程C，这些关系会形成一个图的结构，那么应该以一个怎么样的顺序去学习，就是拓扑排序所解决的问题。

图的连通性和连通分量以及顶点对可达性

无向图的连通性

无向图中，存在点v到点w的路径，我们称v和w是连通的。

class CC
{
    private Graph graph;
    private bool[] marked;
    private int[] id;
    private int count;

    public int Count => count;//连通分量的数量

    public CC(Graph g)
    {
        this.graph = g;
        marked = new bool[g.Verts];
        id = new int[g.Verts];
        for (int i = 0; i < graph.Verts; i++)
        {
            if (!marked[i])
            {
                DFS(i);
                count++;//连通分量计数
            }
        }
    }

    private void DFS(int v)
    {
        marked[v] = true;
        id[v] = count;//记录当前访问到的顶点的连通分量
        foreach (var item in graph.Adj(v))
        {
            if (!marked[item])
            {
                DFS(item);
            }
        }
    }

    //v与w是否连通
    public bool Connected(int v, int w)
    {
        return id[v] == id[w];//若点v与点w处于同一个连通分量中则连通
    }

    public int Id(int v)
    {
        return id[v];
    }
}

遍历图的所有顶点进行DFS，跳过已被标记的点，若该图只有一个连通分量，则在迭代第一个顶点进行DFS时就能遍历完所有顶点，若有顶点未被标记，则说明该顶点与上一次迭代的顶点不连通，此时count++，计算连通分量加一，重复上述步骤。在DFS过程中，count也代表了当前正在搜索的连通分量的id，用int数组保存每个顶点所处于的连通分量。

• 对于图中顶点v与顶点w是否连通问题，看他们所处于的连通分量是否相同
• 对于图有多少个连通分量，顶点v属于哪个连通分量，上文代码Count属性和Id方法能给出回答

有向图的强连通性

有向图中，存在点v和点w，它们之间是互相到达的，我们称v和w是强连通的。

有向图的反向图

public DiGraph Reverse()
{
    DiGraph diGraph = new DiGraph(verts);
    for (int i = 0; i < verts; i++)
    {
        foreach (var item in diGraph.Adj(i))
        {
            diGraph.AddEdge(item, i);
        }
    }

    return diGraph;
}

在解决有向图的强连通性问题之前，我们需要先构造一个反向图，邻接表的有向图结构，是用链表储存每个顶点的相邻顶点，表示这个顶点可以到达这些相邻顶点，而构造一个反向图只需要遍历所有顶点，用顶点的相邻顶点指向自己构成边来构造一个图即可。

Kosaraju算法

class KosarajuScc
{
    private DiGraph diGraph;
    private bool[] marked;
    private int[] id;
    private int count;

    public int Count => count;

    public KosarajuScc(DiGraph g)
    {
        this.diGraph = g;
        marked = new bool[g.Verts];
        DepthFirstOrder depthFirstOrder = new DepthFirstOrder(diGraph.Reverse());//构造原图的方向图
        foreach (var item in depthFirstOrder.ReversePost())//按照反向图的后逆序来进行DFS
        {
            DFS(item);
            count++;
        }
    }

    private void DFS(int v)
    {
        marked[v] = true;
        id[v] = count;
        foreach (var item in diGraph.Adj(v))
        {
            if (!marked[item])
                DFS(v);
        }
    }
    //v与w是否强连通
    public bool IsStronglyConnected(int v, int w)
    {
        return id[v] == id[w];
    }
}

上面代码DepthFirstOrder为有向图基于深度优先搜索的顶点排序中的实现

算法步骤：

1. 在给定的一幅有向图G中，使用DepthFirstOrder来计算它的反向图G^R^的逆后序排列。
2. 在G中进行标准的深度优先搜索，但是要按照刚才计算得到的顺序而非标准的顺序来访问所有未被标记的顶点。
3. 在构造方法中，所有在同一个递归DFS()调用中被访问到的顶点都在同一个强连通分量中，此部分与无向图的连通分量计算实现相同。

这个算法实现上很简单，但有点难以理解，为什么这么做得出的结果就是强连通的？
参考讲解：https://www.zhihu.com/question/58926821

关键是两点：

• 反向图可封死连通分量往外走的路
• 一个图的反向图有着和其相同的强连通分量划分情况

顶点对的可达性

在上文图的可达性与路径搜索给出了从固定某一个点出发，到图中任何一个点的可达性的实现方案，这个实现是要求其中一个顶点是固定的，不能解决检测任意两个顶点是否可达的需求，下文我们分无向图和有向图两种情况来讨论顶点对的可达性。

无向图的顶点对可达性

对于无向图，这个问题等价于无向图的连通性，上文实现中已经给出方案，Connected(v,w)可以检测v与w两个点是否可达。在经过线性级时间的预处理后，可以得到常数级的查询操作。

有向图的顶点对可达性

class TransitiveClosure
{
    private DirectedDFS[] all;
    private DiGraph diGraph;

    public TransitiveClosure(DiGraph g)
    {
        all = new DirectedDFS[g.Verts];
        for (int i = 0; i < g.Verts; i++)
        {
            all[i] = new DirectedDFS(g, i);
        }
    }

    public bool Reachable(int v, int w)
    {
        return all[v].Marked(w);
    }
}

上面代码是有向图的顶点对可达性的实现，实际上是每个顶点都做了一遍到任意顶点的可达性检测，时间复杂度:O(V(V+E))，空间复杂度:O(V^2^)，而无向图的顶点对可达性的时间复杂度:O(V+E)，空间复杂度:O(V)。性能相差非常远。据<<算法>>第四版的说法，能大幅度减少预处理所需的时间和空间同时又保证常数时间查询的算法，至今仍然是一个待解决的研究问题。

加权图

加权图是一种为每条边关联一个权值或是成本的模型。这种图能够自然地表示很多应用。在一幅航空图中，边表示航线，权值则可以表示距离或是费用。

加权无向图的实现

Edge

class Edge
{
    private double weight;//权重
    private int v;//边的一个点
    private int w;//边的另一个店

    public double Weight => weight;
    public int Either => v;//其中一个点


    public Edge(int v, int w, double weight)
    {
        this.v = v;
        this.w = w;
        this.weight = w;
    }
    //用这条边的一个点获取另一个点
    public int Other(int v)
    {
        if (v == this.v)
            return w;
        else if (v == w)
            return this.v;
        else
            throw new Exception("InConsisten edge");
    }
}

我们封装一个Edge类来表示无向图中的一条边，每个Edge对象包括两个顶点数据以及这条边的权重数据，当我们需要取其中一个点时，我们可以用Either属性取，当我们需要取另外一个点时，可以调用edge.Other(edge.Either)获取。

EdgeWeightedGraph

class EdgeWeightedGraph
{
    private int verts;
    private int edges;
    private LinkedList<Edge>[] adj;

    public int Verts => verts;

    public int Edges => edges;

    public EdgeWeightedGraph(int v)
    {
        this.verts = v;
        this.edges = 0;
        adj = new LinkedList<Edge>[v];
        for (int i = 0; i < v; i++)
        {
            adj[i] = new LinkedList<Edge>();
        }
    }


    public void AddEdge(int v, int w, double weight)
    {
        Edge edge = new Edge(v, w, weight);

        AddEdge(edge);
    }

    public void AddEdge(Edge edge)
    {
        int v = edge.Either;
        int w = edge.Other(v);

        adj[v].AddLast(edge);
        adj[w].AddLast(edge);

        edges++;
    }

    public IEnumerable<Edge> Adj(int v)
    {
        return adj[v];
    }

    public IEnumerable<Edge> GetAllEdges()
    {
        List<Edge> edges = new List<Edge>();
        foreach (var linkedList in adj)
        {
            foreach (var edge in linkedList)
            {
                edges.Add(edge);
            }
        }

        return edges;
    }

}

与无向图Graph大致上一样，原本用顶点索引的链表数组储存的是邻接点，现在储存的是邻接边。和不加权的无向图一样，如果一条边连接了顶点v和顶点w，那么它既会出现在v的链表也会出现在w的链表。

加权有向图的实现

DirectedEdge

class DirectedEdge
{
    private double weight;
    private int from;
    private int to;

    public double Weight => weight;
    public int From => from;
    public int To => to;

    public DirectedEdge(int v, int w, double weight)
    {
        this.from = v;
        this.to = w;
        this.weight = weight;
    }
}

加权有向图的边的类型实现比加权无向图的更为简单，因为对于无向图，我们需要提供Other方法，传入这条边的一个顶点来反向查询另一个顶点，有向图则不需要，因为有向图中的边单向的，不需要反向查询，from和to字段已经明确表明了他们的关系。

EdgeWeightedDiGraph

class EdgeWeightedDiGraph
{
    private int verts;
    private int edges;
    private LinkedList<DirectedEdge>[] adj;

    public int Verts => verts;

    public int Edges => edges;

    public EdgeWeightedDiGraph(int v)
    {
        this.verts = v;
        this.edges = 0;
        adj = new LinkedList<DirectedEdge>[v];
        for (int i = 0; i < v; i++)
        {
            adj[i] = new LinkedList<DirectedEdge>();
        }
    }

    public void AddEdge(int v, int w, double weight)
    {
        DirectedEdge directedEdge = new DirectedEdge(v, w, weight);
        AddEdge(directedEdge);
    }

    public void AddEdge(DirectedEdge edge)
    {
        adj[edge.From].AddLast(edge);
        edges++;
    }

    public IEnumerable<DirectedEdge> Adj(int v)
    {
        return adj[v];
    }

    public IEnumerable<DirectedEdge> GetEdges()
    {
        List<DirectedEdge> edges = new List<DirectedEdge>();
        foreach (var linkedList in adj)
        {
            foreach (var edge in linkedList)
            {
                edges.Add(edge);
            }
        }

        return edges;
    }
}

与加权无向图类似，主要区别在于，向图添加一条边时，不需要双向都添加，因为连接是单向的，只需要在起始点索引的链表添加即可。

最小生成树

• 图的生成树是它的一颗含有其所有顶点的无环连通之图。
• 一幅加权图的最小生成树是它的一棵圈子最小的生成树

计算最小生成树的基本算法有Prim算法、Kruskal算法

Prim算法

原理

1. 从连通图中一个点出发，访问与该点直接连接的所有的边，加到一个集合内
2. 在这个集合的所有的边里选出一条至少有一个顶点未加入树且权重最小的边，加入到树中
3. 每当我们把一条边加入到树中，也相当于把一个顶点加入到树中，从这个新加入的顶点出发重复步骤1、2
4. 直到把连通图的所有顶点加入到树时，这棵树就是这副连通图的最小生成树

Prim实际上是从一种从顶点出发，选择权重小的边添加到树中的贪心算法。

实现

class PrimMST
{
    private EdgeWeightedGraph graph;
    private Edge[] edgeTo;//某个点连接最小生成树的边
    private double[] distTo;//某个点到最小生成树的最短距离
    private bool[] marked;//标记某个顶点是否已加入树
    private MinIndexPriorityQueue<double> pq;

    public PrimMST(EdgeWeightedGraph g)
    {
        this.graph = g;
        edgeTo = new Edge[graph.Verts];
        distTo = new double[graph.Verts];
        marked = new bool[graph.Verts];
        pq = new MinIndexPriorityQueue<double>(graph.Verts);

        for (int i = 0; i < graph.Verts; i++)
        {
            distTo[i] = double.MaxValue;
        }

        distTo[0] = 0;
        pq.Insert(0, 0);
        while (!pq.IsEmpty)
        {
            Vist(pq.DelMin());//选一个权重最小的边加入树中，并从对应的顶点出发搜索未加入的边
        }

    }

    private void Vist(int v)
    {
        marked[v] = true;
        foreach (var edge in graph.Adj(v))
        {
            int w = edge.Other(v);
            if (marked[w])//v已经在树中，若w也在数中，那么这条边已经失效
                continue;
            //若边的权重比当前已记录的边的权重小，更新记录
            if (edge.Weight < distTo[w])
            {
                edgeTo[w] = edge;
                distTo[w] = edge.Weight;

                //若优先队列中已经保存了某个顶点到树的距离，更新即可，因为实际上只需要记录这个点到树的最短距离
                if (pq.Contains(w))
                    pq.Change(w, distTo[w]);
                else
                    pq.Insert(w, distTo[w]);

            }
        }
    }
    //获取最小生成树的所有边
    public IEnumerable<Edge> Edges()
    {
        List<Edge> mst = new List<Edge>();
        for (int v = 1; v < edgeTo.Length; v++)
        {
            mst.Add(edgeTo[v]);
        }
        return mst;
    }

}

Prim算法利用了优先队列来维护树外的顶点到树的距离最短的边，每次从一个顶点出发，访问与该点直接连接的所有边，对各个边的另一个点在已记录的距离树的最短路径进行对比，若当前访问的边比已该点已记录的距离更小，则更新数据，加入或更新到优先队列中（注意跳过两个点都已经在树中的边），最后在优先队列中选出一个权重最小的边加入到树中，再从新加入的顶点出发重复上述步骤。

复杂度

时间复杂度：O(ElogV)
空间复杂度：O(V)

Kruskal算法

原理

1. 从图中未被加入树所有边中选一条权重值最小的边
2. 判断这条边的两个顶点是否已经在树中，若在树中，跳过这条边，若不在，加入到树中
3. 当这棵树连接了所有顶点时，就是这幅连通图的最小生成树

实现

class KruskalMST
{
    private EdgeWeightedGraph graph;
    private Queue<Edge> mst;

    public KruskalMST(EdgeWeightedGraph g)
    {
        this.graph = g;
        mst = new Queue<Edge>();

        MinIndexPriorityQueue<Edge> pq = new MinIndexPriorityQueue<Edge>(g.Edges);

        foreach (var item in g.GetAllEdges())
        {
            pq.Insert((int)item.Weight, item);
        }

        UnionFind uf = new UnionFind(g.Verts);//借助并查集查询顶点是否已加入到树中

        while (!pq.IsEmpty && mst.Count < g.Verts - 1)
        {
            Edge edge = pq.Min();//取出权重最小的边
            pq.DelMin();
            int v = edge.Either;
            int w = edge.Other(v);
            if (uf.IsConnected(v, w))//如果边的两个顶点在并查集中连通，说明树已经包含了这两个顶点，再加入一条边的话会形成环
                continue;

            uf.Union(v, w);//把新加入的边的两个顶点，在并查集中标记为连通
            mst.Enqueue(edge);//把边加入最小生成树
        }

    }

    public IEnumerable<Edge> Edges()
    {
        return mst;
    }
}

Kruskal算法借助了优先队列以及并查集来实现，并查集用于记录处于树中的顶点的连通性，避免形成环。先把图的所有边加入到优先队列中，逐个取出权重最小的边，检测这个边的两个顶点是不是都在树中（并查集结果连通，代表在树中），如果是，跳过这条边，如果不是，就把这条边加入到树，并在并查集连通这条边的两个顶点，重复上述步骤，当树中边数e是图的顶点数v-1时，最小生成树现成。

复杂度

时间复杂度：O(ElogE)
空间复杂度：O(E)

Prim算法与Kruskal算法对比

• Prim算法从点出发，逐步构成最小生成树，生成的轨迹是一棵树逐渐成长延伸
• Kruskal算法一条边一条边地构造最小生成树，生成轨迹是不断把森林中的两棵树进行合并，直到最后剩下一棵树
• Prim算法更适合稠密图，Kruskal更适合稀疏图

Prim算法和Kruskal算法都仅能用于加权无向图，不能处理有向图

最短路径

松弛

在讲述最优路径算法前，我们想要理解一个松弛的概念和他的实现，下文所说的几种最短路径算法都离不开松弛这个操作。

什么是松弛

随着算法的执行，将起点到其他顶点的最短路径信息存入了edgeTo[]和distTo[]数组中。在遇到新的边时，通过更新这些信息就可以得到新的最短路径。当我们放松边v->w意味着从s到w的最短路径是否是先从s到v，然后再又v到w，如果是则根据这个情况更新数据结构的内容。对一条边放松一次我们就称为一次松弛操作。

边的松弛

private void Relax(DirectedEdge e)
{
    int v = e.From, w = e.To;
    if(distTo[w] > distTo[v] + e.Weight)
    {
        distTo[w] = distTo[v] + e.Weight;
        edgeTo[w] = e;
    }
}

上面代码实现了边的松弛操作，设起点为s

对一条边放松操作可能会产生两种情况：

1. 放松成功。distTo[w]代表了当前记录的s->w的最短路径，如果s->v->w路径权值小于已记录的distTo[w]，更新distTo[w]和edgeTo[w]数据，这个时候就有新的边加入，而原本的edgeTo[w]则会失效。
2. 边失效，与第一种情况相反，新访问的路径权值比已记录的权值大，则不做更新，且新的边会失效。

松弛这个术语来自于用一根橡皮筋沿着两个顶点的路径紧紧展开的比喻：放松一条边就类似于将橡皮筋转移到一条更短的路径上，从而缓解了橡皮筋的压力

点的松弛

private void Relax(int v)
{
    foreach (var edge in graph.Adj(v))
    {
        int w = edge.To;

        if (disTo[w] > disTo[v] + edge.Weight)
        {
            disTo[w] = disTo[v] + edge.Weight;
            edgeTo[w] = edge;
        }
    }
}

实际在我们的实现上，通常是对一个顶点的所有边进行放松，上面给出对点的松弛的实现。

通用最短路径算法

对于基于松弛的算法的可行性，我们只需要证明它们会放松所有的边直到所有边都失效即可。

Dijkstra算法

原理

1. 从图中一个点出发，访问与该点直接连接的所有的边，加到一个集合内
2. 在这个集合的所有的边里选出一条至少有一个顶点未加入树且距离起点路径最短的边(对点放松的过程)，加入到树中
3. 每当我们把一条边加入到树中，也相当于把一个顶点加入到树中，从这个新加入的顶点出发重复步骤1、2
4. 直到把图的所有非树顶点加入到树或所有非树顶点的距起点距离都是无穷大时，这棵树就是这副图的最短路径树

Dijkstra算法实现与Prim算法非常相似，都是通过每一步向一棵树中添加一条边，逐步构成最终的树，不同的是Prim算法选择的是距离树最短的边，而Dijkstra算法选择的是距离起点最短的边。

实现

class Dijkstracs
{
    private EdgeWeightedDiGraph graph;
    private DirectedEdge[] edgeTo;
    private double[] disTo;
    private MinIndexPriorityQueue<double> pq;

    public Dijkstracs(EdgeWeightedDiGraph g, int s)
    {
        this.graph = g;
        edgeTo = new DirectedEdge[g.Verts];
        disTo = new double[g.Verts];
        pq = new MinIndexPriorityQueue<double>(g.Verts);
        for (int i = 0; i < g.Verts; i++)
        {
            disTo[i] = double.PositiveInfinity;
        }

        disTo[s] = 0;
        pq.Insert(s, 0);
        while (!pq.IsEmpty)
        {
            Relax(pq.DelMin());
        }

    }

    private void Relax(int v)
    {
        foreach (var edge in graph.Adj(v))
        {
            int w = edge.To;

            if (disTo[w] > disTo[v] + edge.Weight)
            {
                disTo[w] = disTo[v] + edge.Weight;
                edgeTo[w] = edge;

                if (pq.Contains(w))
                    pq.Change(w, disTo[w]);
                else
                    pq.Insert(w, disTo[w]);
            }
        }
    }

    public double DisTo(int v)
    {
        return disTo[v];
    }

    public bool HasPathTo(int v)
    {
        return disTo[v] < double.PositiveInfinity;
    }

    public IEnumerable<DirectedEdge> PathTo(int v)
    {
        if (!HasPathTo(v))
            return null;

        Stack<DirectedEdge> result = new Stack<DirectedEdge>();
        for (DirectedEdge x = edgeTo[v]; x != null; x = edgeTo[x.From])
        {
            result.Push(x);
        }

        return result;
    }
}

适用范围

Dijkstra算法只适用于解决边权重非负的加权有向图最短路径问题。

Dijkstra算法对于已经加入了最短路径树的边是不再更新的，新出现的负值可能会使得顶点到起点的权值小于前面已经处理了的节点，这样得出来的结果就不对了。

复杂度

时间复杂度：O(ElogV)
空间复杂度：O(V)

与Prim算法相当

拓扑排序解决无环加权有向图的最短路径

原理

按照拓扑顺序去放松所有的顶点，能在线性时间里得到最短路径。

对于每条边v->w都只会被放松一次，当v被放松时，得到:distTo[w]<=distTo[v]+e.Weight。在算法结束前该不等式都成立，因为distTo[v]是不会变化的（因为按照拓扑顺序放松顶点，在v被放松之后算法不会再处理任何指向v的边）而distTo[w]只会变小（任何放松操作都只会减小distTo[]中的元素的值）。因此，当所有从起点可达的顶点都被加入到树中后，就是最短路径。

实现

class AcyclicSP
{
    private EdgeWeightedDiGraph graph;
    private DirectedEdge[] edgeTo;
    private double[] disTo;

    public AcyclicSP(EdgeWeightedDiGraph g, int s)
    {
        this.graph = g;
        edgeTo = new DirectedEdge[g.Verts];
        disTo = new double[g.Verts];

        for (int i = 0; i < g.Verts; i++)
        {
            disTo[i] = double.PositiveInfinity;
        }

        disTo[s] = 0;

        Topological topological = new Topological(g);
        foreach (var item in topological.Order())
        {
            Relax(item);
        }
    }

    private void Relax(int v)
    {
        foreach (var edge in graph.Adj(v))
        {
            int w = edge.To;
            if (disTo[w] > disTo[v] + edge.Weight)
            {
                disTo[w] = disTo[v] + edge.Weight;
                edgeTo[w] = edge;
            }
        }
    }
}

以上实现中的Topological类用到了上文基于的深度优先搜索实现的拓扑排序的实现

适用范围

对比起Dijkstra算法，基于拓扑顺序来放松顶点来求最短路径，能解决有向图的边的权值为负的情况，但要求图无环。

复杂度

时间复杂度：O(E+V)
空间复杂度：O(V)

Bellman-Ford算法

Bellman-Ford算法解决的问题

1. 负权重环的检测
2. 负权重环不可达时的单点最短路径

原理

在任意含有V个顶点的加权有向图中给定起点s，从s无法到达任何负权重环，以任意顺序放松有向图的所有边，重复V轮，便能得出单点最短路径。

基础实现

for(int pass = 0; pass < G.V(); pass++)
    for(v = 0; v < G.V(); v++)
        for(DirectedEdge e : G.adj(v)
            relax(e);

Bellman-Ford算法的暴力实现

基于队列的Bellman-Ford算法(SPFA)

class BellmanFordSP
{
    private EdgeWeightedDiGraph graph;
    private double[] distTo;
    private DirectedEdge[] edgeTo;
    private bool[] onQ;
    private Queue<int> queue;
    private int cost;
    private IEnumerable<int> cycle;

    public BellmanFordSP(EdgeWeightedDiGraph g, int s)
    {
        graph = g;
        distTo = new double[g.Verts];
        edgeTo = new DirectedEdge[g.Verts];
        onQ = new bool[g.Verts];
        queue = new Queue<int>();

        for (int i = 0; i < g.Verts; i++)
        {
            distTo[i] = double.PositiveInfinity;
        }

        distTo[s] = 0;
        queue.Enqueue(s);
        onQ[s] = true;
        while (queue.Count > 0 && !HasNegativeCycle())//若存在负权重环，退出循环
        {
            int v = queue.Dequeue();
            onQ[v] = false;
            Relax(v);
        }
    }

    private void Relax(int v)
    {
        foreach (var edge in graph.Adj(v))
        {
            int w = edge.To;
            if (distTo[w] > distTo[v] + edge.Weight)
            {
                distTo[w] = distTo[v] + edge.Weight;
                edgeTo[w] = edge;

                if (!onQ[w])
                {
                    queue.Enqueue(w);
                    onQ[w] = true;
                }
            }
        }

        if (cost++ % graph.Verts == 0)
            FindNegativeCycle();//每V次检测检测一次负权重环

    }
}

对于Bellman-Ford的暴力实现，复杂度非常高，很多时候我们是不能接受这样的成本的。

仔细分析不难发现，任意一轮中对许多边的放松都是不会成功的，能放松成功的边必定是与上一次放松成功的边相邻的边。所以我们可以用一个队列，让起始点入队，然后让起始点出队，放松与起始点相邻的顶点，更新放松成功的顶点的数据，并把放松成功的顶点加入队列，然后再从队列取出顶点重复上述步骤，注意这里还用一个bool数组onQ来维护某个顶点是否已经在队列中的状态，若已经在队列中，则不需要重复入队。以上优化将会大大降低算法的时间成本。

另外可以看到上面代码还有检测负权重环的逻辑，但没有给出具体实现，我们将会在下文讲述。

负权重环的检测

private void FindNegativeCycle()
{
    int v = edgeTo.Length;
    EdgeWeightedDiGraph g = new EdgeWeightedDiGraph(v);
    for (int i = 0; i < v; i++)
    {
        if (edgeTo[i] != null)
            g.AddEdge(edgeTo[i]);

        DirectedCycle directedCycle = new DirectedCycle(g);

        cycle = directedCycle.Cycle();
    }
}

public bool HasNegativeCycle()
{
    return cycle != null;
}

public IEnumerable<int> NegativeCycle()
{
    return cycle;
}

将所有边放松V轮之后当且仅当队列非空时有向图中才存在从起点可达的负权重环，如果是这样，edgeTo[]数组中说表示的子图必然含有这个负权重环，因此我们利用edgeTo[]中的边构造一幅加权有向图并在图中检测环。上面实现用到了上文有向图是否存在环中的代码DirectedCycle。

适用范围

可以检测负权重环，求最短路径要求从起点不能到达负权重环，最坏情况时间复杂度较高

应用

1. 相对最后期限限制下的并行任务调度问题：如果任务v必须在任务w启动后的d个时间单位内开始，则添加一条从v指向w的负权重为d的边。将所有边的权重取反即可将该问题转化为最短路径问题。
2. 检测任务调度问题是否存在可行方案：如第一点的相对最后期限限制下的并行任务调度问题，当存在负权重环时，可行方案不存在。负权重环在现实中存在的可能性较低，大多是来自于问题陈述错误导致的，找出负权重环，改正相应的错误，再去解决从起点不可达负权重环的最短路径问题。
3. 套汇问题：一个单位的货币A兑换成货币B再兑换成货币C，最后兑换回来货币A可能大于一个单位。汇率加权有向图中，负权重环的路径就是套汇有收益的路径。而在从起点出发没有负权重环时，求出的最短路径也是货币兑换的汇率最高兑换路径。

复杂度

一般时间复杂度：O(E+V)
最坏时间复杂度：O(EV)
空间复杂度：O(V)

Floyd算法

原理

Floyd实际上是动态规划思想，每一次循环更新经过前k个节点中，任意两点的最短距离。

实现

void Floyd(int n)
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = Math.Min(dist[i][j], dist[i][k] + dist[k][j]);
}

适用范围

不能存在负权重环，可求多源点最短路径问题

复杂度

时间复杂度：O(V^3^)
空间复杂度：O(V^2^)

总结

算法	局限	一般情况时间复杂度	最坏情况时间复杂度	空间复杂度	优势
Dijkstra算法(队列实现)	边的权重必须为正	O(ElogV)	O(ElogV)	O(V)	最坏情况下仍然有较好的性能
拓扑排序	只适用于无环加权有向图	O(E+V)	O(E+V)	O(V)	是无环图中的最优解法
Bellman-Ford算法(队列实现)	不能存在负权重环	O(V+E)	O(VE)	O(V)	使用领域广泛
Floyd	不能存在负权重环	O(V^3^)	O(V^3^)	O(V^2^)	可求多源点最短路径

关键路径

应用背景

优先级限制下的并行任务调度。给定一组需要完成的任务和每个任务所需的时间，以及一组关于任务完成的向后次序的优先级限制。在满足限制条件的前提下应该如何在若干相同的处理器上（数量不限）安排任务并在最短时间内完成所有任务？而决定着这一任务安排的最短时间的路径就是所谓的关键路径。

此问题与上文拓扑排序的应用类似，但拓扑排序解决的是只有单个处理器（同时只能处理一项）的情景。

最长路径

首先这类优先级调度问题必定是一个无环有向图，因为有环代表有互相依赖的任务，是不存在解的。在无环有向图中必定存在一个最长路径，而关键路径问题实际上等价于无环加权有向图的最长路径问题。由优先级限制指定的每一列任务都代表了调度方案的一种可能的时间下限。如果将一系列任务的长度定义为完成所有任务的最早可能时间，那么最长的任务序列就是问题的关键路径，因为这份任务序列中任何任务的启动延迟都会影响到整个项目的完成时间。

实现

class AcyclicLP
{
    private EdgeWeightedDiGraph graph;
    private DirectedEdge[] edgeTo;
    private double[] disTo;

    public AcyclicLP(EdgeWeightedDiGraph g, int s)
    {
        this.graph = g;
        edgeTo = new DirectedEdge[g.Verts];
        disTo = new double[g.Verts];

        for (int i = 0; i < g.Verts; i++)
        {
            disTo[i] = double.NegativeInfinity;
        }

        disTo[s] = 0;

        Topological topological = new Topological(g);
        foreach (var item in topological.Order())
        {
            Relax(item);
        }
    }

    private void Relax(int v)
    {
        foreach (var edge in graph.Adj(v))
        {
            int w = edge.To;
            if (disTo[w] < disTo[v] + edge.Weight)
            {
                disTo[w] = disTo[v] + edge.Weight;
                edgeTo[w] = edge;
            }
        }
    }
}

我们只需要对上文拓扑排序解决无环加权有向图的最短路径中实现的算法稍做修改，就可以从原本的求最短路径变成求最长路径，把disTo[]的初始值改成double.NegativeInfinity，并改变Relax()的不等式方向即可。

复杂度

时间复杂度：O(E+V)
空间复杂度：O(V)