图论初步&&最短路

Part 1:什么是图??

A:图是指由m个点,n条边组成的数据结构,分为有向图和无向图两种,其中有向图是指"1-->3" 而无向图是"1--3",在存图是会有不同(有向图只需存一遍,而无向图需要反向存一遍(a[i][j]=a[j][i]=val;))

Part 2:如何存图??

A:有三种方式可以用来存图,分别是邻接矩阵(数组模拟),邻接表(数组模拟),Vector存图;

代码也很简单:

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 5005;
int mapp[maxn][maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]==0x7f7f7f7f;
        }
    }
    for(int i=1;i<=n;i++)
    {
        a[i][i]=0;
    }
    for(int u,v,val;m;m--)
    {
        mapp[u][v]=val;//从u到v的权值为val
        //mapp[u][v]=val; 无向图; 
    }
 } 
邻接矩阵

#include<iostream>
using namespace std;
struct Node{
    int u;//边的起点
        int v;//边的终点
        int w;//边的权值
    int next;//边的上一条边（用于连接）
}e[/*边的最大条数*/];    
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int u,v,w;m;m--)
    {
        int i=1;
        scanf("%d%d%d",&u1,&v1,&w1);
        e[i].u =u1;//赋给第i条边的起点        
        e[i].v =v1;//赋给第i条边的终点
        e[i].w =w1;//赋给第i条边的权值
        e[i].next =head[u1];//现在这条边的上一条边=现在这条边的起点的上一条边（u1是起点） 
        head[u1]=i;//于是，对于以后的边来说，现在这条边就是起点的上一条边 
        i++;
    }
}
​
邻接表

还有重头戏 利用STL中的Vector进行存图

#include<vector>
#include<cstdio>
using namespace std;
struct EDGE
{
    int to;//终点
    int cost;//边的权值
};
vector<EDGE>G[maxn];//G[i]中i表示出发点
int main()
{
    int m;//路径数 
    int temp1;//起点 
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        EDGE e;
           scanf("%d%d%d",&temp1,&e.to,&e.cost);//输入出发点，终点，边的权值
          G[temp1].push_back(e);//将数据压入动态数组，表示在这个出发点下引出的边
           //相当于二维动态数组
    } for (int i=1; i<=n; i++) //按照出发点的顺序遍历
    {
        for(int j=0; j<G[i].size(); j++) //遍历出发点所引出的边
        {
            EDGE e=G[i][j];//1以二维数组形式输出
            printf("from %d to %d,the cost is %d\n",i,e.to,e.cost);
        }
    }
    return 0;
}
​
vector存图

Part 3:最短路问题

图已经存好了,接下来就是利用c++语言来求解问题了.

其中最经典的问题当然就是如何求最短路了;

1. Floyd 求多源最短路;

2. Dijkstra 求单源最短路;

3. 队列优化后的Bellman-Ford(天朝oiers称作SPFA)

三种代码按照顺序一一介绍,

首先是 Floyd:

这是一种O(n^3)的算法,原理：对每一个中间节点k做松弛（寻找更短路径）；

但它适合算多源最短路径，即任意两点间的距离。

但spfa，迪杰斯特拉就只能算一个点到其他任一点的最短路径。

k不单单是枚举，还是一个状态变量，找i和j之间通过编号不超过k（k从1到n）的节点的最短路径（一定要注意，这里是当前最短路径，

k之前的已经变成最短路了,对于每一个k，我们都进行了n^2的充分枚举(ij)，已保证当前已经满足对从1到k的节点最优，

那么当k枚举完所有点，那么一定是最优的了

for(k=1;k<=n;k++) //中转节点 
     for(i=1;i<=n;i++) //第二层循环
         for(j=1;j<=n;j++)  //第三层循环
                if(e[i][j]>e[i][k]+e[k][j] )//如果直接到达比通过k这个中转接点到达的距离短   
                     e[i][j]=e[i][k]+e[k][j];//那么就更新松弛

Dijkstra算法,

Dijkstra算法基于贪心的思想，每次从dis[ ]数组中取出一个dis[ ]值最小的节点x，把vis[x]标记为true，同时用这个点的所有连边去更新与x相连的点y的dis[ ]值

其中，更新的条件是这样的：（dis[y]=min(dis[y],dis[x]+x->y)）,也就是y的更新后最短路值=min(当前y的最短路值，x的最短路值+x->y的边权)

每次松弛操作，使得1->x,1->y,x->y这三条边满足三角形不等式，扫完x点的所有边之后，此时，没有被访问过且dis值最小的点的最短路就已经被确定了

重复取出dis[ ]值最小节点的操作，更新y的值，直到vis[ ]全部为true，也就是所有节点都被访问过。此时，dis数组中dis[i]就是1->i的最短路

Part 2：优化Dijkstra算法

还记得吗？前面我们提到了在松弛之前，有一个取出dis数组中最小值的操作，对吧？

这个操作的复杂度是O(n)O(n)的，再加上用来更新的for循环，整体复杂度就变成了O(nO(n22))的

显然，O(nO(n22))的复杂度还不够快，那么考虑怎么优化？

很容易想到数据结构对吧？这里我们可以使用一个小根堆来实时维护dis中的最小值和这个最小值所对应的编号，取得最小值所在节点编号的复杂度降低到了O(logn)O(logn)

这样做，使得整体复杂度降低到了O((m+n)logn)O((m+n)logn)（其中m是边数，n是点数）

问题又来了，手写小根堆优化会导致码量的暴增，而且容易出错，我们迫切的需要一种简洁，易实现的代码

当然不，STL中queue头文件为我们提供了priority_queue这样一个大根堆，我们想想，可不可以利用这个大根堆呢？

想要利用priority_queue，首先要解决两个问题：

1、我们需要存下两个变量，一个是dis数组中的值，当做第一关键字入堆，还有这个dis值对应的节点编号，这需要开一个结构体

开结构体又导致另一个问题——priority-queue不知道以谁为关键字入堆排序

2、把优先队列的大根堆形式变成小根堆

“做到这些，需要一些奇技淫巧” ——By 一扶苏一 2020.6.28

解决方法一：重载‘<’运算符

我们重载‘<’号运算符，让priority_queue一dis值为第一关键字的同时，把原来的大根堆变成小根堆

代码如下：

struct node{
    int sp,num;
    bool friend operator < (node a,node b){
        return a.sp>b.sp;
        priority_queue<node>q;
    }
}

这里我们重载了‘<’运算符(PS：对于所有C++STL，需要比较大小的，只要求我们重载‘<’运算符，因为通过‘<’号的定义，可以推至所有别的符号的定义，比如，这里我把‘<’重载为返回sp大的，那么‘>’自然就是返回sp小的),一次性解决了上面的两个问题

解决方法二：C++内置pair二元组

我们可以使用C++内置的二元组pair来解决关键字的问题，因为pair默认以第一维为第一关键字

(PS:pair以第二维为第二关键字，但是这里第二关键字我们并不关心，因为不会影响到dijkstra的结果)

C++内置pair基本用法如下代码：

#include<cstdio> 
#include<iostream>
using namespace std;
int main(){
    pair<int,int>x;//声明二元组的第一维，第二维的数据类型和二元组名字 
    x=make_pair(1,2);//给二元组赋值，先把“1,2”用make_pair()打包，然后分别赋值给第一维和第二维 
    int a=x.first,b=x.second;//分别返回二元组x的第一维，第二维 
    printf("%d %d",a,b);
}

另外，把大根堆变成小根堆，我们可以在入堆的时候把dis值取反(只是在堆中是相反数，dis值保持原样)，这样我们就用pair解决了这两个问题 ----引用自同机房大佬顾昕麟的blog

所以最后优化后的代码如下

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=100010,M=500010;
int head[N],ver[M],edge[M],Next[M],d[N];
bool v[N];
int n,m,tot,s;
priority_queue< pair< int,int > >q;//包含pair的优先队列 
void add(int x,int y,int z){//链式前向星存图 
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
}
void dijkstra(int x){
    memset(d,0x3f,sizeof(d));//把距离初始化无限大 
    memset(v,0,sizeof(v));//初始化没有访问过 
    d[x]=0;//初始节点距离为0 
    q.push((make_pair(0,x)));//初始节点入堆 
    while(q.size()!=0){
        int x=q.top().second;//访问第二维，也就是节点编号 
        q.pop();//弹出 
        if(v[x]==1) continue;//如果走过了，直接进行下一次 
        v[x]=1;//标记访问过 
        for(int i=head[x];i;i=Next[i]){//链式前向星访问连边 
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z){//松弛 
                d[y]=d[x]+z;//更新最短路 
                q.push(make_pair(-d[y],y));//把d[y]的相反数入堆，大根堆变小根堆 
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);//n点m边，s出发点 
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);//读边 
        add(x,y,z);
    }
    dijkstra(s);//求单元最短路 
    for(int i=1;i<=n;i++)
        printf("%d ",d[i]);//输出到每一个节点的距离，如果到不了该节点，输出0x3f3f3f3f
    return 0;
}

SPFA算法

SPFA其实是天朝的OIers对于队列优化后的Bellman-Ford的一种叫法,

声明：以下的三元组(x,y,z)表示点 i ->点 j 有边权值为z，dis[x]表示出发点到编号为x节点距离

算法原理：

给定一张有向图，如果对于图中任意一条边(x,y,z)有 dis[y]<=dis[x]+z 成立，那么称这条边满足三角不等式

如果所有的边都满足三角不等式，则dis[x]就是出发点到x结点的最短路长度

正确性请读者自证（滑稽）

实现方法：

建立一个队列，最初队列里只有初始结点（假设为1）

取出队头节点x，扫描它的所有出边(x,y,z)，如果不满足三角不等式 (dis[y]>dis[x]+z)，更新 dis[y]=dis[x]+z，同时，如果此时 y 点不在队列中，把 y 点入队

重复上面的步骤，直到队列为空（此时所有边都满足三角不等式，得到单源最短路的解）

附代

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define N 101000
using namespace std;
typedef unsigned int unint;//闲的没事的typedef 
struct edge{
    int to,cost;//结构体构建邻接表 
};
vector<edge>v[N];//邻接表 
queue<int>q;//队列 
int dist[N],vis[N],n,m;
void spfa(int s)//s是起点 
{
    memset(dist,0x3f,sizeof(dist));//初始化距离无限大 
    memset(vis,0,sizeof(vis));//所有元素都不在队列里 
    dist[s]=0;//初始化起点距离是0 
    vis[s]=1;//起点在队列里 
    q.push(s);//起点入队 
    while(q.size()!=0)//队列不为空，执行循环 
    {
        int x=q.front();//取出队首 
        q.pop();
        vis[x]=0;//元素不在队列里 
        for(unint i=0;i<v[x].size();i++)//避免Dev警告，强迫症unint 
        {
            int y=v[x][i].to;//x点可以到的结点 
            int z=v[x][i].cost;//边的权值 
            if(dist[y]>dist[x]+z)//不满足三角不等式，进行更新 
            {
                dist[y]=dist[x]+z;
                if(vis[y]==0)//如果y不在队列里，入队 
                {
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
}

BB时间:中高考都已落下了帷幕,成绩什么的也很快就要出来了,如果考得很满意,那就好好放松放松,如果不合心意,也不要太过紧张,一切都是最好的安排,放轻松,开开心心的开始大学(高中)新生活!!!