图论总结

5.13 开始讲图论的，我咕咕咕到了 5.20。。。

图论相对于 DP 和数学期望那块，算是简单的了。感觉就是要多总结多找题感吧。

这里从基础概念开始，总结一些非常非常基础的东西。由于我太菜似乎也总结不出什么深奥的东西/kk。

概念

注：这里是总结了一部分我认为比较重要或者比较难的概念，可能并不全面，全面的图的概念见图论相关概念 - OI Wiki。

图

图（Gragh）是一个二元组 \(G=(V(G),E(G))\)。其中 \(V(G)\) 是点集，\(E(G)\) 是边集。

根据不同的分类标准可以把图分为不同的种类：

按照边是否有边权把图分为无权图和有权图；按照图是否连通分为连通图和非连通图；按照边是否有向分为有向图和无向图……

度数

与一个顶点 \(v\) 相连的边的条数称作该顶点的度数（degree），记作 \(d(v)\)。

对于有向图，一个点的度数又可以分为入度和出度。对于一个点 \(v\)，以该点为终点的边的条数叫点 \(v\) 的入度，以该点为起点的边的条数叫点 \(v\) 的出度。

重边

若 \(E\) 中存在两个完全相同的元素（边）\(e_1,e_2\)，则它们被称作（一组）重边。

生成子图

在图 \(G=(V(G),E(G))\) 中，选一些点和边，若这些点和边构成了一棵树，则这是这些点和边构成了一张生成子图。

连通图/强联通图

在一个无向图上的任意两个点可以互相到达，那么这张图叫做连通图。

在一个有向图上的任意两个点可以互相到达，那么这张图叫做强连通图。

稀疏图/稠密图

若一张图的边数远小于其点数的平方，那么它是一张稀疏图。

若一张图的边数接近其点数的平方，那么它是一张稠密图。

图的存储

图有三种存储方式。

邻接矩阵

方法

定义一个二维数组 \(a_{u,v}\) 表示节点 \(u\) 到 \(v\) 之间是否有边；有边，则 \(a_{u,v}=1\)，反之，则 \(a_{u,v}=0\)。

对于有权图，\(a_{u,v}\) 可以存储 \(u\) 到 \(v\) 的边权。

时间复杂度

查询两点间是否有边：\(O(1)\)。

遍历一个点所有出边：\(O(n)\)。

遍历整张图：\(O(n^2)\)。

空间复杂度：\(O(n^2)\)。

优点

可以在 \(O(1)\) 的时间里查询两点间是否有边。

缺点

1. 只适用于图无重边的情况；

2. 对于点数较多的图，空间复杂度太大，无法接受；

3. 遍历一个点的所有出边和遍历整张图时间复杂度较大，难以接受。

代码实现

int a[maxn][maxn];
for(int i=1;i<=m;i++)//输入 m 条边
{
    int u,v,w;
    u=read();v=read();w=read();//无权图不需要输入 w
    a[u][v]=w;//无权图：a[u][v]=1;
    //无向图：a[v][u]=w;
}

邻接表

使用一个可以作为动态数组的数据结构（vector 或者 basic_string）来存边。

方法

定义 basic_stringedge[maxn]（或 vector），edge[u] 就表示点 \(u\) 所有出边信息。每次遇到一个 \(u,v,w\)，就连边，具体见下方实现代码。

时间复杂度

查询两点 \(u,v\) 之间是否有边：\(O(d(u))\)。

遍历一个点所有出边：\(O(d(u))\)。

遍历整张图：\(O(n+m)\)（\(n\) 是点数，\(m\) 是边数）。

空间复杂度：\(O(m)\)（注意无向图需要开 2 倍空间）。

优点

1. 遍历整张图和遍历一个所有出边的时间复杂度均较小；

2. 空间复杂度较小；

3. 尤其适用于需要对一个点的所有出边进行排序的场合。

4. 适用于稠密图。

缺点

判断两点间是否有边的时间复杂度较大。

代码实现（这里以有向无环图为例）

struct Node{int v,w;}//v 另一个端点，w 表示边权。

basic_stringedge[maxn];

//存边
for(int i=1;i<=m;i++)
{
    int u,v,w;
    u=read();v=read();w=read();
    edge[u]+=Node{v,w};
}
//遍历一个点所有出边
for(Node y:edge[x])
{
    //y.v 即为终点
    //y.w 即为边权
}

链式前向星

由于这玩意写起来太麻烦我实在懒得用。不过为了以后复（重）习（开）还是总结一下吧。

方法

将邻接表换成类链表的形式即可。

对于一个点 \(u\)，定义 \(head_u\) 表示以 \(u\) 为起点的第一条边编号，\(to_u\) 表示当前边的终点，\(nxt_i\) 表示 \(u\) 的第 \(i\) 条边的下一条边的编号，\(cnt\) 表示当前图中总共有多少边。

逆序存边。每次连一条边 \(u,v\) 时：

1. 边数 \(cnt++\)；

2. 将该边的 \(nxt\) 设为原 \(head_u\)；

3. 新的 \(head_u\) 设为当前边数 \(cnt\)；

4. \(to_u\) 设为 \(v\)。

（这里说的比较简略，若想要更加深刻的了解链式前向星或没看懂的，可以移步链式前向星（详解）_Stephencurry‘s csdn的博客-CSDN博客_链式前向星）

时间复杂度：同邻接表时间复杂度。

空间复杂度：同邻接表空间复杂度。

优点

前两条同邻接表。

然而其实我也不知道它有什么其它的优点（至少现在未体会到）。先引（chao）用（xi） OIWiki 的一句话，等日后有所体会再回来补充吧：

优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i 的反边（常用于 网络流）。

缺点

1. 判断两点间是否有边的时间复杂度较大;

2. 不能方便地对一个点的出边进行排序；

3. 写起来显然比前两种麻烦的多（所以用这玩意干啥）。

代码实现

int head[maxn],to[maxn],nxt[maxn];
int cnt;
void add(int u,int v)//连一条从 u 到 v 的边
{
    nxt[++cnt]=head[u];
    head[u] = cnt;
    to[cnt] = v;
}
// 遍历 u 的出边
for(int i=head[u];i;i=nxt[i]) 
{
    int v = to[i];
}

最小生成树

定义

生成树：对于一个无向连通图 \(G=(V,E),n=|V|,m=|E|\)，由 \(V\) 中的全部 \(n\) 个节点和 \(E\) 中的 \(n-1\) 条边构成的无向联通子图叫做图 \(G\) 的一棵生成树。

最小生成树：对于一个无向连通图，其边权和最小的生成树就叫做这个无向连通图的最小生成树（Minimum Spanning Tree），简称 MST。

注：最小生成树存在的前提是无向连通图，非无向连通图没有生成树。（非连通图只有最小生成森林）

Kruskal 算法

基本思想

利用贪心思想。

在任意时刻，都从剩余的边中选出一条权值最小，且该边两个端点不属于同一棵树（不连通），把该边加入 MST 中。

步骤

1. 对于每一个节点单独建立一个并查集；

2. 将图上所有的边从小到大排序；

3. 遍历每一条边。

4. 判断连接这条边的两个节点是否在同一个集合内。

   若不在，则将它们连边，同时加入到一个集合里。

   若在，则 continue。

5. 直到加入 \(n-1\) 条边，即形成了一棵树，结束遍历。

时间复杂度

排序+并查集：\(O(m \log m)\)。

证明

咕咕咕

懒得写（之后补上吧，最近要总结的东西多了点）

代码实现

struct Node{int u,v,w;}e[maxm];//结构体存边
int fa[maxn];//并查集
int n,m,ans;

int find(int x)
{
    if(x!=fa[x])fa[x]=find(fa[x]);
    return fa[x];
}

void add(int x,int y)
{
    x=find(x);y=find(y);
    fa[x]=y;
}

int cmp(Node a,Node b){return a.w

int calc(int a,int b){return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);}
//计算两点间距离
void add(int x)//将一个点加入连通块。
{
    for(int i=1;i<=n;i++)
    {
        if(vis[i])continue;
        if(i==x)continue;
        dis[i]=min(dis[i],calc(i,x));
    }
    vis[x]++;
}

void Prim()
{
    dis[1]=0;
    add(1);
    int T=n-1;
    while(T--)
    {
        int now=0;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&dis[i]

//摘抄我的 P4180 严格次小生成树
struct P{int u,v,w;}e[maxn<<1];
int f[maxn],vis[maxn],fa[maxn][25],tt[5];
int maxx[maxn][25],minn[maxn][25],dep[maxn];
//maxx 表示的是
int n,m,ans,ss;

struct Node{int v,w;};
basic_stringedge[maxn<<1];

int cmp(P a,P b){return a.w=0&&tt[t]==tt[3])t--;
        if(t<0)minn[x][i]=-INF;
        else minn[x][i]=tt[t];
    }
    for(Node y:edge[x])
    {
        if(y.v==fath)continue;
        maxx[y.v][0]=y.w;
        dfs(y.v,x);
    }
}

int lca(int u,int v)
{
    if(dep[u]=0;i--)
    {
        if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}
    }
    return fa[u][0];
}

int query(int x,int y,int val)
{
    int ret=-INF;
    for(int i=20;i>=0;i--)
    {
        if(dep[fa[x][i]]>=dep[y])
        {
            if(val!=maxx[x][i])ret=max(ret,maxx[x][i]);
            else ret=max(ret,minn[x][i]);
            x=fa[x][i];
        }
    }
    return ret;
}

void work()
{
    ans=INFLL;
    for(int i=1;i<=m;i++)
    {
        if(!vis[i])
        {
            int LCA=lca(e[i].u,e[i].v);
            int x=query(e[i].u,LCA,e[i].w);
            int y=query(e[i].v,LCA,e[i].w);
            int kk=max(x,y);
            if(kk!=-INF)ans=min(ans,ss-kk+e[i].w);
        }
    }
    if(ans==INFLL)cout<<-1<

//复制粘贴我 货车运输 的代码。码风可能和现在有所区别。但~~懒得改了~~
int find(int x)
{
    if(x!=f[x]){f[x]=find(f[x]);}
    return f[x];
}

void dfs(int x,int fath,int v)
{
    dep[x]=dep[fath]+1;
    sum[x][0]=v;
    fa[x][0]=fath;
    for(int i=1;i<=20;i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        sum[x][i]=min(sum[x][i-1],sum[fa[x][i-1]][i-1]);
    }
    for(Node y:edge[x])
    {
        if(y.v==fath)continue;
        dfs(y.v,x,y.w);
    }
}

int work(int x,int y)
{
    if(dep[x]=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            ans=min(ans,min(sum[x][i],sum[y][i]));
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    int t=sum[x][0];
    if(fa[x][0]!=y) t=min(t,sum[y][0]);
    return min(t,ans);
}

int main()
{
    memset(sum,0x3f3f3f,sizeof(sum));
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        e[i].x=read();e[i].y=read();e[i].z=read();
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a=find(e[i].x),b=find(e[i].y);
        if(f[a]==b)continue;
        f[a]=b;
        edge[e[i].x]+=((Node){e[i].y,e[i].z});
        edge[e[i].y]+=((Node){e[i].x,e[i].z});
    }
    for(int i=1;i<=n;i++)
    {
        if(f[i]==i)dfs(i,i,100000);
     } 
    int q=read();
    while(q--)
    {
        int x,y;// q 组询问，每次求 x 和 y 路径上最小边权最大值。
        x=read();y=read();
        int X=find(x),Y=find(y);
        if(X!=Y)cout<<-1<<'\n';
        else cout<

for(int i=1;i<=m;i++)
{
    int u,v;
    u=read();v=read();
    edge[u]+=v;
    in[v]++;//in[v] 表示 v 的入度。
}
for(int i=1;i<=n;i++)//将第一轮所有入度为 0 的点入队。
{    
    if(!in[i])q.push(i);
}
while(!q.empty())
{
    int now=q.front();
    q.pop();
    for(int y:edge[now])
    {
        in[y]--;
        if(!in[y])q.push(y);
    }
}

//注意 k 是最外层循环，i 是次外层，j 是内层。
//不能是以 i,j,k 的顺序循环。
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=m;i++)
{
    int u,v,w;
    u=read();v=read();w=read();
    dp[u][v]=min(dp[u][v],w);
}
for(int k=1;k<=n;k++)
{
    for(int x=1;x<=n;x++)
    {
        for(int y=1;y<=n;y++)
        {
            dp[x][y]=min(dp[x][y],dp[x][k]+dp[k][y]);
        }
        dp[x][x]=0;
    }
}