图论复习

xjzm · 2024-01-04 13:27:54 · 个人记录

由于我的图论学的实在是太差了，所以进行复习整理；；；

图论

一.图论的概念

图，就是点与点之间用有向边或无向边进行连接的关系。就是将实际问题抽象为连接不同的点的点的关系。

1.无向图，每两个点间只要存在连线就可以双向通行的图。

2.有向图，两点之间的连线存在方向，只能单方向通行。

3.图的度和连通性，图中每一个点都有自己的度，分为入度和出度，入度是以该点为结尾的所有道路的数量，出度是以该点为起点的所有道路的数量。图上所有点都可以互相到达的图是为连通图，否则为非连通图。

二.图的存储

1.邻接矩阵（缺点是内存占用极大）

最简单的存储方式，g[i][j]表示i点和j点之间有没有边进行连接，通常情况下我们需要将g数组初始化为极大值，在进行读入的时候不断更新可链接的位置为1。

邻接矩阵的好处是存图直接且方便，但是由于需要每个点都建立数组，空间占用极大，并且遍历时间复杂度很高，无法判断自环和重边。

2.邻接表

在邻接矩阵的基础上，对空间占用进行优化，将u，v，w存入的动态数组。

有两种方法实现邻接表的处理，分别为vector数组和链式前向星

vector 数组就是动态更新数组大小的数组，在存储的时候我们将u，v,w压入vector进行存储，在遍历的时候从0到n进行遍历。

vector数组板子

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,w;
}; 
const int maxn=1000;
int n,m;
vector<node>a[maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    int u,v,w;
    cin>>u>>v>>w;
    a[u].push_back({v,w});
    a[v].push_back({u,w});
    }
}

链式前向星就是模拟链表进行存储，以每个顶点都为起点。

之前我一直搞不太清楚链式前向星的逻辑，这几天我想了一下，我之前的思路是考虑点与点之间的关系，而链式前向星是以边和边的关系建立链表，每次进去的是边，判断的是起点相同的边而不是点伸出的不同的边。改正就方便理解了。

链式前向星逻辑：

当读入不同的边的时候，如果该起点已经存在其他边，那么就将上一个边作为当前边的nxt，上一个边的head成为当前边，遍历的时候通过nxt关系进行遍历。（其实也就是链表）

链式前向星板子：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int to,nxt,w;
}edge[m];//这个数组表示每个边的终点，下一个边和该边的权值。 
int n,m;//n为节点的数量，m为边的数量； 
int head[n+1],cnt;//head数组记录该边的上一个边，cnt记录边的编号。 
void add(int u,v,w){
    edge[cnt].nxt=head[u];//将上一个边由队头压入第二位； 
    edge[cnt++].to=v;
    edge[cnt].w=w;//建立边的终点和权值。 
    head[u]=cnt;//将当前边设立为队头； 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u,v,w;
    add(u,v,w)//建边  
    }
    return 0;
}

三.图的遍历（连通）

前面写完了邻接矩阵和邻接表的存图方式，接下来我们要分析dfs和bfs两种遍历方式。

1.深度优先搜索遍历（dfs）

在遍历的过程中我们需要从起点开始，遍历每一个节点，当该节点已经被遍历到的时候，我们就对该节点打上标记。如果该节点还可以拓展到其他的未被打上标记的子节点，那么就接着向下搜索，否则返回该节点的父节点进行继续遍历。

深度优先搜索板子(默认使用链式前向星）：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int to,nxt,w;
}edge[m];//这个数组表示每个边的终点，下一个边和该边的权值。 
int n,m;//n为节点的数量，m为边的数量； 
bool vis[n];
int head[n+1],cnt;//head数组记录该边的上一个边，cnt记录边的编号。 
void add(int u,v,w){
    edge[cnt].nxt=head[u];//将上一个边由队头压入第二位； 
    edge[cnt++].to=v;
    edge[cnt].w=w;//建立边的终点和权值。 
    head[u]=cnt;//将当前边设立为队头； 
}
void dfs(int x){
    cout<<x;//输出已经遍历到的节点 
    vis[x]=1;//打标记 
    for(int i=head[x];i;i=edge[i].nxt){//从该点搜索所有可以拓展到的点 
        int y=edge[i].to;  
        if(vis[y]) continue;
        dfs(y);//进入新的未遍历点进行搜索; 
    }
}   
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u,v,w;
    add(u,v,w)//建边  
    }
    dfs(1);
    return 0;
}

2.广度优先搜索遍历（bfs）

同样从起点出发，访问并进入每一个可扩展到且还未扩展的点，继续进行扩展；

广度优先搜索遍历板子（默认使用链式前向星）：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int to,nxt,w;
}edge[m];//这个数组表示每个边的终点，下一个边和该边的权值。 
int n,m;//n为节点的数量，m为边的数量； 
bool vis[n];
int head[n+1],cnt;//head数组记录该边的上一个边，cnt记录边的编号。 
void add(int u,v,w){
    edge[cnt].nxt=head[u];//将上一个边由队头压入第二位； 
    edge[cnt++].to=v;
    edge[cnt].w=w;//建立边的终点和权值。 
    head[u]=cnt;//将当前边设立为队头； 
}
void bfs(int x){
    queue<int> q;//队列 
    q.push(x);//将起点加入队列 
    vis[x]=1;//打标记 
    while(!q.empty()){
    int k=q.front();
    q.pop();//出队 
        for(int i=head[k],i;i=edge[i].nxt){
        int y=edge[i].to;
        if(vis[y]) continue;
        q.push(y);//拓展 
        vis[y]=1;
        }   
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u,v,w;
    add(u,v,w)//建边  
    }
    bfs(1);
    return 0;
}

四.最短路径算法

1.Dijkstra（迪杰斯特拉）算法

迪杰斯特拉的算法逻辑就是不断向前扩展判断点，如果在当前端点可以直接扩展到的另一端点距离小于已有距离，那么就更新其的距离值（有点像bfs不是吗）是一种基于贪心的最短路方案，但是需要注意的是当图中存在负权回路的时候迪杰斯特拉算法不能进行正确判断。

Dijkstra算法板子（以链式前向星为例）

#include<bits/stdc++.h>
using namespace std;
int dist[n+10];//每个点的最短距离 
int min;
bool vis[n+10];//这个点是否已经作为中间点查询过 
struct node{
    int to,nxt,w;
}edge[m];//这个数组表示每个边的终点，下一个边和该边的权值。 
int n,m;//n为节点的数量，m为边的数量； 
int head[n+1],cnt;//head数组记录该边的上一个边，cnt记录边的编号。 
void add(int u,v,w){
    edge[cnt].nxt=head[u];//将上一个边由队头压入第二位； 
    edge[cnt++].to=v;
    edge[cnt].w=w;//建立边的终点和权值。 
    head[u]=cnt;//将当前边设立为队头； 
}
void dijkstra(int s){
    memset(dist,0x3f,sizeof(dist));//将dist数组初始化为最大值防止调用错误
    dist[s]=0;//当前位置的距离为0，即s到s的距离 
    vis[s]=1;//打标记
    for(int i=1;i<=n;i++){
    min=0x3f3f3f;//最大值初始化；
    int tmp=0; 
        for(int j=1;j<=n;j++){
            if(!vis[j]&&min>dist[j]){//寻找dist数组中还没作为0点的最小值； 
                min=dist[j]; 
                p=j;
            }
            vis[p]=1;//打标记； 
            for(int j=head[p];j;j=edge[j].nxt){//更新最短距离； 
                int v=edge[j].to;
                if(!vis[v]&&dist[v]>dist[p]+edge[j].w) dist[v]=dist[p]+edge[j].w;
                //如果该位置的距离大于从当前点走另外一条路径，则直接选择当前点的路径。 
            }   
        }
    }
} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u,v,w;
    add(u,v,w)//建边  
    }
    return 0;
}

Bellman-Ford（贝尔曼福德）算法

在前面介绍迪杰斯特拉算法的时候我们发现迪杰斯特拉算法是不可以处理负权回路情况的，这个时候我们就需要用贝尔曼福德算法来解决单源负权最短路情况。

贝尔曼福德的算法逻辑是不断更新vi，更新条件是

dist[i]+w(vi,vj)<dist[j]

这种操作我们称之为松弛操作，基于dp思想的来。因为下一个阶段的距离肯定由上一个节点和上一个的节点到这个节点的边权构成的，所以可以进行动态规划。

这种松弛操作就是贝尔曼福德算法的核心。