这里介绍了图论中常见算法的原理和实现。
一、邻接表存图
用邻接矩阵表示稀疏图会浪费大量内存空间。而在邻接表中是通过把类似于“从顶点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;
}