A3阶段 第五课 图

2025年6月28日

学习时长

约1.6小时

难度

A3阶段/CSP-J

标签

数据结构

讲师

王骏峣

图

概念

  1. 图由若干节点和若干节点之间的边构成
  2. 边可能有方向（有向图），也有可能没有方向（无向图）
  3. 边也可能带有权值(带权图)
  4. 度数:无向图中,一个节点连边的条数称作这个节点的度数,有向图中,分为了入度和出度
  5. 入度:将一个节点作为终点的边的条数称为这个节点的入度
  6. 出度:将一个节点作为起点的边的条数称为这个节点的出度
  7. 重边:两个节点之间不止一条边直接相连,那么就称为重边
  8. 自环:一条边的起点和终点一样,造成自环
     注：1.大多数情况:重边可合并,自环可忽略
      2.重边、自环可能有做题的作用

图可以类比为我们生活中的地图,节点就是地点,边就是道路


方便起见,我们接下来用v和E分别表示一张图的点数和边数

图的存储

邻接矩阵

使用一个大小为点集大小的二维数组M,其中M[1][j]记录节点i和节点之间边的信息
 无权图:只保存两点之间是否有边
 带权图:保存两点之间的边权
 无向图:保存的矩阵通常对所有的i,j满足M[i][j]==M[j][i]

邻接矩阵
int M[N][N]; //邻接矩阵
int main()
{
 cin >> n >> m; //读入点数n、边数m
 for(int i = 1;i <= m;i ++)
 {
  cin >> u >> v;//读入无向边<u,v>
  M[u][v] = M[v][u] = 1;
 }
}

邻接表

邻接矩阵有一个很大的问题是需要v2的空间,且需要O(v)的时间找到一个节点的所有出边,这对于稀疏图(E<<V2)来说非常浪费

因此引入邻接表存图,定义vector<int>e其中e[u]保存所有以为端点的边,如果是有向图,则保留以u为起点的边

无向无权图

邻接表
vector<int>e[N]; //邻接表
int main()
{
 cin >> n >> m; //读入点数n、边数m
 for(int i = 1;i <= m;i ++)
 {
  cin >> u >> v;//读入无向边<u,v>
  e[u].push_back(v);
  e[v].push_back(u);
 }
}

无向有权图

邻接表
vector<pair<int,int>>e[N]; //邻接表
int main()
{
 cin >> n >> m; //读入点数n、边数m
 for(int i = 1;i <= m;i ++)
 {
  cin >> u >> v >> k;//读入无向边<u,v>
  e[u].push_back({v,k});
  e[v].push_back({u,k});
 }
}

链式前向星

用链表维护邻接表,具体来说,是用n个单链表来取代vector数组,了解即可,对代码实现不做要求

总结

图的存储大部分情况下都使用邻接表,偶尔使用邻接矩阵

图的遍历

深度优先遍历(dfs)

当访问到一个点时,递归访问它的所有出边指向的点中还没有被访问过的

DFS
int vis[N];//vis[i]表示节点i是否被访问过
vector<int>e[n];
void dfs(int u){//当前正在访问节点u
 vis[u] = 1;
 for(int v : e[u]){
  if(vis[v] == 0) // 没有被访问过
   dfs(v);
 }
}

邻接表深度优先遍历时间复杂度为O(V+E)

第一题

前往

解析：

  1. 考虑从每个点出发进行一次深度优先遍历
  2. 能访问到的点就是从该点出发能到达的点
  3. 将其中编号最大的作为答案
  4. 时间复杂度O(NM)
  5. 反向建边转化为对一个点,求能到达它的编号最大的点
  6. 贪心:按照节点n,节点n-1,节点n-2,…的顺序依次去进行dfs
  7. 节点n能dfs到的点答案必然为n
  8. 节点n-1进行dfs时,一旦发现当前节点被遍历过,则可以直接返回
  9. 依次类推

例题1
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,m,k,s,t,ans[N];
vector<int> e[N];
void dfs(int u){
 for(int v:e[u])
  if(ans[v] == 0)
   ans[v] = ans[u],dfs(v);
}
int main(){
 cin >> n >> m;
 for(int i=1;i<= m;++i){
  cin >> s >> t;
  e[t].push_back(s);//反向建边
 }
 for(int i=n;i>= 1;--i)
  if(ans[i] == 0)
   ans[i] = i,dfs(i);
 for(int i=1;i<= n;++i)
  cout << ans[i] << " ";
}

第二题

前往

题意：

  1. 给定n个点,每个点都恰好有一条出边,求图中的最小环
  2. 环:从任意点出发绕一圈后回到自身
  3. n≤2*105
  4. 丛每个结构的任意一个点出发,沿着边的方向前进,最后必定能找到这个环
  5. ·给沿途的点编号,一县访问到一个曾经遍历过的点,则环长=两者编号的差值+1
  6. 细节：每次初始编号=上一次的初始编号+2n

当一个点被访问过的时候,就尽可能想办法不再访问

例题2
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,m,k,s,t;
long long vis[N],a[N],ans=0x3f3f3f3f;
void dfs(int u){
 if (vis[a[u]])
 {//已访问更新答案
  ans = min(ans,vis[u] + 1 - vis[a[u]]);
  return;
 }
 vis[a[u]] = vis[u] + 1;
 dfs(a[u]);
}
int main(){
 cin >> n;
 for(int i=1;i<= m;++i)
  cin >> a[i];
 long long cnt = 1;
 for(int i=1;i<= n;++i)
  if(!vis[i])
  {
   vis[i] = cnt;
   cnt += 2 * n;
   dfs(i);
  }
 cout << ans;
}

第三题

前往

题意：

  1. 给定n个点m条边的无向图,选择尽量少的点满足对于任意一条边都恰好有一个端点被选择
  2. 求选择的最少点数或者输出无解
  3. n≤104,m≤105
  4. 这样的图称为二分图,本题实际要求我们判断给出的图是否是二分图
  5. 染色法
  6. 使用dfs每次将同一个连通块内的元素都染上颜色
  7. 如果产生冲突,则说明当前图不是二分图
  8. 否则,选择的点的个数=min(颜色1的点个数,颜色2的点个数)
  9. 注意:题目没有保证图连通,所以需要对多个连通块进行dfs,累加每个连通块的答案

例题3
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,m,k,s,t,col[N],num[3],ans,bo;
vector<int> e[N];
void dfs(int u){
 for(int v:e[u]){
  if(col[v]){
   if(col[v] == col[u])
    bo = 1;
   continue;
  }
  dfs(v);
 }
}
int main(){
 cin >> n >> m;
 for(int i = 1;i <= m;i ++){
  cin >> s >> t;
  e[s].push_back(t);
  e[t].push_back(s);
 }
 for(int i = 1;i <= n;i ++){
  if(!col[i]){
   num[1] = 1;
   num[2] = 0;
   col[i] = 1;
   dfs(i);
   ans += min(num[1],num[2]);
  }
 }
 if(bo) cout << "Impossible";
 else cout << ans;
}

二分图判定

  1. 二分图的染色法是图论中比较基础和重要的内容
  2. 题意:给定一个无向图,要求把所有边标记方向,并使整张图中没有距离>=2的路径,问是否存在并输出方案。(n,m≤2*105)
  3. 如果一个点即作为入度点,又作为出度点,那么就非法了
  4. 也就是说每个点要么是入度点,要么是出度点
  5. 对于每条有向边,两个端点恰好一个是入度点,一个是出度点
  6. 所以这道题目也是一个二分图判定问题
  7. 例题：洛谷CF1144F

广度优先遍历（BFS）

  1. 初始队列里只包含起点。每次取出队头,然后将它的所有出边指向的所有点中仍未遍历过的加入队列
  2. 对无权图,该遍历方式按照从起点的单源最短路递增访问所有点
  3. 方法通常被用来在O(V+E)时间内求一个无权图上的单源最短路
广度优先遍历
queue<int> q;
memset(d,0x3f,sizeof(d));
d[1] = 0;q.push(1);
while(!q.empty()){
 int u = q.front();
 q.pop();
 for(int v:e[u]){
  if(d[v] > d[u] + 1){
   d[v] = d[u] + 1;
   q.push(v);
  }
 }
}

使用邻接表存图,bfs时间复杂度为O(V+E)

第四题

前往

解析：

  1. 这道题目让我们计算节点1到其余点的最短路条数,而且是无权图
  2. BFS
  3. n≤104,m≤105
  4. 定义num[i]表示节点1到节点i的最短路条数
  5. 初始num[1]=1

例题4
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000005;
int n,m,k,s,t,d[N],num[N];
vector<int> e[N];
int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 cin >>n>>m;
 for(int i=1;i<= m;++i){
  cin >> s >> t;
  e[s].push_back(t);
  e[t].push_back(s);
 }
 memset(d,0x3f,sizeof(d));
 queue<int> q;
 q.push(1);
 d[1]=0;
 num[1]=1;
 while (!q.empty()){
  int u = q.front();
  q.pop();
  for(int v:e[u]){
   if(d[v] > d[u] + 1){
    d[v] = d[u] + 1;
    num[v] = num[u];
    q.push(v);
   }
   else if(d[v] == d[u] + 1){
    num[v] = (num[v] + num[u]) % 100003;
   }
  }
 }
 for(int i = 1; i <= n; ++i)cout << num[i] << endl;
}

总结

  1. 图由若干个节点和若干个节点之间的边构成
  2. 有向图,无向图
  3. 带权图,无权图
  4. 图的常用存储方式有邻接矩阵、邻接表
  5. 图的遍历方式有深度优先遍历dfs、广度优先遍历bfs
  6. 广度优先遍历按照从起点的单源最短路递增顺序访问所有点,常用来求无权图的单源最短路