数据结构-图

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

最小生成树

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

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

模版例题： HDU-1102

#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

#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)$

需要注意的小知识点

图的逆邻接表存储只适用于有向图
邻接表不便于求入度，逆邻接表不便于求出度，而十字链表便于求入度和出度。
图的BFS生成树的树高$\le$DFS生成树的树高（如只有一个点的图和形成一个环的图）
$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$ :边数))的图称为稀疏图