还有2天就复赛了，现在暂时不知道做啥题了，写一下这两天复习的图论知识。

10.23 闲话 图论复习

还有2天就复赛了，现在暂时不知道做啥题了，写一下这两天复习的图论知识。

1.存图方式

(1.) 邻接矩阵

没什么好说的，最简单的存图方式，一眼就会。

定义矩阵数组 \(a[n][n](n为点的数量数)\) ，\(a[u][v]=w\) 代表 \(u,v\) 之间存在一条权值为 \(w\) 的路径。

由于采用二维数组存图，导致其在稠密图中效率低下，会有很多空间被浪费掉，限制了其发挥。

(2.) \(vector\)

动态数组存图，比较好写也比较常用的一种方式，定义的话为 \(vector<数据类型>a[n](n为点的数量)\) 对于 \(a[u][i]=v\) 来说，其代表点 \(u\) 的第 \(i\) 条边的终点是 \(v\) ，若需存储其权值，则需要改变其数据类型，使用结构体类型。

存储权值的方式以及遍历点 \(i\) 的所有出度的方式。

<code>struct node{

int id,w;

};

vector<node>a[maxn];

//向点u压入一条权值为w的通往v的出度

a[u].push((node){v,w});

for(int j=0;j<a[i].size();j++){

//所有的a[i][j]即为其所有出度

}

比起邻接矩阵存图，其省去了大量的冗余空间存储不存在的边。故其在稠密图的表现明显优于邻接矩阵。

(3.)链式前向星

学的不太好，可能讲起来会比较抽象。

建立结构体数组 \(e[m](m为边的数量)\) 结构体的变量为 \(to(边的终点),next(其同起点的一个兄弟)，w(边的权值)\) ，与一个 \(head\) 数组， \(head[i]\) 表示 \(i\) 点的最近一条连边。

存储方式及遍历方法：

struct edge{

int to,next,w;

}e[m];

int head[n];

void add_edge(int u,int v,int w){ //添加一条由u通向v的权值为w的边

tot++; //tot为当前边的编号

e[tot].to=v; //边的终点

e[tot].next=head[u]; //更新其兄弟

e[tot].w=w;

head[u]=tot; //记录u点的最近一条出度

}

//遍历点x的所有出度

for(int i=head[x];i;i=e[i].next){ //最早的点的next值为0

}

较起前两种，链式前向星由于不用存储起点，只存储边，不由点决定，决定其空间利用率极高，是最省空间的存图方式。

2.拓扑排序

首先阐述其的定义，在一张 \(DAG(有向无环图)\) 中，若 \(i,j\) 存在一条由 \(i\) 指向 \(j\) 的边，则称 \(j\) 依赖于 \(i\) ，则拓扑排序的目的就是使排序后排在前面的点不依赖于后面的点。

可能有点抽象，形象点来说，就是在一张由有向无环图中，输出入度为零的点，同时将其所连的点的入度减一，重复此过程，直到所有的点都已被输出。这也点出了我们的解决思路，队列存储入度为零的点，当队列非空时，每次取出队首，遍历其所有出度，将其能到达的点的入度减一，若减为零，则将其加入队列，否则继续遍历。

int idx[maxn]; //入度数组

vector<int>e[n];

queue<int>qu;

for(int i=1;i<=n;i++){

if(idx[i]==0){

qu.push(i);

cout<<i<<" ";

}

}

while(!qu.empty()){

int op=qu.top();qu.pop();

for(int i=0;i<e[op].size();i++){

int k=a[op][i];

idx[k]--;

if(idx[k]==0){

qu.push(k);

cout<<k<<" ";

}

}

}

3.最短路

很经典的图论问题，也是很常考的知识点。求图上两点的最短路，分为全源最短路及单源最短路两种。

(1.)全源最短路：

全源最短路常使用 \(Floyd\) 算法，其主要思想是通过枚举中继点来缩小路径长度，复杂度为 \(O(n^3)\) 很差，不过相较于对每个点进行一遍寻找单源最短路， \(Floyd\) 算法还是占优势的。

主要采用 \(dp\) 的思想 \(dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])\) 三维数组效率有点低下，所以使用滚动数组，优化掉第一维 \(dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j])\) 当然由于使用了滚动数组的原因，导致枚举 \(k\) 的循环必须在 \(i\) , \(j\) 循环的外层。

void flord(){

for(int k=1;k<=n;k++){

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

}

}

}

}

//则dp[i][j] 为i点到j点的最短路

(2.)单源最短路

这里是 \(dijkstra\) 算法，一种通过贪心来确定最短路的算法。只能用于无负边权值的图。使用优先队列存储点到起点的距离，对于一个已经在优先队列中的点，若期之前未被遍历过，则遍历其所有出度，更新其可到达的点，若更新后距离更短，则更新距离。

struct edge{

int u,v;

int w;

};

vector<edge>e[maxn]; //vector存图

struct node{

int id,dis;

bool operator < (const node &x)const{

return dis<x.dis;

}

}

int dis[maxn]; //dis记录点i到起点的距离

bool vis[maxn]; //vis代表是否已被确定

void dijkstra(){

for(int i=1;i<=n;i++){

dis[i]=inf;

vis[i]=false;

}

dis[s]=0;

priority_queue<node>pq;

pq.push((node){s,0});

while(!pq.empty()){

node u=pq.top();pq.pop();

if(vis[u.id]) continue;

vis[u.id]=true;

for(int i=0;i<e[u].size();i++){

edge k=e[op.id][i];

if(vis[k.v]) continue;

if(dis[k.v]>y.w+u.dis){

dis[k.v]=y.w+u.dis;

q.push((node){k.v,dis[y.v]});

}

}

}

}

4.最小生成树

最小生成树( \(MST\) )，在图上，联通所有点且不含回路的子图称为一颗生成树，其中边权和最小的称为最小生成树。

这里使用 \(kruskal\) 算法,由于需要连接每一个点，所以可以使用贪心的思路，对所有的边进行排序。选出其中较小的，维护一个并查集，存储已经加入最小生成树的点，维护一个点的集合，直到每一条边都已经遍历。

struct node{

int u,v,w; //边集数组u:起点 v:终点 w:权值

}e[maxn];

bool cmp(node a,node b){return a.w<b.w;} //按权值大小排序

int fa[maxn];

int find(int x){

if(fa[x]==x) return x;

return fa[x]=find(fa[x]);

}

void merge(int x,int y){

int f1=find(x),f2=find(y);

if(fa!=f2){

fa[f1]=f2;

}

}

int kruskal(){

for(int i=1;i<=n;i++) fa[i]=i;

int ans=0;

sort(e+1,e+1+m,cmp);

for(int i=1;i<=m;i++){

int u=e[i].u,v=e[i].v;

if(find(u)==find(v)) continue;

merge(u,v);

ans+=e[i].w;

}

return ans;

}

总结

大概先写到这，图论就学到这了，确实不多，还不一定熟练觉得有点悬。

S组复赛祝好。