图论2021版

标签：图论 int 路径算法 MAXN 2021 include dis

图

基本概念
图可以理解成一个二元组，是由点集V和边集E组成的。
G=(V, E)，V表示点的集合，E表示边的集合。
每条边是一幅点对(v,w) v,w都是点集V中的点。(v,w∈V)

图的分类：可以按照边有无方向，可以分为有向图和无向图。
比如上图1中，边AB之间没有画出方向（即点之间是无序的），这就是无向图。
无向图：每条边都是无向的图为无向图
有向图：每条边都是有向的图为有向图

图的分类：可以按照边的数量分为，简单图和多重图
简单图：在无向图中，任意2点间只有1条边；在有向图中，任意2点间只有1条同向边
多重图：在无向图中，任意2点间不只有1条边；在有向图中，任意2点间不只有有1条同向边

图的度
在无向图中，与这个结点相连的边的个数，称为结点的度。比如在图1中，X的度数为4
在有向图中，结点的度分为入度和出度。
结点的入度：以这个结点为终点的有向边的个数
结点的出度：以这个结点为起点的有向边的个数
性质：图的总度数=边数*2

连通
无向图中：从任意点，都存在到达其它点的路径，称为连通图。
有向图中：从任意点，都存在到达其它点的路径，称该有向图是强连通的。

子图
对于图G和图G’,如果图G’ 的边集和点集都是图G的边集和点集的子集，那么图G’是图G的子图

导出子图
对于图G和图G’,如果图G’ 的点集都是图G点集的子集，那么图G’是图G的导出子图，其边集不一定是图G边集的子集。

补图
对于图G和图G’，如果2个图的点集相同，边集没有交集，并且边集为完全图的边集，那么图G和图G’ 互为补集。

其它概念
权值：边的“费用”，可以看成是边的长度
回路：起点和终点相同的路径，称为“回路”，或者“环”
完全图：无向图中，如果任意两点之间都存在一条边，则是一个无向完全图，无向完全图有n(n-1)/2条边；有向图中，如果任意两点之间都存在互通的两条边，则是一个有向完全图，有向完全图有n(n-1)条边。
稠密图：边数接近于完全图的图
稀疏图：边数远远少于完全图的图
强连通分量：有向图中任意两点都连通的最大子图。
存储方式
邻接矩阵：int $G[i][j]$; //$G[i][j]$表示从点$i$到点$j$的权值，定义如下

G[i][j]  有边  没有边
有权图     权值   正无穷
无权图       1       0

邻接表：邻接矩阵存储的缺点在于，当图是稀疏图时，邻接矩阵的存储效率很低。为此，我们图有另外一种存储方式，邻接表。
无权图

vector<int> g[MAXN];
g[i].push_back(j);//i→j 存在有向边
//g[j].push_back(i); 如果是无向图，该代码也得加上。
#include <vector>
vector<int> G[5];
G[0].push_back(1);
G[1].push_back(3);
G[2].push_back(1);
G[3].push_back(0);
G[3].push_back(2);
G[4].push_back(3);

有权图

struct edge{
  int to;
  int w;
}
vector<edge> g[MAXN];
g[i].push_back((edge){j,w});//i→j 存在有向边,权值为w
g[j].push_back((edge){i,w});//如果是无向图，该代码也得加上。

Floyd 最短路径问题

单源最短路径问题：给定一个有权图G=(V,E)和一个特定顶点S作为输入，找出S和G中每一个其他顶点的带权最短路径。
多源最短路径问题：求出所有结点对的最短路径问题。
Floyd 算法
Floyd算法是多源最短路径算法。时间复杂度为O(n^3)
弗洛伊德算法的思想是，如果我要求出从点i到点j之间的最短路径的距离，如果不能直接到达的话，我可以从中间选择出一个中转点k，先求出从点i到点k的最短距离
dis[i][k]，以及点k到点j的最短距离dis[k][j]，
如果dis[i][k]+dis[k][j] < dis[i][j]，则我们可以更新dis[i][j]为dis[i][k]+dis[k][j]。

首先我们需要把存在直连边的两点之间的距离置为两点之间的边的权值，不存在直连边的两点之间的距离置为无穷大。然后通过三重循环实现了这个算法

参考代码

memset(dis, 0x3f, sizeof(dis));
for(int i=1; i<=m; i++)
    dis[u][v] = dis[v][u] = w;
for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(dis[i][k]+dis[k][j]<dis[i][j])
                dis[i][j] = dis[i][k]+dis[k][j];

这里k这重循环枚举的是中转点。必须放在最外层。
表示的含义是，当前k个点作为中转点时，任意两点之间能求出的最短距离。

Dijkstra(未优化)

Dijkstra算法(未优化)

Dijkstra算法是用来处理单源最短路径的算法，即起点只有一个的最短路径问题。
并且Dijkstra算法不能处理存在负权边的最短路径问题。
算法的时间复杂度为O(N^2)。
引理：
一个点的最短路径必然在是其需要经过的中转点的最短路径的基础上得到的。
算法实现参考代码

int n;
int cost[MAXN][MAXN];
bool found[MAXN];
int dis[MAXN];
void Dijkstra(int s) {
    memset(found, false, sizeof(found));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    while(true) {
        int u = -1;
        for(int i=1; i<=n; i++)
            if(!found[i]&&(u==-1||dis[i]<dis[u])) 
                u = i;
        if(u==-1)   return;
        found[u] = true;
        for(int i=1; i<=n; i++) 
//          if(cost[u][i]<INF) 
                dis[i] = min(dis[i], dis[u]+cost[u][i]);
    }
}

Dijkstra堆优化 Dijkstra算法优化原理

当Djikstra未优化时，时间大部分花在查找更新为蓝点的白点上了。
因此可以借助堆（优先队列）来优化下一次更新的白点的过程。
堆的本质是一个二叉树（二叉树的查找最小值为O(1)，删除和插入为O(logn)）
优化的方式是将最短距离用小根堆进行维护。查找更新的白点的过程时间复杂度为O(logn)
综上时间复杂度可以降为O(nlogn+E)，可以近似看为 O(Elogn)，这样时间复杂度就大大降低了。
Dijkstra的堆优化辅助工具
Dijkstra的堆优化需要用到priority_queue(堆)和pair
每次需要从白点中挑选一个距离最小的白点，需要知道每个点的最短距离以及点的编号，此时用pair存储。
而优先队列里每次需要先比较距离，因此在放入pair时，距离放在编号前面。

typedef pair<int,int> P;//距离，编号
priority_queue<P,vector<P>,greater<P> > q;//定义一个小根堆，类型是P 优先比较距离

此时就可以对Dijkstra进行堆优化了
pair
头文件

#include<vector>

用法用来存储一对相关的数据，实现方式是结构体的方式
写法：pair<type1,type2> p;
type1,type2是数据类型，p是变量名
p=pair<type1,type2>(a,b); a是type1类型的，b是type2类型的。
p.first 表示a， p.second 表示b
可以比较大小，优先比较p.first,再比较p.second
pair用起来不是很方便，比较长，这时候可以借助typedef 给类型名起别名

typedef pair<int,int> P;//pair<int,int> 起了一个别名P

即:

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef pair<int,int> P;
P p1,p2; 
int main(){
    p1=P(1,2);
    p2=P(2,3);
    printf("(%d,%d)\n(%d,%d)\n",p1.first,p1.second,p2.first,p2.second);
    if(p1>p2){
        printf("(%d,%d)>(%d,%d)\n",p1.first,p1.second,p2.first,p2.second);
    }
    else{
        printf("(%d,%d)<=(%d,%d)\n",p1.first,p1.second,p2.first,p2.second);
    }
    return 0;
}

参考代码

typedef pair<int,int> P;//距离，编号
struct edge{
    int to, w;
}; 
vector<edge> g[MAXN];
int dis[MAXN];

void dijkstra(int s){
    memset(dis,0x3f,sizeof(dis));
    //fill(dis,dis+MAXN,INF);
    dis[s]=0;
    q.push(P(0,s));
    while(!q.empty()){
        P t=q.top(); q.pop();
        int u=t.second;//编号 
        if(d[u]<t.first) continue;
        // 小根堆里的队首元素 是最小值，如果满足此条件说明已经被更新过了，就不需要再更新。 
        for(int i=0;i<g[u].size();i++){
            edge e=g[u][i];
            if(dis[e.to]>dis[u]+g[u][i]){
                dis[e.to]=dis[u]+g[u][i];
                q.push(P(dis[e.to],e.to));
            }
        }
    }
}

Prim

最小生成树问题

n个点，以及n个点之间存在若干条权值不同的边，权值表示建这条边的代价。
现在求应该选哪些边，可以使得n个点连通，并且总花费最小。
定理: n个点，n-1条边的无向连通图，一定是树。
在一个图上生成出的树叫做这个图的一个生成树，边的权值之和最小的生成树叫做这个图的最小生成树。
Prim算法
首先把所有点分为两类：蓝点和白点
已经选入最小生成树中的点: 蓝点
还没有选入最小生成树中的点:白点
初始化随机一点到最小生成树的距离为0，其它点到最小生成树的距离为inf
每次从白点的集合中挑选出距离已有的最小生成树距离最近的白点，加入最小生成树中
直到所有点都被加入最小生成树
Prim算法模板

 int MST_prim(){
    int ans=0;
    memset(dis,0x3f,sizeof(dis));
    memset(found,false,sizeof(found));
    dis[1]=0;
    while(1){
        int u=-1;
        for(int i=0;i<=n;i++){
            if(!found[i]&&(u==-1||dis[i]<dis[u])){
                u=i;
            }
        }
        if(u==-1) break;
        found[u]=true;
        ans+=dis[u];
        for(int i=0;i<=n;i++){
            if(!found[i]&&g[u][i]<dis[i]){
                dis[i]=g[u][i];
            }
        }
    }
    return ans;
}

拓扑排序

拓扑排序算法思想
从DAG图中选择一个没有前驱的顶点并输出
从图中删除该顶点和以该顶点为起点的有向边。
重复1、2，直到当前的DAG为空，或者当前图中不存在有前驱的顶点为止。如果最终图不为空，则必然存在环。
参考代码

int n,m;
vector<int> g[MAXN];
queue<int> q;
int f[MAXN],in[MAXN];

void Topsort(){
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int t=q.front();
        cout<<t<<" ";
        q.pop();
        for(int i=0;i<g[t].size();i++){
            int idx=g[t][i];
            if(--in[idx]==0){
                q.push(idx);
            }
        }
    }
}

欧拉路径

若图$G$中存在这样一条路径，使得它恰通过$G$中每条边一次，则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉回路
我们定义奇点为度为奇数的点，对于存在欧拉路径的图，有以下两个定理：

存在欧拉路径的充要条件：图是连通的，有且只有$2$个奇点

存在欧拉回路的充要条件：图是连通的，有$0$个奇点

找欧拉路径（回路）的算法是深搜,时间复杂度为深搜的时间复杂度（邻接矩阵：$O(n^2)$；邻接表：$O(n+m)$）
参考代码

通过上面两个图，发现深搜时先序记录是不对的，只能后序遍历
代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#define MAXN 5010
using namespace std;
int n,m,start;//start是起点 
bool g[MAXN][MAXN];//此图用邻接矩阵存储 
int degree[MAXN];//每一个点的度 
int path[MAXN],cnt;//记录路径 
void find(int x){
    for(int i=1;i<=n;i++){
        if(g[x][i]){
            g[x][i]=g[i][x]=false;//该图是无向图 
            find(i);
        }
    }
    path[++cnt]=x;//记录当前路径，后序记录路径 
    //注意：只能后序记录，不能先序记录！先序记录是不对的！ 
    //这是因为，如果遇到分叉口，先序遍历的话，一旦走错，就凉了！ 
}
int main(){
    scanf("%d %d",&n,&m);//n为点的个数，m为边的数量 
    for(int i=1;i<=m;i++){//输入的时候处理度的问题 
        int x,y;
        scanf("%d %d",&x,&y);
        g[x][y]=g[y][x]=true;
        degree[x]++;
        degree[y]++;
    }
    for(int i=1;i<=n;i++){
        if(degree[i]%2==1){
            start=i;//存在奇点，以这个点为起点 
            break;
        }
    }
    if(start==0)//没有奇点 
        find(1);//从任何一个点开始均可 
    else//有两个奇点 
        find(start);//从一个奇点开始，到另一个奇点结束 
    for(int i=cnt;i>=1;i--){//如果题目要求你按字典序输出，需要逆序输出 
        printf("%d ",path[i]);
    }
    return 0;
}

哈密尔顿回路

定义：不重复地走过所有的点，最后回到起点的路径
哈密尔顿回路的求法就是搜索（填数问题），没有更好的方法（邻接矩阵：$O(n^2)$；邻接表：$O(n+m)$）

参考代码

#include <iostream>
using namespace std;
int n, m, g[105][105], ans[105];
bool vis[105];
bool dfs(int x, int t) {
    if(t>n) {
        if(g[x][1])    return true;
        return false;
    }
    for(int i=1; i<=n; i++) {
        if(g[x][i] && !vis[i]) {
            ans[t] = i;
            vis[i] = true;
            if(dfs(i, t+1))    return true;
            vis[i] = false;
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    int u, v;
    for(int i=1; i<=m; i++) {
        cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }
    ans[1] = 1;
    vis[1] = true;
    if(dfs(1, 2)) {
        for(int i=1; i<=n; i++)
            cout << ans[i] << ' ';
        cout << ans[1];
    }
    else    cout << "NO";
    return 0;
}

Kruscal算法

Kruscal算法将一个连通块当做一个集合
Kruscal首先将所有边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于$n$个独立的集合
然后按顺序从小到大枚举每一条边。如果这条边连接着两个不同的集合，那么久把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一个集合，就跳过
直到选取了$n-1$条边结束
参考代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
struct edge{
    int u,v,cost;
    bool operator<(const edge &tmp)const{
        if(cost!=tmp.cost)
            return cost<tmp.cost;
        if(u!=tmp.u)
            return u<tmp.u;
        return v<tmp.v;
    }
}e[20010];
int fa[5010];
void init(){
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int find(int x){
    if(x==fa[x])
        return x;
    return fa[x]=find(fa[x]);
}
bool same(int x,int y){
    return find(x)==find(y);
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    fa[y]=x;
}
int Kruscal(){
    int MST=0;
    init();
    sort(e+1,e+1+m);//e为边集 
    for(int i=1;i<=m;i++){
        if(same(e[i].u,e[i].v)){
            unite(e[i].u,e[i].v);
            MST+=e[i].cost;
        }
    }
    return MST;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].cost);
    printf("%d",Kruscal());
    return 0;
}

$Bellman-Ford$算法

$Bellman-Ford$算法解决的是一般情况下的单源最短路径问题，在这里，边的权值可以为负数
$Bellman-Ford$算法返回一个布尔值，以表明是否存在一个从原点可以到达的权值为负数的环。
如果存在这样的环，算法将告诉我们不存在解决方案。如果没有这种环存在，算法将给出最短路径和它们的权值
算法执行$n-1$次，每次遍历边集，至少会找到一个点，使得新的最短路径比原来的更小

伪代码

for i from 1 to n-1: //算法需要重复执行n-1次
    for j from 1 to m: //遍历每一条边
        if dis[e[j].u]+e[j].w<dis[e[j].v]: //这个if操作叫做松弛
            dis[e[j].v]=dis[e[j].u]+e[j].w
for j frome 1 to m: //再次执行一次算法
    if dis[e[j].u]+e[j].w<dis[e[j].v]: //此时所有的点的最短路径都算出来了
        return false //如果有边还能松弛，则有负环
return true //没有负环

通过伪代码可以看出，$Bellman-Ford$的时间复杂度为$O(nm)$，完全劣于$Dijkstra$算法的$O(n^2)$时间复杂度（也劣于优化的$O(m \log n)$时间复杂度）

模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int n,m,st,dis[1010];
struct edge{
    int to,cost;
};
vector<edge> g[1010];
bool Bellman_Ford(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<g[j].size();k++){
                //两层循环遍历整个邻接表 
                edge e=g[j][k];
                if(dis[j]+e.cost<dis[e.to])
                    dis[e.to]=dis[j]+e.cost;
            }
        }
    }
    for(int j=1;j<=n;j++){
        for(int k=0;k<g[j].size();k++){
            //两层循环遍历整个邻接表 
            edge e=g[j][k];
            if(dis[j]+e.cost<dis[e.to])
                return false;
        }
    }
    return true;
    //时间复杂度为O(nm)，劣于Dijkstra 
}
int main(){
    cin>>n>>m>>st;
    for(int i=1;i<=n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back((edge){v,w});
    }
    if(Bellman_Ford(st)){
        for(int i=1;i<=n;i++)
            cout<<dis[i]<<" ";
    }
    else{
        cout<<"No";
    }
    return 0;
}

$Bellman-Ford$ 队列优化——$SPFA$

$SPFA$是$Bellman-Ford$算法的一种队列实现，减少了不必要的冗余计算
主要思想初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束
这个算法，利用了每个店不会更新次数太多的特点发明的
$SPFA$在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点除了队列就不可能重新进入队列，但是$SPFA$中一个点可能在出队列之后再次被放入队列，也就是说一个点修稿过其它的点之后，过了一段时间可能会获得更短的路径，于是再次用来修改其它的点，这样反复进行下去
时间复杂度：$O(k \cdot m)$，$m$是边的数量，$k$是一个常数（不好分析），平均值为$2$
核心代码

struct edge {
    int nxt, w;
};
queue<int> q;
int dis[1005];
bool exist[1005];//判断一个点是否已经加入了队列中 
void SPFA(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(exist, false, sizeof(exist));
    dis[s] = 0;
    q.push(s);
    exist[s] = true;
    while(!q.empty()) {
        int h = q.front();
        q.pop();
        exist[h] = false;
        for(int i=0; i<g[h].size(); i++) {
            edge e = g[h][i];
            if(dis[e.nxt]>dis[h]+e.w) {
                dis[e.nxt] = dis[h]+e.w;
                if(!exist[e.nxt]) {
                    q.push(e.nxt);
                    exist[e.nxt] = true;
                }
            }
        }
    }
}

标签：图论,int,路径,算法,MAXN,2021,include,dis
From： https://www.cnblogs.com/hzy-ygkl/p/17189685.html

伪代码

模板

相关文章

赞助商

阅读排行