并查集

代码实现：

int par[MAXN], Rank[MAXN];
void init(int n)
//初始化，将自身作为自己的父节点
{
for (int i = 0; i < n; i++)
{
par[i] = i;
Rank[i] = i;
}
}
int find(int x)
//找到x的父节点
{
if (par[x] == x)return x;
else return x = find(par[x]);
}
void unite(int x,int y)
//合并x和y的集合
{
x = find(x);
y = find(y);
if (x == y)return;
if (Rank[x] > Rank[y])
par[x] = y;
else
{
par[y] = x;
if (Rank[x] = Rank[y])Rank[x]++;
}
}
bool same(int x, int y)
//判断二者的集合是否一致
{
return find(x) == find(y);
}

最短路问题：

1. 单源最短路问题1(Bellman-Ford算法)

• 单源最短路问题是固定一个七点，求它到其他所有顶点的最短路的问题
• d[i] = min{d[i]+(从j到i的边的权值)|e=(j,i)∈E}

代码实现：

#include <iostream>
#define INF 0x3f3f3f3
const int maxn = 1000;
using namespace std;
//从顶点from指向顶点to的权值为val的边
struct edge
{
int from; int to; int val;
};
edge es[maxn];
//边
int d[maxn], V, E;
//V是顶点数，E是边数，d[i]存放点i的最短距离。
//求解从顶点s出发到所有点的最短距离
void Shortest_path(int s)
{
for (int i = 0; i < V; i++)d[i] = INF;
d[s] = 0;
while (true)
{
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.val)
{
d[e.to] = d[e.from] + e.val;
update = true;
}
}
if (!update)break;
}
}

• 若图中不存在可达的负权回路，那么该最短路不会经过同一个结点两次(也就是说，最多通过V-1条边，while(true)的循环最多执行V-1次，因此若在第V次还在更新d的值说明图中存在负圈。所以，如果一开始对所有的顶点i，都把d[i]赋值为0，那么可以检查出所有的负圈。

检测负圈代码实现：

//如果返回true则说明存在负圈
bool find_negative_loop()
{
memset(d, 0, sizeof d);
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.val)
{
d[e.to] = d[e.from] + e.val;
//若第V次还在更新说明存在负圈
if (i == V - 1)return true;
}
}
}
return false;
}

2. 单源最短路问题2(Dijkstra算法)

• 在Bellman-Ford算法中，如果d[i]还不是最短距离的话，那么即使进行d[j]=d[i]+(从i到j的边的权值)的更新，d[j]也不会变成阻断距离。而且，即使d[i]没有变化，每一次循环也要检查一遍从i出发的所有边。浪费时间。因此做出如下优化：
  • (1)找到最短距离已经确认的点，从它出发更新相邻顶点的最短距离
  • 此后不需要再关心已经确认过最短距离的点。

代码实现：

#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f
const int maxn = 1001;
using namespace std;
int val[maxn][maxn];	//val[i][j]表示边(i,j)的权值(不存在时这条边设为INF)
int d[maxn];
//顶点s出发的最短距离
bool used[maxn];
//已经使用过的图
int V;
//顶点个数
//求从起点s出发到各个顶点的最短距离
void dijkstra(int s)
{
fill(d,d+V,INF);
fill(used, used + V, false);
d[s] = 0;
while (true)
{
int v = -1;
//在尚未使用过的点中选择距离最小的顶点
for (int u = 0; u < V; u++)
if (!used[u] && (v == -1 || d[u] < d[v]))v = u;
if (v == -1)break;
used[v] = true;
for (int u = 0; u < V; u++)
d[u] = min(d[u], d[v] + val[v][u]);
}
}

3. 任意两点间的最短路问题(Floyd-Warshall算法)

​ 代码实现

#include <iostream>
const int maxn = 1001;
using namespace std;
int d[maxn][maxn];
int V;
void warshall_floyd()
{
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

4. 路径还原

代码实现：

int prevd[maxn];
//求从起点s出发到各个顶点的最短距离
void dijkstra(int s)
{
fill(d, d + V, INF);
fill(used, used + V, false);
fill(prevd, prevd + V, -1);
d[s] = 0;
while (true)
{
int v = -1;
//在尚未使用过的点中选择距离最小的顶点
for (int u = 0; u < V; u++)
if (!used[u] && (v == -1 || d[u] < d[v]))v = u;
if (v == -1)break;
used[v] = true;
for (int u = 0; u < V; u++)
if (d[u] > d[v] + val[v][u])
{
d[u] = d[v] + val[v][u];
prevd[u] = v;
}
}
}

最小生成树：

• 给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树。如果边上有权值，那么使得边权之和最小的生成树就叫做最小生成树。

1. 最小生成树问题1（prim算法）

代码实现：

int minval[maxn];	//已确定最短距离集合到结点v的距离
bool vis[maxn];
//判断结点是否已在最短距离集合
int val[maxn][maxn];//记录结点之间的权值
int V,E;
int prim()
{
fill(minval, minval + V, INF);
fill(vis, vis + V, false);
minval[0] = 0;
int ans = 0;
while (true)
{
int v = -1;
for (int u = 0; u < V; u++)
if (!vis[u] && (v == -1 || minval[u] < minval[v]))
v = u;
if (v == -1)break;
ans += minval[v];
vis[v] = true;
for (int u = 0; u < V; u++)
minval[u] = min(minval[u],val[v][u]);
}
return ans;
}

最小生成树问题2（kruskal算法）

• Kruskal算法按照边的权值顺序从小到大查看一遍，如果不产生圈(重边等也在内)，就把当前这条边加入到生成树之中。

代码实现：

#define MAXN 10010
int V, E;
struct edge
{
int u, v, val;
}es[MAXN];
bool cmp(edge a, edge b)
{
return a.val < b.val;
}
int kruskal() {
sort(es, es + E, cmp);
//将所有边按照权值大小，从小到大排序
init(V);
//并查集的初始化，将每个节点当作一个集合，不断合并
int res = 0;
for (int i = 0; i < E; i++)
{
edge e = es[i];
if (!same(e.u, e.v))
//合并结点
{
unite(e.u, e.v);
res += e.val;
}
}
return res;
}

最后

以上就是清爽狗为你收集整理的图论【最短路，生成树问题】并查集最短路问题：最小生成树：的全部内容，希望文章能够帮你解决图论【最短路，生成树问题】并查集最短路问题：最小生成树：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。