0%

数据结构-图

关于图的算法及其复杂度和适用场景分析

最小生成树

$prim$算法(普里姆算法)

  • 时间复杂度$O(N^2)$
  • 适用场景:稠密图
  • 又叫加点法

模版例题: HDU-1102

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstring>
int N, Q;
/*
Prim 求 MST
耗费矩阵 cost[][],标号从 1 开始,1 ~ n
返回最小生成树的权值,返回 -1 表示原图不联通
*/
const int INF = 0x3f3f3f3f;
const int MAXN = 100 + 10;
int cost[MAXN][MAXN];
bool vis[MAXN];
int lowc[MAXN];
int Prim(){
int ans = 0;
memset(vis, 0, sizeof(vis));
vis[1] = true;
for(int i = 2; i <= N; i++){
lowc[i] = cost[1][i];
}
for(int i = 2; i <= N; i++){
int minc = INF;
int p = -1;
for(int j = 1; j <= N; j++){
if(!vis[j] && minc > lowc[j]){
minc = lowc[j];
p = j;
}
}
if(minc == INF) return -1;// 原图不联通
ans += minc;
vis[p] = true;
for(int j = 1; j <= N; j++){
if(!vis[j] && lowc[j] > cost[p][j]){
lowc[j] = cost[p][j];
}
}
}
return ans;
}
int main(){
while(~scanf("%d", &N)){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
scanf("%d", &cost[i][j]);
}
}
scanf("%d", &Q);
while(Q--){
int u, v;
scanf("%d%d", &u, &v);
cost[u][v] = cost[v][u] = 0;
}
printf("%d\n", Prim());
}
return 0;
}

$Kruskal$算法(克鲁斯卡尔算法)

  • 时间复杂度$O(elog_2e)$
  • 适用场景:稀疏图
  • 又叫加边法,所以对边操作特别方便(如让求最小生成树最大或最小边的裸题)
例题:POJ - 1251
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
const int MAXN=27+10;//最大点数
const int MAXM=75+10;//最大边数
int F[MAXN];//并查集使用
struct Edge{
int u,v,w;
}edge[MAXM];
int tol;//边数,加边前赋值为0
void addedge(int u,int v,int w){
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
//排序函数,将边按照权值从小到大排序
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
int find(int x){
if(F[x]==-1) return x;
else return F[x]=find(F[x]);
}
//传入点数,返回最小生成树的权值,如果不连通返回-1
int Kruskal(int n){
memset(F,-1,sizeof F);
sort(edge,edge+tol,cmp);
int cnt=0;//计算加入的边数
int ans=0;
for(int i=0;i<tol;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if(t1!=t2){
ans+=w;
F[t1]=t2;
cnt++;
}
if(cnt==n-1) break;
}
if(cnt<n-1) return -1;//不连通
else return ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int n,k,w;
char u,v;
while(cin>>n&&n){
tol=0;//初始化边数
for(int i=1;i<n;i++){
cin>>u>>k;
while(k--){
cin>>v>>w;
addedge(u-'A',v-'A',w);
}
}
cout<<Kruskal(n)<<"\n";
}
}

最短路径

$Dijkstra$算法(迪杰斯特拉算法)

  • 时间复杂度:不用堆优化$O(N^2)$,堆优化以后$O(Nlog_2N)$

$Floyd$算法(弗洛伊德算法)

  • 时间复杂度:$O(N^3)$

需要注意的小知识点

  1. 图的逆邻接表存储只适用于有向

  2. 邻接表不便于求入度逆邻接表不便于求出度,而十字链表便于求入度和出度

  3. 图的BFS生成树的树高$\le$DFS生成树的树高(如只有一个点的图和形成一个环的图)

  4. $MST \bigl( Minimum Spanning Tree \bigr)$性质:假设$N=(V,E)$是一个联通网,$U$是顶点集$V$的一个非空子集(可以从图的定义理解:$G=(V,E)$中$V$就是顶点的有穷非空子集,在图中不可以为空,而树是可以为空的。),若$(u,v)$是一条具有最小权值(代价)的边,其中$u\subseteq U, v\subseteq V-U$,则必存在一颗包含$(u,v)$的最小生成树。

一些名词解释

  • 稀疏图:有很少边或弧(如 $e<nlog_2n$ ( $n$ :点数, $e$ :边数))的图称为稀疏图
如果对您有帮助,请我喝杯奶茶?