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\) 的所有出度的方式。

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组复赛祝好。