devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法-图论_图论算法

作者：羊村懒王 | 2024-04-12 02:39:30

赞

踩

图论算法

图论（算法）

以下内容部分来自陈小玉老师的算法ppt，将图论中常见的算法进行汇总。包括图的存储以及图论的经典算法（最短路径、最小生成树）等。

部分代码转自陈小玉老师的《算法训练营》。

主要汇总了常用的图的存储和算法，建议初学者直接看B站的相关视频

一、图的存储

1、链式前向星

图的存储方法很多，最常见的除了邻接矩阵、邻接表和边集数组外，还有链式前向星。链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有临界点。

链式前向星存储包括两种结构：（要理解清除两个数组的含义）

  • 边集数组：**edge[ ] **,edge[i]表示第i条边
  • 头结点数组：head[ ]，head[i]存以i为起点的第一条边的下标
数据结构
int n,m,x,y,w;	//顶点数、边数、（弧头、弧尾、权重）
int cnt;		//边计数器
int head[maxn]; //头结点数组

struct node{
    int to,next,w;
}edge[maxe];    //边集数组，一般设置比maxn*maxn大的数，如果题目有要求除外

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
相关函数
  • 初始化，所有head都赋值-1，并且将边计数器赋值为0
void init(){//初始化
    memset(head,-1,sizeof(head));	//引入头文件 cstring
    cnt=0;
}

  • 1
  • 2
  • 3
  • 4
  • 添加边到边集中（头插法）
void add(int u,int v,int w){//添加一条边
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

注意：如果是有向图，每输入一条边，执行一次add(u,v,w)即可；如果是无向图，则需要执行add(u,v,w)，add(v,u,w);

  • 访问一个结点u的所有邻接点
for(int i=head[u] ; i!=-1 ; i=edge[i].next){	//这里的i!=-1可以用~i代替，结果相同
    int v=edge[i].to;
    int w=edge[i].w;
    //...
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 示例
int main(){
    cin>>n>>m;
    //初始化
    init();
    //创建图
    for(int i=1;i<=m;i++){
        cin>>x>>y>>w;
        add(x,y,w);
        //add(y,x,w);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
特性

  1. 和邻接表一样，因为采用头插法进行链接，所以边输入顺序不同，创建的链式前向星也不同。

  2. 对于无向图，每输入一条表，需要添加两条边，互为反向边。

    这两条边互为反向边，可以通过与1的异或运算得到其反向边，一条边的下标为i，则i^1是其反向边的下标。这个特性应用在网络流中非常方便。

  3. 链式前向星具有边集数组和邻接表的功能，属于静态链表，不需要频繁地创造结点。

2、边集数组

边集数组表示，通过数组存储每条边的起点和重点，如果是网，则增加一个权值域。

数据结构
struct Edge{
    int u,v,w;
}e[N*N];

  • 1
  • 2
  • 3
示例代码
#include <iostream>
#include <algorithm>	//使用其中的sort函数
using namespace std;
const int N=100;
int fa[N];
int n,m;//节点数，边数
struct Edge{
    int u,v,w;
}e[N*N];

bool cmp(Edge x,Edge y){//排序中使用，按照边权从小到大排序
    return x.w<y.w;
}

void Init(int n){       //初始化集合号为自身
    for(int i=1;i<=n;i++)
        fa[i]=i;
}

int Merge(int a,int b){   //合并
    int p=fa[a];
    int q=fa[b];
    if(p==q) return 0;    //属于同一个集合,如果p==q,则会构成回路
    for(int i=1;i<=n;i++){//检查所有节点，把集合号是q的改为p
        if(fa[i]==q)
            fa[i]=p;      //a的集合号赋值给b集合号
    }
    return 1;
}

int Kruskal(int n){       //求最小生成树
	int ans=0;
    sort(e,e+m,cmp);
    for(int i=1;i<m;i++){
        if(Merge(e[i].u,e[i].v)){
            //如果加入e[i]不会构成回路，则将e[i]加入到最小生成树
            ans+=e[i].w;
            n--;
            if(n==1)      //n-1次合并
                return ans;
        }
    }
    return 0;
}

int main(){
    cin>>n>>m;
    Init(n);
    for(int i=0;i<m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    cout<<"最小花费是"<<Kruskal(n)<<endl;
    return 0;
}

  • 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
特性

优点：可以对边按权值排序，方便对边进行处理。

缺点：不便于判断两点之间是否有边，不便于访问所有邻接点，不便于计算各顶点的度。

3、邻接矩阵

邻接矩阵是表示顶点之间关系的矩阵。

数据结构

邻接矩阵存储方法：

  • 一个一维数组存储图中顶点的信息（当顶点表示为a,b…等非数字形式时，起作用）
  • 一个二维数组存储图中顶点之间的邻接关系

存储顶点之间邻接关系得到二维数组成为邻接矩阵。

能够表示顶点信息有多种方式：（本质上就是将非整数映射到整数）

一维数组vex[] 或者 map映射到整数 或者 通过其他方式映射到整数

初始化+矩阵赋值

示例代码
const int maxn=10005;//结点数最大值
const int inf=0x3f3f3f3f;//ACM等竞赛中通常使用0x3f3f3f3f来表示无穷大
int E[maxn][maxn];//邻接矩阵
int n,m;//结点数，边数

void createAM(){
    int u,v;				//(带权图)网: int u,v,w;
    cin>>n>>m;
    for(int i=0;i<n;i++)	//初始化所有值为0，如果是网，则初始化为无穷大
        for(int j=0;j<n;j++)
            E[i][j]=0;		//网: E[i][j]=inf;
    for(int i=0;i<m;i++){
        cin>>u>>v;		  	//网: cin>>u>>v>>w;
    	E[u][v]=E[v][u]=1;	//网: E[u][v]=w;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
特性

优点：快速判断两顶点之间是否有边，方便计算各顶点的度

缺点：不便于增删顶点，不便于访问所有邻接点，空间复杂度高

4、邻接表

邻接表是图的一种链式存储方法。邻接表包含两部分：顶点和邻接点。

数据结构

顶点：包含顶点信息data和指向第一个邻接点的指针first。

邻接点：包括邻接点的存储下标v和指向下一个邻接点的指针next，如果是网的邻接点，则还需增加一个权值域w。

顶点vi的所有邻接点构成一个单链表。

  • 经典定义，完整定义（算法竞赛中不常用）
typedef struct AdjNode{//定义邻接点类型
    int v;//邻接点下标
    struct AdjNode *next;//指向下一个邻接点
}AdjNode;

typedef struct VexNode{//定义顶点类型
    VexType data;//VexType为顶点的数据类型，根据需要定义
    AdjNode *first;//指向第一个邻接点
}VexNode;

typedef struct{
    VexNode Vex[Max Vnum];//节点表
    int vexnum,edgenum;//节点数，边数
}ALGraph;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

由于在算法竞赛中，往往只有一个图，所以在竞赛中，通常不定义ALGraph，而是将节点表和节点数，边数等单独写在外部，并且通常使用vector和map。

  • vector存储图
vector<int> E[maxn];//每个节点定义一个vector，存储其邻接点
int n,m;//节点数，边数
void createVec(){//用vector存储无向图
    int u,v;
    cin>>n>>m;
    for(int i=0;i<m;i++){//创建邻接表
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 结合map的vector存储图
vector<int> E[MaxVnum];//引入头文件#include <vector>,定义数组E[]
map<string,int>mp;     //map映射，字符串映射到一个整数编号
void createVec(){
    string s1,s2;
    int k=1;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>s1>>s2;//一条边的两个结点字符串
        if(mp[s1]==0)  //如果这个string在map中没有，就新建一个string-int
            mp[s1]=k++;//映射到一个结点编号，
        if(mp[s2]==0)
            mp[s2]=k++;
        E[mp[s1]].push_back(mp[s2]);//邻接表中存放的都是结点的编号
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

map访问不存在的key值时，会在map中添加key-value，value会被赋予默认值

特性

优点：便于增删顶点，便于访问所有邻接点，空间复杂度低

缺点：不便于判断两顶点之间是否有边，不便于计算各顶点的度

总体上，邻接表比邻接矩阵效率更高

二、最短路径算法

Dijkstra算法：单源最短路径

Floyd算法：各个顶点之间最短路径，没有负环

Bellman-Ford算法：负权边、判断负环，单源最短路径

SPFA算法：对Bellman-Ford算法的优化

1、Dijkstra算法

Dijkstra算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该路径求出长度次短的一条路径，直到求出源点到其他各个节点的最短路径。

Dijkstra算法基本思想：将节点集合V划分为两部分：集合S和集合V-S，其中S中的节点到源点的最短路径已经确定，V-S中的节点到源点的最短路径待定。

（常常使用一个额外的数组来划分集合）

从源点触发只经过S中的节点到达V-S中的节点的路径成为特殊路径。Dijkstra算法的贪心策略是选择最短的特殊路径长度dist[t]，并将节点t加入到集合S中，同时借助t更新数组dist[]。一旦S包含了所有节点，dist[]就是从源点到其他节点的最短路径长度。

算法设计
  • 数据结构。邻接矩阵G[][]（可以是其他存储方式）存储图，**dist[t]**记录从源点到节点i的最短路径长度，**p[i]记录最短路径上节点i的直接前驱。如果flag[i]**等于true，说明节点i已加入集合S，否则i属于集合V-S。
  • 初始化。假设u为源点，令集合S={u}，对V-S集合中节点i，初始化dist[i]=G[u][i]，如果源点u到节点i有边相连，初始化p[i]=u，否则p[i]=-1。
  • 找最小。按照贪心策略来查找V-S集合中dist[]最小的节点t，t就是V_S集合中距离源点u最近的节点。将节点t加入集合S。
  • 松弛操作。对V-S集合中所有节点j，考察是否可以借助t得到更短的路径。如果源点u经过t到j的路径更短，dist[j]>dist[t]+G[t][j]，则更新dist[j]=dist[t]+G[t][j]，即松弛操作，并记录j的直接前驱为t，即p[j]=t。
  • 重复，直到V-S为空。

存储：可以使用邻接矩阵，邻接表，链式前向星

找最小：可以遍历，或者使用优先队列

输出路径：可以采用栈实现翻转，或者递归实现翻转

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
const int N=1005;
const int INF=0x3f3f3f3f;//无穷大
int G[N][N],dist[N];//G[][]为邻接矩阵，dist[i]表示源点到i的最短路径长度
int p[N]; 			//p[i]表示源点到结点i的最短路径上i的前驱
int n,m;			//n为结点数，m为边数
bool flag[N];		//如果flag[i]等于true,说明节点i已经加入到S集合，否则i属于V-S

//初始化+找最小+松弛操作
void dijkstra(int u){
    //初始化
    for(int i=1;i<n;i++){
        dist[i]=G[u][i];//初始化距离数组dist[]
        flag[i]=flase;
        if(dist[i]==INF)//初始化前驱数组p[]
     		p[i]=-1;
        else
            p[i]=u;
    }
    dist[u]=0;
    flag[u]=true;//初始，集合S中只有源点u
    
    for(int i=1;i<n;i++){
        //找最小值，找到V-S中dist[]最小结点
        int temp=INF,t=u;	//暂存S集合到V-S集合的最短距离和节点
        for(int j=1;j<=n;j++){
            if(!flag[j]&&dist[j]<temp){//V-S集合中并且更短
                t=j;
                temp=dist[j];
            }
        }
        if(t==u)	return; //如果没有找到最小值，跳出循环
        flag[t]=true;		//找到t，将其加入到S中
        //松弛操作,更新dist[],和p[]
        for(int j=1;j<=n;j++){
            if(!flag[j]&&(dist[j]>dist[t]+G[t][j])){
                //利用新加入的t节点，对V-S集合中剩余的所有点，进行松弛操作
            	dist[j]=dist[t]+G[t][j];
                p[j]=t;
            }       
        }
    }
}

void print(){//输出源点到其他节点的最短距离
    for(int i=1;i<=n;i++){
        if(i!=1) cout<<" ";
        if(dist[i]==INF)
            cout<<"impossible";
        else
            cout<<dist[i];
    }
    cout<<endl;
}

void findp(int u){//输出源点到u的最短路径，（递归）
    if(u!=-1)
        return;
    findp(p[u]);
    cout<<u<<"\t";
}

void findpath(int u){//输出源点到其他各节点的最短路径，（递归）
    cout<<"源点为:"<<u<<endl;
    cout<<"源点到其他各节点最短路径为："<<endl;
    for(int i=1;i<=n;i++){
        findp(i);
        cout<<"最短距离为:"<<dist[t]<<endl;
    }
}

void findpath2(int u){//输出源点到其它各节点的最短路径，（利用栈非递归）
	int x;
    stack<int> s;
    cout<<"源点为:"<<u<<endl;
    cout<<"源点到其他各节点最短路径为:"<<endl;
    for(int i=1;i<=n;i++){
        x=p[i];
        while(x!=-1){
            s.push(x);
            x=p[x];
        }
        while(!s.empty()){
            cout<<s.top()<<"---";
            s.pop();
        }
        cout<<i<<"\t最短距离为:"<<dist[i]<<endl;
    }
}

  • 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
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 算法分析

时间复杂度：找最小值和松弛操作本身各执行n次，需要重复n-1次，总执行次数均为n2，时间复杂度为O(n2)

空间复杂度：包含数组flag[]、p[]，空间复杂度为O(n)

  • 算法优化1

找最小值。按照贪心策略查找V-S集合中dist[]最小的节点，其时间复杂度为O(n)，如果使用优先队列，则每次找最小值时间复杂度降为O(logn)，找最小值的总时间复杂度为O(nlogn)。

  • 算法优化2

松弛操作。如果采用邻接表或链式前向星存储，松弛操作就不用每次执行n次，而是执行节点t的邻接点数（t的出度），所有节点的出度之和等于边数m，松弛操作的总时间复杂度为O(m)。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1005;
const int INF=0x3f3f3f3f;//无穷大
int G[N][N],dist[N];     //G[][]为邻接矩阵，dist[i]表示源点到结点i的最短路径长度
int n,m;				 //n为结点数，m为边数
bool flag[N]; 			 //如果flag[i]等于true，说明结点i已经加入到S集合;否则i属于V-S集合

struct node{
    int u,dis;//结点u,源点到u的最短路径长度dis
    node(){};
    node(int _u,int _dis){//构造函数，使得赋值方便 
        u=_u; dis=_dis;
    }
    bool operator < (const node &a)const{ //重载<,优先队列优先级，dis越小越优先 
        return dis>a.dis;			//注意优先队列内部是从大到小输出
    }
};

void dijkstra(int u){
	priority_queue<node>que;  // 优先队列优化
    //初始化
    for(int i=1;i<=n;i++){
    	dist[i]=INF; // 初始化所有距离为无穷大
    	flag[i]=false;
	}
	dist[u]=0;
	node vs=node(u,0);//创建源点node
    que.push(vs);
    while(!que.empty()){
        node it=que.top();//优先队列队头元素为dist最小值
        que.pop();
        int t=it.u;
        if(flag[t])//说明已经找到了最短距离，该结点是队列里面的重复元素
            continue;
        flag[t]=true;//将t加入到S集合中
        for(int j=1;j<=n;j++){//松弛操作 
            if(!flag[j]&&dist[j]>dist[t]+G[t][j]){
                dist[j]=dist[t]+G[t][j];
                que.push(node(j,dist[j])); //把更新后的最短距离压入优先队列，注意：里面的元素有重复
            }
        }
    }
}

void print(){//输出源点到其它节点的最短距离 
	for(int i=1;i<=n;i++){
    	if(i!=1) cout<<" ";
        if(dist[i]==INF)
        	cout<<"impossible";
        else
        	cout<<dist[i];
    }
    cout<<endl;
}

  • 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

2、Floyd算法

Dijkstra算法用于求从源点到其他各个节点的最短路径。如果求解任意两个节点之间的最短路径，则需要以每个节点为源点，重复调用n次Dijkstra算法。

Floyd算法可用于求解任意两个节点间的最短路径。Floyd算法又被称为插点法，其算法核心是在节点i和节点j之间插入节点k，看看是否可以缩短节点i与节点j之间的距离（松弛操作）。

算法设计

数据结构。邻接矩阵G[][]存储图，dist[i][j]记录从节点i到节点j的最短路径长度，p[i][j]记录节点i到节点j的最短路径上节点j的直接前驱。

初始化。dist[i][j]=G[i][j]，如果节点i到节点j有边相连，p[i][j]=i，否则p[i][j]=-1。

插点。其实就是在节点i、j之间插入节点k，看是否可以缩短节点i、j之间的距离（松弛操作）。

如果dist[i][j]>dist[i][k]+dist[k][j]，则dist[i][j]=dist[i][k]+dist[k][j]，并记录节点j的前驱，p[i][j]=p[k][j]。

算法分析

时间复杂度：三层for循环，时间复杂度为O(n3)。

空间复杂度：数组dist[][]、p[][]，空间复杂度为O(n2)。

示例代码
#include <iostream>
#include <cstring>
using namespace std;
const int N=100;
const int INF=0x3f3f3f3f;
int G[N][N],dist[N][N];//G[][]为邻接矩阵，dist[i][j]表示i到j的最短路径长度
int p[N][N];//p[i][j]表示i到j的最短路径上j的前驱
int n,m;//n表示节点数，m表示边数

void Floyd(){
    //初始化
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)
                dist[i][j]=0;//自己到自己的最短距离为0
            else
                dist[i][j]=G[i][j];
            if(dit[i][j]<INF&&i!=j)
                p[i][j]=i;//如果i，j有边，则j前驱为i
            else
                p[i][j]=-1;//如果i，j无边，则j前驱置为-1
        }
    }
    //插点法，松弛操作
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(dist[i][k]+dist[k][j]<dist[i][j]){//从i经k到j的一条路径更短
                    dist[i][j]=dist[i][k]+dist[k][j];//更新dist[i][j]
                    p[i][j]=p[k][j];//尤其注意，更改j的前驱
                }    
}

void print(){
    for(int i=0;i<n;i++){//输出最短距离数组
        for(int j=0;j<n;j++)
            cout<<dist[i][i]<<"\t";
        cout<<endl;
    }
    cout<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cout<<dist[i][j]<<"\t";
        cout<<endl;
    }
}

void DisplayPath(int s,int t){//输出s到t的最短路径
    if(p[s][t]!=-1){		  //利用递归实现反向输出，或者利用栈实现反向输出
        DisplayPath(s,p[s][t]);
        cout<<p[s][t]<<"-->";
    }
}

  • 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

3、Bellman-Ford算法

用于求解单源最短路径问题。优点是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但是，对该算法可以进行若干种优化，以提高效率。

Bellman-Ford算法与Dijkstra算法类似，都以松弛操作为基础。Dijkstra算法以贪心法选取未被处理的具有最小权值的节点，然后对其邻接点进行松弛操作。Bellman-Ford算法对所有边进行松弛操作，共n-1次，因为负环可以无限制的减少最短路径长度，所以如果第n次操作仍可以松弛，则一定存在负环。

算法设计
  1. 数据结构。因为需要利用边进行松弛，因此采用边集数组存储。每条边都有三个域：两个端点a、b和边权w
  2. 松弛操作。对所有的边j(a,b,w)，如果dist[e[j].b]>dist[e[j].a]+e[j].w，则dist[e[j].b]=dist[e[j].a]+e[j].w。dist[v]表示从源点到节点v的最短路径长度
  3. 重复松弛操作n-1次
  4. 再执行一次，如果仍可以松弛，则说明有负环
示例代码
#include <iostream>
#include <cstring>
using namespace std;
const int N=1005;
const int INF=0x3f3f3f3f;	//无穷大
struct node{
    int a,b,w;
}e[N*N];					//边数要设置为N*N
int dist[N];
int n,m,cnt;

void add(int u,int v,int w){//添加一条边
    e[cnt].a=u;
    e[cnt].b=v;
    e[cnt++].w=w;
}

bool bellman_ford(int u){//求源点u到其他各个顶点的最短路径长度
	//初始化 
    memset(dist,0x3f,sizeof(dist));//初始化为无穷大，注意memset按照字节进行初始化
    dist[u]=0;
    for(int i=1;i<n;i++){
        bool flag=false;
        for(int j=0;j<m;j++){//边数m或者cnt，如果是无向图，边数则为2m
            if(dist[e[j].b]>dist[e[j].a]+e[j].w){
                dist[e[j].b]=dist[e[j].a]+e[j].w;
                flag=true;
            }
        }
        if(!flag)		//不能进行松弛操作了，提前结束
            return false;
    }
    for(int j=0;j<m;j++)//再执行1次，还能松弛说明有负环
        if(dist[e[j].b]>dist[e[j].a]+e[j].w)
            return true;
    return false;
    }
}

  • 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
算法分析

时间复杂度：算法中对每条边进行松弛操作，重复n-1次，时间复杂度O(nm)。

空间复杂度：包含数组e[]、dist[]，空间复杂度为O(n+m)

算法优化

提前退出循环，在实际操作中，Bellman-Ford算法经常会在未到达n-1次时就求解完毕，可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环。通过上段代码中的if(!flag)就可以提前退出循环。

队列优化。松弛操作，必定只会发生在最短路径松弛过的前驱节点上，用一个队列记录松弛过的节点，可以避免冗余计算。这就是队列优化的Bellman-Ford算法，又被称为SPFA算法。

4、SPFA算法

SPFA算法是Bellman-Ford算法的队列优化算法，通常用于求解包含负权边的单源最短路径，以及判负环。在最坏情况下，SPFA算法的时间复杂度和Bellman-Ford算法相同，为O(nm)，但在稀疏图上运行效率比较高，为O(km)，其中k是一个比较小的常数。

算法设计

数据结构。链式前向星存储图，dist[i]记录从源点到节点i的最短路径长度，vis[i]标记节点i是否在队列中，sum[i]记录节点i入队次数。

创建一个队列，源点u入队，标记u在队列中，u的入队次数加1。

松弛操作，取出队头，标记x不在队列中，考察x的所有出边i(x,v,w),，如果dist[v]>dist[x]+e[j].w，则dist[v]=dist[x]+e[i].w，如果节点v不在队列中，如果v的入队次数加1后大于或等于n，则说明有负环，退出；否则v入队，标记v在队列中。

重复松弛操作，直到队列为空。

示例代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1005;
const int INF=0x3f3f3f3f;
int n,m,cnt;
int head[N],dist[N],sum[N];
bool vis[N];//标记是否在队列中
struct node{
    int to,next,w;
}e[N*N];

void add(int u,int v,int w){
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

bool spfa(int u){
    queue<int> q;
    //初始化
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(sum,0,sizeof(sum));
    memset(dist,0x3f,sizeof(dist));
    vis[u]=1;
    dist[u]=0;
    sum[u]++;
    q.push(u);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(dist[v]>dist[x]+e[i].w){
                dist[v]=dist[x]+E[i].w;
                if(!vis[v]){
                    if(++sum[v]>=n)
                        return true;//说明有负环
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

  • 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
算法分析

时间复杂度：最坏情况下时间复杂度是O(nm)，对于稀疏图的时间复杂度为O(km)，其中k是一个较小的常数。

空间复杂度：包含数组e[]、disst[]，空间复杂度为O(n+m)。

算法优化

SPFA算法两个优化策略：SLF，LLL

SLF策略：如果待入队的节点是j，队首元素为结点i，若dist[j]<dist[i],，则将j插入队首，否则插入队尾。

LLL策略：设队首元素为结点i，队列中所有dist[]的平均值为x，若dist[i]>x,则将节点i插入队尾，查找下一元素，直到找到某一节点i满足dist[i]<=x，将节点i出队，进行松弛操作 。

三、最小生成树

找出n-1条权值最小的边很容易，那么怎么保证无回路呢？如果在一个图中社恩度搜索或者广度搜索没有回路，是一件繁重的工作。有一个很好的办法----集合避圈法。

1、Prim算法

把已经在生成树中的节点看作一个集合，剩下节点看作另一个集合，从连接两个集合的边中选择一条权值最小的边。

直观地看图很容易找出U到V-U集合的边中哪条边是最小的，但是程序中如果穷举这些边，再找最小值就太麻烦了，那怎么办？

可以设置两个数组巧妙解决这个问题：

closest[j]：表示V-U中的顶点j到集合U中的最邻近点

lowcost[j]：表示V-U中的顶点j到集合U中的最邻近点的边值，即边(j,closest[j])的权值

算法设计

初始化：领集合U={u0}，u0∈V，并初始化数组s[]、closest[]、lowcost[]

在V-U集合中找lowcost[]值最小的顶点t，即lowcost[t]=min{lowcost[j]|j∈V-U}，满足该公式的顶点t就是集合V-U中连接集合U的最邻近点

将顶点t加入集合U

如果V-U为空，算法结束，否则，继续

对集合V-U中的所有顶点j，更新其lowcost[]和closest[]，重复以上操作

其实：就是不断将两个集合的连接边中的最小值找到，利用新加入U的t更新这些最小值

示例代码
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1005;
int c[N][N],closest[N],lowcost[N],ans[N];
bool s[N];//区分U和V-U集合
int n,m;//结点数、边数

int prim(int n){
    //初始化
    s[1]=true;//加入1到集合U中
    lowcost[1]=0;
    for(int i=2;i<=n;i++){
        lowcost[i]=c[1][i];
        closest[i]=1;
        s[i]=false;
    }
    
    for(int i=1;i<n;i+++){//考虑加入剩下n-1个节点
        int temp=inf;
        int t=1;
        for(int j=1;j<=n;j++){//
            if(!s[j]&&lowcost[i]<temp){
                t=j;
                temp=closets[j];
            }
        }
        if(t==1)
            return 0;//找不到t，跳出循环，不存在最小生成树（非连通图）
        s[t]=true;
        for(int j=1;j<=n;j++){
            if(!s[j]&&c[t][j]<lowcost[j]){
                lowcost[j]=c[t][j];
                closest[j]=t;
            }
        }
    }
    int sumcost=0;
    for(int i=1;i<=n;i++)
        sumcost+=lowcost[j];
    return sumcost;
}

  • 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
算法分析

时间复杂度：两层for循环，时间复杂度为O(n2)

空间复杂度：辅助数组closest[]、lowcost[]、s[]，空间复杂度为O(n)

2、Kruskal算法

Kruskal算法将n个顶点看成是n个孤立的连通分支，首先将所有的边按权值从小到大排序，然后做贪心选择。

在边集E中选取权值最小的边(i,j)，如果将边(i,j)加入集合TE中不产生回路，则将边(i,j)加入到边集TE中，否则将继续选择下一条最短边。

Kruskal用了非常聪明的办法，即集合避圈法：

如果待选边的起点和终点都在T的集合中，就可以判定形成回路。待选择边的两个端点不能属于同一集合。

算法设计

初始化：将图G的边集E中的所有边按权值从小到大排序，边集TE={}，每个顶点初始化一个集合号。（采用边集数组存储）

在E中寻找权值最小的边(i,j)。

如果顶点i和j位于两个不同的连通分支，则将边(i,j)加入边集TE，并将两个连通分支进行合并。

将边(i,j)从集合E中删去，即E=E-{(i,j)}。

如果选取边数小于n-1，重复，否则，算法结束。

示例代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1005;
int nodeset[N];
int n,m;
struct Edge{
    int u,v,w;
}e[N*N];

bool cmp(Edge x,Edge y){//定义优先级，按边值进行升序排序
    return x.w<y.w;
}

void init(int n){//为每个节点初始化一个集合号
    for(int i=1;i<=n;i++)
        nodeset[i]=i;
}

bool merge(int a,int b){//合并集合
	int p=nodeset[a];
    int q=nodeset[b];
    if(p==q) return false;//集合号相同，也就是说会产生回路
    for(int i=1;i<=n;i++){//检查所有节点，把集合号是q的都改成p
    	if(nodeset[i]==q)
            nodeset[i]=p;
    }
    return true;//完成合并
}

int kruskal(int n){
    int ans=0,cnt=0;
    for(int i=0;i<m;i++){
        if(merge(e[i].u,e[i].v)){
            ans+=e[i].w;
            cnt++;
	        if(cnt==n-1)
    	        return ans;//选中n-1条边是结束
    	}
    }
    return 0;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        init(n);
        for(int i=0;i>m;i++){
            cin>>e[i].u>>e[i].v>>e[i].w;
        }
        sort(e,e+m,cmp);
        cout<<kruskal(n)<<endl;
    }
    return 0;
}

  • 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 <iostream>
#include <algorithm>
using namespace std;
const int N=1005;
int fa[N];
int n,m;
struct Edge{
    int u,v,w;
}e[N*N];

bool cmp(Edge x,Edge y){
    return x.w<y.w;
}

void init(int n){
    for(int i=1;i<=n;i++)
        fa[i]=i;
}

int find(int x){
    if(x!=fa[x])		  //表明这个节点已经加入到最小生成树中
        fa[x]=find(fa[x]);//把当前节点到其祖宗路径上的所有节点的集合号改为祖宗集合号
    return fa[x];
}

bool merge(int a,int b){
    int p=find(a);
    int q=find(b);
    if(p==q) return false;
    fa[q]=p;
    return true;
}

int kruskal(int n){
    int ans=0,cnt=0;
    for(int i=0;i<m;i++){
        if(merge(e[i].u,e[i].v)){
            ans+=e[i].w;
            cnt++;
            if(cnt==n-1)
                return ans;
        }
    }
    return 0;
}

  • 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
算法分析

时间复杂度：边排序为O(mlogm)，合并为O(n2)。

空间复杂度：辅助数组nodeset[]，空间复杂度为O(n)。

算法优化

时间复杂度：边排序为O(mlogm)，合并为O(nlogn)

空间复杂度：O(n)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/408804
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号