这里介绍了图论中常见算法的原理和实现。

一、邻接表存图

用邻接矩阵表示稀疏图会浪费大量内存空间。而在邻接表中是通过把类似于“从顶点0出发有到顶点1、2、3、4的边”这样的信息保存在链表中来表示图的。这样只需要$O(|V| + |E|)$的内存空间。

#include <cstdio>
#include <vector>
std::vector<int> g[max_v];
/**
 *边上有属性的情况 
 *sturct edge
 *{
 *    int to, cost;
 *};
 *std::vector<edge> g[max_v];
 */
int main(void)
{
    int v, e;
    scanf("%d%d", &v, &e);
    for(int i = 0; i != e; ++i)
    {
        int s, t;
        scanf("%d%d", &s, &t);
        g[s].push_back(t);
        //g[t].push_back(s);//无向图的情况 
    }
    return 0;
}

二、最短路问题

1.Bellman-Ford求单源最短路

记从起点$s$出发到顶点$i$的最短距离为$d_i$，对于图中有圈的情况，设$d_s=0, d_i=\infty $则可以在有限次数内算出新的$d$。只要不存在从$s$可达到的负圈，最多在$|V| - 1$次循环后for(;;)就会break，因此复杂度是$O(|V| × |E|)$。也就是说，若存在负圈，在第$|V|$次循环也会更新$d$值，可以利用这个性质检查是否存在负圈。

struct edge
{
    int from, to, cost;
};
edge es[max_e];
int d[max_v];
int v, e;
//从顶点s出发的单源最短路
void bellman_ford(int s)
{
    for(int i = 0; i != v; ++i)
        d[i] = INF;//无限大
    d[s] = 0;
    for( ; ;)
    {
        bool update = false;
        for(int i = 0; i != e; ++i)
        {
            edge e = es[i];
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost)
                d[e.to] = d[e.from] + e.cost, update = true;
        }
        if(!update)
            break;
    }
}
//检查负圈，返回真为有
bool find_negative_loop(void)
{
    std::fill(d, d + max_v, 0);
    for(int i = 0; i != v; ++i)
    for(int j = 0; j != e; ++j)
    {
        edge e = es[j];
        if(d[e.to] > d[e.from] + e.cost)
        {
            d[e.to] = d[e.from] + e.cost;
            //第n次仍更新则存在负圈 
            if(i == v - 1)
                return true;
        }
    }
    return false; 
}

2.Dijkstra求无负边的单源最短路

描述：①找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离，此后不需要再关心“最短距离已经确定的顶点”。如何得到“最短距离已经确定的顶点”呢？在开始时，只有到起点的最短距离是确定的。在尚未使用过的顶点中，距离$d_i$最小的顶点就是最短距离已经确定的顶点。下面给出时间复杂度为$O(|V|^{2})$使用邻接矩阵实现的Dijkstra算法。

int cost[max_v][max_v];//存权值的邻接矩阵
int d[max_v];//最短距离
bool used[max_v];//已经使用过的图
int v;//顶点数量
void Dijkstra(int s)
{
    std::fill(d, d + v, INF);
    std::fill(used, used + v, false);
    d[s] = 0;
    for( ; ;)
    {
        int v = -1;
        //从未使用过的顶点中找出一个距离最小的顶点
        for(int u = 0; u != ::v; ++u) 
            if(!used[u] && (v == -1 || d[u] < d[v]))
                v = u;
        if(-1 == v)
            break;
        for(int u = 0; u != ::v; ++u)
            d[u] = std::min(d[u], d[v] + cost[v][u]);
    }
}

当使用邻接表时，更新最短距离只需要访问每条边1次，因此这部分的复杂度是$O(|E|)$，但是查找顶点需要都枚举一次，最终复杂度还是平方级的。可以使用C++ STL的优先队列priority_queue来实现。在每次更新时往堆里插入当前最短距离和顶点的值对，当取出的最小值不是最短距离的话，就丢弃它。这样算法的复杂度优化到了$O(|E|\log|V|)$。Dijkstra较Bellman-Ford效率更高，但无法应用于存在负边的图。

#include <queue>
#include <vector>
#include <utility>
struct edge
{
    int to, cost
};
typedef std::pair<int, int> P;//first 最短距离, second 顶点编号 
int v;
std::vector<edge> g[max_v];
int d[max_v];
void Dijkstra(int s)
{
    std::priority_queue<P, std::vector<P>, std::greater<P> > que;
    std::fill(d, d + v, INF);
    d[s] = 0;
    que.push(P(0, s));
    while(!que.empty())
    {
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first)
            continue;
        for(auto &e : g[v])
            if(d[e.to] > d[v] + e.cost)
            {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
    }
}

3.适用于在各种图中求任意两点间距离的Floyd-Warshall

代码极短，十分有效，不解释原理。同样可用于判断是否存在负圈：检查是否存在d[i][j]是负数。复杂度：$O(|V|^{3})$。

int v, d[max_v][max_v];
void Floyd_Warshall(void)
{
    for(int k = 0; k != v; ++k)
    for(int i = 0; i != v; ++i)
    for(int j = 0; j != v; ++j)
        d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
}

三、最小生成树问题

1.用于邻接矩阵的Prim

假设有一颗只包含一个顶点v的树T，贪心地选取T和其他顶点之间相连的最小权值的边并把它加入到T中。不断进行这个操作就可以得到生成树了。下面给出的算法时间复杂度是$O(|V|^{2})$。

int v;
int cost[max_v][max_v];
int mincost[max_v];//从集合X出发的边到每个顶点的最小权
bool used[max_v] ;//顶点i是否包含在集合X中
int Prim(void) 
{
    std::fill(mincost, mincost + v, INF);
    std::fill(used, used + v, false);
    mincost[0] = 0;
    int res = 0;
    for( ; ;)
    {
        int v = -1;
        //从不属于集合X的顶点中选取从X到其权值最小的顶点
        for(int u = 0; u != ::v; ++u) 
            if(!used[u] && (v == -1 || mincost[u] < mincost[v]))
                v = u;
        if(-1 == v)
            break;
        used[v] = true;//把顶点v加入集合X
        res += mincost[v];//把边的长度加入结果 
        for(int u = 0; u != ::v; ++u) 
            mincost[u] = std::min(mincost[u], cost[v][u]);
    }
    return res;
}

2.用于邻接表的Kruskal

按照边的权值的顺序从小到大查看一遍（需要排序），若不产生圈或重边，就把这条边加入到生成树中。
如何判断是否产生圈：若要把连接u和v的边e加入到生成树中，只要加入之前u和v不在同一个连通分量里，加入e就不会产生圈，若在就一定会产生圈。引入并查集就可以做到，并查集的实现包含在代码包里。Kruskal最耗时的操作是对边的排序，时间复杂度：$O(|E|\log |V|)$。

#include <algorithm>
#include "UFS.hpp"
struct edge
{
    int u, v, cost;
};
edge es[max_e];
int v, e;
int Kruskal(void)
{
    std::sort(es, es + e, [](const edge &a, const edge &b)
    {
        return a.cost < b.cost;
    });
    init(v);//初始化并查集 
    int res = 0;
    for(auto &e : es)
        if(!same(e.u, e.v))
        {
            unite(e.u, e.v);
            res += e.cost;
        }
    return res;
}