22232程序设计·图论基础

2023-03-30

字数统计: 6k | 阅读时长≈ 29 分钟

这是本系列的第一篇文章，旨在记录我学习C++历程中所有的感想和感悟。

本文章将以与之前写作方法不同的方式来撰写，系统的串述图论的基本知识。

第一部分图的概述

定义1.1：图论 $〔〕$ 是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

定义1.2：图 $（）$ 是一个 顶点集合和 顶点之间关系集合（又称为边集） 共同组成的一个二元组。边集由二元点组 $，$ 组成 ，表示之间存在一条边。根据边集中的边是否具有方向性来区分为 有向图（Directed Graph） 和无向图 （Undirected Graph）。

定义1.3：网络 $（）$ 是图的升级，边集由三元组组成，表示之间存在一条长度为的边。成为边的边权。网络亦称为赋权图。

定义1.4：入度 $（）$ 表示对于以点为终点的有向边的条数；出度 $（）$ 表示对于以为起点的有向边的条数。特称入度为0的点为孤立点。

定义1.5：子图$G^{'}=<V{'},E^{'}> G=<V,E> $当且仅当$ V^{'} V,E^{'}E$。

定义1.6：简单图指没有重边和自环的图。有向无环图（DAG）指一个不包含环的有向图。完全图指每一对不同节点均恰有一条边连接彼此的图。连通图指如果一个无向图的任意一节点到其余剩余节点均只有一条通路的图。

定义1.7：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为,则它的生成树含有条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

其他概念详见参考资料数据结构：图论

第二部分图的存储方法

2.1 邻接矩阵式存储

邻接矩阵存储图的节点与边信息是最稳定的做法之一，但其缺点也相当的明显：限于二维数组的超大存储空间缺陷以及此方法对空间的巨额浪费，邻接矩阵一般情况只能满足1000个以下点的存储，超过此限度可能内存爆炸。

int connects[1001][1001];
for(int i=1,u,v,w;i<=m;i++)
{
    cin>>u>>v>>w;//起点，终点，边权
    connects[u][v]=connects[v][u]=w;//无向图，有向图只有一个
}

2.2 链式邻接表存储

相较于邻接矩阵存储，链式邻接表存储更便于统计边的数目，时间复杂度是，并且大幅度的降低了空间复杂度，可以更高效的完成图的统计。然而，其缺点也是相当明显的，它并不方便使用者判断两个节点之间是否存在连接边，并且不容易计算各个顶点的入度（出度好算,就是下列代码中的connects[i].size()）

struct nexts
{
  int pos;
  int data;
}
vector<nexts> connects[10001];
for(int i=1,u,v;i<=m;i++)
{
      cin>>u>>v>>w;
      connects[u].push_back({v,w});
      connects[v].push_back({u,w});
}

2.3 链式前向星存储

静态建立的邻接表，时间复杂度为，空间效率也为,优化后文所提到的和 $、$ 的大杀器。

相对中规中矩的数据存储结构。但有一个略微致命的缺陷，不采用起终节点为下标存储边会导致找不到同起点的所有边的问题。因此，在前向星中添加一个来保存同起点的下一条边的地址。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100001;//点数最大值
int n, m, cnt;//n个点，m条边
struct Edge
{
    int to, w, next;//终点，边权，同起点的上一条边的编号
}edge[maxn];//边集
int head[maxn];//head[i],表示以i为起点的第一条边在边集数组的位置（编号），初始化为-1.
void init()//初始化
{
    for (int i = 0; i <= n; i++) head[i] = -1;
    cnt = 0;
}
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
    cin >> n >> m;
    int u, v, w;
    init();//初始化
    for (int i = 1; i <= m; i++)//输入m条边
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);//加边
        /*
        加双向边
        add_edge(u, v, w);
        add_edge(v, u, w);
        */
    }
}

第三部分图的遍历

3.1 图的DFS遍历

3.1.1 邻接表存储

#include<bits/stdc++.h>
using namespace std;
vector<int> connect[10001];
bool visit[10001];
int n,e;
void dfs(int target)
{
    cout<<target<<" ";
    for(int i=0;i<connect[target].size();i++)
    {
        if(!visit[connect[target][i]])
        {
            visit[connect[target][i]]=1;
            dfs(connect[target][i]);
        }
    }
}
int main()
{
    cin>>n>>e;
    for(int i=1,u,v;i<=e;i++)
    {
        cin>>u>>v;
        connect[u].push_back(v);
        connect[v].push_back(u);
    }
    visit[1]=true;
    dfs(1);
    system("pause");
    return 0;
}

3.2.2 链式前向星存储

输出顺序会和上述方法略有不同。链式前向星式存储会按照每个节点输入边的倒序遍历。

比如说，你的输入顺序为

1 2
1 3
1 4

在邻接表或者邻接矩阵下，搜索的遍历顺序为2-3-4;而前向星为4-3-2.

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int terminal;
    int next;
    int w;
};
int head[10001];
bool visit[10001];
edge connects[10001];
int m, n;
int ans = 0;
void add(int u, int v)
{
    connects[ans].terminal = v;
    connects[ans].next = head[u];
    head[u] = ans++;
    return;
}
void dfs(int start)
{
    cout << start << " ";
    visit[start] = true;
    for (int i = head[start]; i != -1; i = connects[i].next)
        if (!visit[connects[i].terminal])
        {
            visit[connects[i].terminal] = 1;
            dfs(connects[i].terminal);
        }
}
void init()
{
    memset(head, -1, sizeof(head));
    ans = 0;
}
int main()
{
    cin >> n >> m;

    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1);
    cout<<endl;
    system("pause");
    return 0;
}

3.2 图的BFS遍历

3.2.1 邻接表

#include<bits/stdc++.h>
using namespace std;
struct point
{
    int data;
    vector<int>connect;
}s[10001];
bool visit[10001];
void bfs(point start)
{
    queue<point> q;
    q.push(start);
    while(!q.empty())
    {
        point tem=q.front();
        q.pop();
        cout<<tem.data<<" ";
        for(int i=0;i<tem.connect.size();i++)
        {
            if(!visit[tem.connect[i]])
            {
                visit[tem.connect[i]]=1;
                q.push(s[tem.connect[i]]);
            }
            
        }

    }

}
int main()
{
    int n,e;
    cin>>n>>e;
    for(int i=1;i<=n;i++)
    {
        s[i].data=i;
    }
    for(int i=1,u,v;i<=e;i++)
    {
        cin>>u>>v;
        s[u].connect.push_back(v);
        s[v].connect.push_back(u);
    }
    visit[1]=true;
    bfs(s[1]);
    cout<<endl;
    system("pause");
    return 0;
}

3.2.2 链式前向星

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int terminal;
    int next;
    int w;
};
int head[10001];
bool visit[10001];
edge connects[10001];
int m, n;
int ans = 0;
void add(int u, int v)
{
    connects[ans].terminal = v;
    connects[ans].next = head[u];
    head[u] = ans++;
    return;
}
void bfs(int u) /// 队列实现广度优先搜索
{
    queue<int> q;
    visit[u] = true;
    q.push(u);
    while (!q.empty())
    {
        int k = q.front();
        q.pop();
        cout << k << " ";
        for (int i = head[k]; ~i; i = connects[i].next)
        {
            if (!visit[connects[i].terminal])
            {
                q.push(connects[i].terminal);
                visit[connects[i].terminal] = true; /// 因为不是递归实现，所以每次放入队列后都需要立即标记。
            }
        }
    }
}

void init()
{
    memset(head, -1, sizeof(head));
    ans = 0;
}
int main()
{
    cin >> n >> m;

    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    bfs(1);
    system("pause");
    return 0;
}

第四部分图的最小生成树

4.1 Prim算法生成最小树

算法查找最小生成树的过程，采用了贪心算法的思想。对于包含个顶点的连通网，算法每次从连通网中找出一个权值最小的边，这样的操作重复次，由条权值最小的边组成的生成树就是最小生成树。

算法的实现思路是：

初始状态下，所有顶点均属于集合~；
选择任意一个顶点，令；
从~的所有顶点出发，找出一条连接着中的某个顶点且权值最小的边，将此边连接着的 ~中的顶点移动到集合中；
重复执行第 3 步，直至 ~类中的所有顶点全部移动到 S中，恰好可以找到 N-1 条边。

Prim

关于算法的图解参考资料

邻接矩阵写法

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7f7f7f;
int connects[1001][1001];
int dist[1001];
bool visit[1001];
int prim(int n)
{
    dist[1]=0;//最小生成树，起点随意选，默认选一
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int location=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visit[j]&&(location==-1||dist[j]<dist[location]))
            {
                location=j;
            }
        }//从dist集合中选出要放入集合S的点（距离集合S最近的一个点）
        if(dist[location]>=INF)return -1;//如果没有就剪枝，不可能存在。
        ans+=dist[location];
        visit[location]=true;
        for(int k=1;k<=n;k++)
        {
            if(!visit[k])dist[k]=min(dist[k],connects[location][k]);
        }
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            visit[i]=false;
            dist[i]=INF;
            for(int j=1;j<=n;j++)
            {
                connects[i][j]=INF;
            }
        }
        for(int i=1,u,v,w;i<=m;i++)
        {
            cin>>u>>v>>w;
            connects[u][v]=w;
            connects[v][u]=w;
        }
        int sum=prim(n);
        if(sum==-1)cout<<"impossible"<<endl;
        else cout<<sum<<endl;

    }
    system("pause");
    return 0;

}

邻接表写法

#include<bits/stdc++.h>
using namespace std;
struct connect
{
    int pos;
    int w;
};
vector<connect> connects[10001];
int dist[10001];
bool visit[10001];
const int INF=0x7f7f7f;
int Prim(int n)
{
    dist[1]=0;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int location=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visit[j]&&(location==-1||dist[j]<dist[location]))
            location=j;
        }
        if(dist[location]>=INF)return -1;
        ans+=dist[location];
        visit[location]=true;
        for(int j=0;j<connects[location].size();j++)
        {
            if(!visit[connects[location][j].pos])dist[connects[location][j].pos]=min(dist[connects[location][j].pos],connects[location][j].w);
        }
    }
    return ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        visit[i]=false;
        dist[i]=INF;
    }
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        connects[u].push_back({v,w});
        connects[v].push_back({u,w});
    }
    int sum=Prim(n);
        if(sum==-1)cout<<"impossible"<<endl;
        else cout<<sum<<endl;
    system("pause");
}

链式前向星

#include <bits/stdc++.h>
using namespace std;
struct nexts
{
    int terminal;
    int next;
    int w;
} connects[10001];
bool visit[10001];
int head[10001];
int cnt;
int n, m;
int dist[10001];
void initset()
{
    cnt = 1;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w)
{
    connects[cnt].terminal = v;
    connects[cnt].next = head[u];
    connects[cnt].w = w;
    head[u] = cnt++;
}
int Prim(int n)
{
    int sum = 0;
    dist[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        int location = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!visit[j] && (location == -1 || dist[j] < dist[location]))
                location = j;
        }
        if (dist[location] >= 0x7f7f7f)
            return -1;
        visit[location] = true;
        sum += dist[location];
        for (int ij = head[location]; ij!= -1; ij = connects[ij].next)
        {
            if(!visit[connects[ij].terminal])dist[connects[ij].terminal]=min(dist[connects[ij].terminal],connects[ij].w);
        }
    }
    return sum;
}
int main()
{
    cin >> n >> m;
    initset();
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        addedge(u, v, w);
        addedge(v, u, w);
    }
    memset(dist, 0x7f7f7f, sizeof(dist));
    int sum = Prim(n);
    if (sum == -1)
        cout << "impossible" << endl;
    else
        cout << sum << endl;
    system("pause");
}

/*
测试样例
7 12
1 2 23
1 7 36
1 6 28
2 7 1
6 7 25
2 3 20
6 5 17
7 3 4
7 4 9
7 5 16
3 4 15
5 4 3

*/

4.2 Kruskal算法生成最小树

采用并查集和类似链式前向星的数据结构维护的最小生成树。

并查集相关知识敬请参见22232程序设计原理·数据结构扩展

算法查找最小生成树的方法是：将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于个顶点的连通网，挑选出条符合条件的边，这些边组成的生成树就是最小生成树。

#include<bits/stdc++.h>
using namespace std;
struct information
{
    int x,y,w;
}point[10001];
bool compare(information a,information b)
{
    return a.w<b.w;
}
int father[10001];
int getfather(int x)
{
    if(x!=father[x])father[x]=getfather(father[x]);
    return father[x];
}
int calc,p,q,result;
int m,s;
void build()
{
    for(int i=1;i<=s;i++)
    {
        p=getfather(point[i].x);
        q=getfather(point[i].y);
        if(p==q)continue;//如果p和q的父亲节点相同，证明p和q均已经被取用并入同一集合S
        father[q]=p;//并入集合S
        result+=point[i].w;
        calc++;//计数器，剪枝
        if(calc==m-1)break;
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        calc=p=q=result=0;
        cin>>m>>s;
        for(int i=1;i<=m;i++)father[i]=i;
        for(int i=1,u,v,l;i<=s;i++)
        {
            cin>>u>>v>>l;
            point[i].x=u;point[i].y=v;point[i].w=l;
        }
        sort(point+1,point+s+1,compare);
        build();
        if(calc==m-1)cout<<result<<endl;
        else cout<<"-1"<<endl;
    }
    system("pause");
    return 0;
}

第五部分单源最短路径算法

5.1 单源最短路径算法

5.1.1 Dijkstra算法

迪杰斯特拉算法和的思路略有类似，简略概括如下：

设置两顶点的集合和，集合中存放已找到最短路径的顶点，集合中存放当前还未找到的最短路径的顶点。
初始状态时，集合中只包含源点，设为。
然后从集合中选择到源点路径长度最短的顶点加入到集合中。
集合中每加入一个新的顶点都要修改源点带集合中剩余顶点的当前最短路径值，集合中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过顶点到达该顶点的带权路径长度中的较小者。
回到3，此过程不断重复，直到集合T中的顶点全部加入到集合中为止。

Dijkstra

参考资料源：法苏ovo的博客

#include<bits/stdc++.h>
using namespace std;
bool visit[1001];
int prefix[1001];
int connects[1001][1001];
int dist[1001];
int n,m;
const int INF=0x7f7f7f;
void Dijkstra(int startpoint)//和Prim算法极其相似
{
    dist[startpoint]=0;
    prefix[startpoint]=startpoint;//前缀终点，结束路径输出
    for(int i=1;i<=n;i++)
    {
        int location=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visit[j]&&(location==-1||dist[j]<dist[location]))
            {
                location=j;
            }
        }//找到当前从起点到终点距离最小的目标点，开始松弛操作
        if(dist[location]>=INF)return;//目标点是INF无穷大证明已经没有可操作的点了，直接回退结束函数。
        visit[location]=true;//location点进入集合S
        for(int k=1;k<=n;k++)
        {
            if(!visit[k])dist[k]=min(dist[location]+connects[location][k],dist[k]);//对点的所有连接进行松弛操作。
            if(dist[k]==dist[location]+connects[location][k])prefix[k]=location;//如果成功松弛，就改变其前缀。
        }
    }

}
void findway(int terminal)
{
    stack<int> s;
    int i=terminal;
    s.push(i);
    while(prefix[i]!=i)
    {
        s.push(prefix[i]);
        i=prefix[i];
    }
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
    cout<<endl;
    return;

}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        visit[i]=false;
        dist[i]=INF;
        for(int j=1;j<=n;j++)
        connects[i][j]=INF;
        prefix[i]=i;
    }
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        connects[u][v]=connects[v][u]=w;
    }
    Dijkstra(1);
    for(int i=1;i<=n;i++)
    cout<<dist[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
    findway(i);
    system("pause");
    return 0;
}
/*
测试样例与结果：
6 9
1 3 5
1 4 30
2 1 2
2 5 8
3 6 7
3 2 15
5 4 4
6 4 10
6 5 18


0 20 5 22 28 12
1
1 3 2
1 3
1 3 6 4
1 3 2 5
1 3 6
*/

队列优化提速：

#include<bits/stdc++.h>
using namespace std;
const int INF=2147483647;
struct nexts
{
    int pos;
    int w;
};
vector<nexts> connects[100001];
struct nodes
{
    int dist;
    int location;
    bool operator<(const nodes &x)const
    {
        return x.dist<dist;
    }
};
priority_queue<nodes> q;
int n,m,dis[10001],s,visit[100001],father[100001];
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=INF;
        visit[i]=false;
        father[i]=i;
        connects[i].clear();
    }
}
int Dijkstra_queue(int n,int start)
{
    dis[start]=0;
    q.push((nodes){dis[start],start});
    while(!q.empty())
    {
        int location=q.top().location;
        q.pop();
        if(visit[location])continue;
        visit[location]=1;
        if(dis[location]>=INF)return -1;
        int num=connects[location].size();
        for(int i=0;i<num;i++)
        {
            int v=connects[location][i].pos,wv=connects[location][i].w;
            if(!visit[v])
            if(dis[v]>dis[location]+wv)
            {
                dis[v]=dis[location]+wv;
                father[v]=location;
                q.push({dis[v],v});
            }
        }

    }
    return 1;
}
void print(int terminal)
{
    stack<int> s;
    int i=terminal;
    s.push(terminal);
    while(father[i]!=i)
    {
        s.push(father[i]);
        i=father[i];
    }
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
    cout<<endl;
    return;
}
int main()
{
    cin >> n >> m >> s;
    init(n);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        connects[u].push_back({v, w});
        // connects[v].push_back({u,w});
    }
    int sun = Dijkstra_queue(n, s);
    if (sun == 1)
        for (int i = 1; i <= n; i++)
            cout << dis[i] << " ";
    else
        cout << -1;
    cout << endl;
    for (int i = 1; i <= n; i++)
    print(i);
    system("pause");
    return 0;
}

5.2 Bellman-Ford算法

算法原理在于：

每次松弛操作实际上是对相邻节点的访问，第次松弛操作保证了所有深度为的路径最短。由于图的最短路径最长不会经过超过条边，所以可知算法所得为最短路径。
与算法不同的是，算法的基本操作“拓展”是在深度上寻路,而“松弛"操作则是在广度上寻路，这就确定了算法可以对负边进行操作而不会影响结果。
因为负权环可以无限制的降低总花费，所以如果发现第次操作仍可降低花销，就一定存在负权环。这是整个算法的核心，松弛操作就是利用松弛函数。
对边集合中任意边，以表示顶点出发到顶点的权值，以表示当前从起点到顶点的路径权值。
若存在边使得: 则更新值: 即：

所以松弛函数的作用，就是判断是否经过某个顶点，或者说经过某条边，可以缩短起点到终点的路径权值。

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;//顶点最大数
const int inf=0x3f3f3f3f;
int n,m;//顶点数与边数。
int graph[maxn][maxn];//邻接矩阵存储图
int dis[maxn];//存储所有顶点到源点的距离。
void init(){
    memset(dis,inf,sizeof(dis));
    memset(graph,inf,sizeof(graph));
}
int bellman_ford(int S){
    dis[S]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            //进行松弛操作
            dis[j]=min(dis[i]+graph[i][j],dis[j]);
            
        }
    }
    int flag=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            //进行松弛操作
            if(dis[j]>dis[i]+graph[i][j]){
                flag=1;
                break;
            }
        }
    }
    return flag;
}
int main(){
    while(cin>>n>>m){
        int u,v,w;
        init();
        for(int i=0;i<m;i++){
            cin>>u>>v>>w;
            graph[u][v]=graph[v][u]=w;
        }
        int S,E;//起点与终点。
        cin>>S>>E;
        int result=bellman_ford(S);
        if(result)cout<<"此存在负权回路，计算两点之间距离可能没有意义,输出的仅供参考"<<endl;
        cout<<dis[E]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;//顶点最大数
const int M=1e4;//边最大数
const int inf=0x3f3f3f3f;
int n,m;//顶点数与边数。
int cnt;//递增存储边。
typedef struct Edge{
    int u;//边起点
    int v;//边的终端节点
    int w;//边权值。
    Edge(){};
    Edge(int u,int v,int w):u(u),v(v),w(w){}//构造函数
}Edge;
Edge edge[M];//前向星存储
int dis[maxn];//存储所有顶点到源点的距离。
void init(){
    memset(dis,inf,sizeof(dis));
}
int  bellman_ford(int S){
    dis[S]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<cnt;j++){
            //进行松弛操作，不断接近真实最短路径
            if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w){
                dis[edge[j].v]=dis[edge[j].u]+edge[j].w;
            }
        }
    }
    int flag=0;
    for(int j=0;j<cnt;j++){
        //如果还能进行松弛操作，说明存在负权回路。
        if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w){
            flag=1;
            break;
        }
    }
    return flag;
}
int main(){
    while(cin>>n>>m){
        int u,v,w;
        init();
        cnt=0;
        for(int i=0;i<m;i++){
            cin>>u>>v>>w;
            edge[cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;  //这里是针对无向图。一定要注意的是，无向图中有负边的话一定存在负权回路，而负权回路是没有意义的。
            cnt++;
            edge[cnt].u=v;edge[cnt].v=u;edge[cnt].w=w;
            cnt++;
        }
        int S,E;//起点与终点。
        cin>>S>>E;
        int result=bellman_ford(S);
        if(result)cout<<"此存在负权回路，计算两点之间距离可能没有意义,输出的仅供参考"<<endl;
        cout<<dis[E]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int maxn=105;//顶点最大数
const int M=1e4;//边最大数
const int inf=0x3f3f3f3f;
int n,m;//顶点数与边数。
typedef struct Edge{
    int to;//边的终端节点
    int w;//边权值。
    Edge(int to,int w):to(to),w(w){}//构造函数
}Edge;
vector<Edge> graph[maxn];//用vector模拟邻接表
int dis[maxn];//存储所有顶点到源点的距离。
void init(){
    memset(dis,inf,sizeof(dis));
}
int bellman_ford(int S){
    dis[S]=0;
    int t;
    int temp,len;
    for(int i=1;i<=n;i++){
            t=graph[i].size();
        for(int j=0;j<t;j++){
            temp=graph[i][j].to;
            len=graph[i][j].w;
            if(dis[temp]>dis[i]+len)
                dis[temp]=dis[i]+len;
        }
    }
    int flag=0;
    //判断是否存在负环。
    for(int i=1;i<=n;i++){
            t=graph[i].size();
        for(int j=0;j<t;j++){
            temp=graph[i][j].to;
            len=graph[i][j].w;
            if(dis[temp]>dis[i]+len){
                flag=1;
                break;
            }
        }
    }
    return flag;
}
int main(){
    while(cin>>n>>m){
        int u,v,w;
        init();
        for(int i=0;i<m;i++){
            cin>>u>>v>>w;
            graph[u].push_back(Edge(v,w));//这里针对的是无向图，有向图加边只加一次。
            graph[v].push_back(Edge(u,w));
        }
        int S,E;//起点与终点。
        cin>>S>>E;
        int result=bellman_ford(S);
        if(result)cout<<"此存在负权回路，计算两点之间距离可能没有意义,输出的仅供参考"<<endl;
        cout<<dis[E]<<endl;
    }
    return 0;
}

5.3 SPFA算法——他死了

在上进行了队列优化。

算法实现:

我们首先定义一个数组，代表我们选定的起点到其他各个点的距离最小值，将数组中除了起点以外的所有的元素都赋成(无限大);
然后我们定义一个队列（先进先出），并将起点压入队列中，记录起点已经在队列中;
循环:取出一个节点(设为)，枚举与之相连的节点(设为，并设线段的长度为),如果发现 $＋$ ，那么就更新 $＋$ ，并且如果不在队列中，就将其加入队列，并记录点已经在队列中。。如果不满足 $＋$ ，那么就什么也不做，继续取下一个。

双端队列优化优化

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
struct nexts
{
    int pos;
    int w;
};
vector<nexts> connects[100001];
int dist[100001], cnt[100001];
const int INF = 2147483647;
bool visit[100001];
void init(int n)
{
    for (int i = 1; i <= n; i++)
    {
        visit[i] = false;
        dist[i] = INF;
        connects[i].clear();
        cnt[i] = 0;
    }
}
int spfa_slf(int n, int start)
{
    deque<int> q;
    dist[start] = 0;
    q.push_back(start);
    cnt[start]++;
    visit[start] = true;
    while (!q.empty())
    {
        int location = q.front();
        q.pop_front();
        visit[location] = false;
        int t = connects[location].size();
        for (int i = 0; i < t; i++)
        {
            int v = connects[location][i].pos;
            int w = connects[location][i].w;
            if (dist[v] > dist[location] + w)
            {
                dist[v] = dist[location] + w;
                if (!visit[v])
                {
                    if (!q.empty() && dist[v] <= dist[q.front()])
                        q.push_front(v);
                    else
                        q.push_back(v);
                    cnt[v]++;
                    if (cnt[v] > n)
                        return -1;
                    visit[v] = true;
                }
            }
        }
    }
    return 1;
}
int main()
{
    cin >> n >> m >> s;
    init(n);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        connects[u].push_back({v, w});
    }
    int change = spfa_slf(n, s);
    if (change == 1)
        for (int i = 1; i <= n; i++)
            cout << dist[i] << " ";
    cout << endl;
    system("pause");
    return 0;
}

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

第一部分 图的概述

第二部分 图的存储方法