基本图论

sLMxf · 2023-08-26 11:15:41 · 个人记录

1. 图的一些基本概念

图：简单来说，是由一些顶点用边连接的一个图。（例如地图上的各个点都是用边连起来的）
顶点：图中的数据元素。
边：顶点之间的逻辑关系,表示为 (v_i,v_j)。

2. 有向边和无向边、有向图和无向图

有向边：
从字面理解，就是边有方向。例如 a\to b 表示 a 到 b 有一条边，但只能从 a 走到 b，不能从 b 走到 a。
无向边：
同理，就是边没有方向，例如 (a,b) 之间有一条无向边，那么 a 可以走到 b，b 也可以走到 a。
有向图：
只用有向边的图叫有向图。
无向图：
只用无向边的图叫无向图。

3. 完全图、稀疏图、稠密图

完全图
字面就看得出来，完全图就是每个点跟其他所有点都有边连着。
完全图有一个性质：n 个点的完全图有 (n-1)+(n-2)+\cdots+3+2+1=\dfrac{(n-1+1)\times(n-1)}{2}\approx n^2 条边
稀疏图和稠密图
稀疏图和稠密图没有标准的定义，你可以理解为稀疏图边较少，稠密图边较多。

4. 例题：可莉的难题

这题很多人以为要存图，实际上是玩你的。
断开第一个点需要炸掉 n-1 条边
断开第二个点需要炸掉 n-2 条边

\cdots\cdots

最后这道题的答案为 (n-1)+(n-2)+(n-3)+\cdots+(n-k+1)。

5. 权值、度

权值
权值分为点权和边权，很简单，点权代表点 i 代表了一个 xxx，边权同理。
度
无向图顶点的边数叫度，有向图顶点的边数叫出度和入度。

6. 邻接矩阵

建立
用一个二维数组 a_{i,j} 表示。
输入
例如：有一个 n 个点、m 条边的无向图，每次给定输入 i,j，表示 i\to j 有一条无向边。请将它存下来。
很容易写出代码：
```
cin>>n>>m;
for(int i=1;i<=m;i++)
{
       int x,y;
       cin>>x>>y;
       a[x][y]=1;
}
```
但这样写是错误的，因为你只存了 a_{i,j}，而 j\to i 也应该是有一条边的。（一条无向边相当于两条有向边）。所以正确代码应是：
```
cin>>n>>m;
for(int i=1;i<=m;i++)
{
       int x,y;
       cin>>x>>y;
       a[x][y]=1;
       a[y][x]=1;
}
```

7. 邻接表

建立
前置芝士：vector
邻接矩阵对于稀疏图还是太浪费空间了，我们一般用vector为基础的邻接表。
建立的方式很简单：vector<int> a[1001];

输入
a[x]表示点 x 能到的所有边。
那么输入代码：

cin>>n>>m;
for(int i=1;i<=m;i++)
{
       int x,y;
       cin>>x>>y;
       a[x].push_back(y);
       a[y].push_back(x);
}

a[x][y] 表示点 x 到点 a[x][y] 有一条边。

8. 邻接矩阵和邻接表的优点和缺点

用了一个表来表示：

图的类型	优点	缺点
邻接矩阵	好写、查询时间为 O(1)	浪费空间
邻接表	节省空间	理解较难、查询时间为 O(n)

9. 例题：图的存储、图的存储与出边的顺序

$\text{AC}$ 记录2：[link](https://www.luogu.com.cn/record/119414407) ### 10. 遍历图上遍历分两种：DFS、BFS，这里都说一下： - DFS 前置芝士：DFS 图上DFS并没有什么特殊的：就是将所有节点可以直接到达的点枚举。注意一下边界即可。接下类给出模板： ```cpp void dfs(int x) { if(x到达边界) return; for(int i=0;i<a[x].size();i++) { ... dfs(a[x][i]);//遍历 ... } } ``` - BFS 前置芝士：BFS 图上BFS和BFS差不多，先将一些点压入队列，然后每次弹出，将它的相邻节点全部压入队列。接下来给出模板： ```cpp for(int i=1;i<=n;i++) if(a[i]符合要求) q.push(i); while(!q.empty()) { int u=q.front();q.pop(); if(u到达边界) continue; for(int i=0;i<a[u].size();i++) { ... q.push(u); ... } } ``` ### 11. 图的一些其他术语 - 环分为自环和环。自环：自己到自己有一条边环：一条只有第一个和最后一个顶点重复的非空路径 - 重边可以理解为两个点之间不只有一条直接路径，这些重复的直接路径为（一组）重边。 - 简单图不含环与重边的图。 - 反图可理解为取反所有边方向。（例如本来是 $i\to j$，改成 $j\to i$） ### 12. 有向无环图有向无环图（Directed Acyclic Graph），简称DAG 定义：是一张有向图，并且没有**环**的一张图。对一张有向无环图，求最短路算法为 $O(n+m)$。先拓扑排序，再将方程改为 $dis_u=\min(dis_u,dis_v+dis_{v,u})$ 即可。 ### 13. 练习 - 建议 - [高手去散步](https://www.luogu.com.cn/problem/P1294) - [漂浮的鸭子](https://www.luogu.com.cn/problem/P5145) - [图的遍历](https://www.luogu.com.cn/problem/P3916) ### 14. Floyd-多源最短路算法 - 多源最短路模板 [题目传送门](https://www.luogu.com.cn/problem/B3647) Floyd运用的是DP的思想。假设有两个点 $x,y$，我们只有两种走法： 1.直接从 $x$ 点走向 $y$ 点。那么可以得到方程 `f[x][y]=a[x][y]`。 2.先从 $x$ 点走向 $z$ 点，再从 $z$ 点走向 $y$ 点。那么可以得到方程 `f[x][y]=f[x][z]+f[z][y]`。最后取最小值便可，核心代码实现：时间复杂度 $O(n^3)

   for(int k=1;k<=n;k++)
                 for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

传递闭包
题目传送门
传递闭包是Floyd一个重要的应用。
和Floyd一样，每两个点要不直接可以通过，要不通过其他点联通。
所以状态转移方程变为 f[x][y]=f[x][y]|(f[x][k]&f[k][y])

15. Dijkstra-单源最短路算法

松弛
后面的算法需要松弛操作。松弛操作就是更新为点 s 到点 i 的最短路和点 s 到 j，再从 j 到 i 的最短路。即 dis_i=\min(dis_i,dis_j+e_{i,j})。
暴力
题目传送门
这题Floyd会炸。考虑用别的算法。
建立两个数组，dis[i],vis[i]，分别表示点 s 到点 i 的最短路，是否经过点 i。
一开始将所有到点 s 的最短路设为 \infty，当然，从 s 点到 s 点的最短路为 0。
接着，每次将没有经过的（即 vis[i]=0 的i）中选一个 dis[i] 最小的点，将他和他所有能直接到达的点进行松弛操作。
重复上列操作，直到遍历完所有点。
时间复杂度 O(n^2+m)，核心代码如下：
```
for(int i=1;i<=n;i++)
{
      int u=-1,minn=dis[0];
      for(int v=1;v<=n;v++)
          if(!vis[v]&&dis[v]<minn) minn=dis[v],u=v;
      if(u==-1) break;
      else vis[u]=1;
      for(int v=0;v<a[u].size();v++)
      {
          node z=a[u][v];
          dis[z.to]=min(dis[z.to],dis[u]+z.v);
      }
}
```
优先队列优化
题目传送门
我们发现，找最小的 dis 的这个操作，可以使用优先队列。
开始现将所有 s 插入优先队列，每次取队头，进行松弛。
但是我们会发现一个问题，可能队列里同时出现两个相同的数据。
但没有办法，只能插入两个相同的。
由于最多队列里会有 m 个数据，所以时间复杂度为 O(m\log m)
```
dis[1]=0;
q.push((node){1,0});
while(!q.empty())
{
         node u=q.top();
         q.pop();
         int x=u.x,v=u.v;
         if(vis[x]) continue;
         vis[x]=1;
         for(int i=0;i<a[x].size();i++)
         {
            node z=a[x][i];
             if(dis[z.to]>dis[u]+z.v) q.push((node){z.to,dis[u]+z.v});
          }
}
```

16. 拓扑排序

拓扑排序例题：B3644
这题一看就是DAG(有向无环图)
我们知道，必定要先列出祖先。祖先的入度一定为 0，不然就还会有祖先先输出。
那么新建一个队列，每一次将入度为 0 的点压入队列。
每弹出一个点，就将他所有可出去的儿子的入度 -1，或者说删除这个点。还要将他压入队列。
队列为空时结束。
时间复杂度：由于顶多经过每个点一次，每条边一次，所以时间复杂度为 O(n+m)。
核心代码：

for(int i=1;i<=n;i++) if(r[i]==0) q.push(i);
while(!q.empty())
{
        int u=q.front();q.pop();
        for(int i=0;i<a[u].size();i++)
        {
            int v=a[u][i];
            r[v]--;
            if(r[v]==0) q.push(v);
        }
        ans[++cnt]=u;
}

17. 最小生成树

定义
一个数的最小生成树是边权和最小的生成树。

Kruskal
为了让生成树最小，考虑每次选择最短的边。
但是，如果两个点已经连通，再连就没有意义了，故需要一个并查集来维护（你不要告诉我你不会并查集）。代码如下：

int Kruskal(int m,int n,node a[])
{
  int sum=0,flag=0,number=0;
  sort(a+1,a+1+m,cmp);
  for(int i=1;i<=m;i++)
  {
      int fau=find(a[i].u),fav=find(a[i].v);
      if(fau==fav) continue;
      fa[fau]=fav;
      sum+=a[i].c;
      number++;
      if(number==n-1)
      {
          flag=1;
          break;
      }
  }
  if(flag) return sum;
  else return -1;
}

注意要对并查集初始化。