本文基础：请确保你学过图论基本知识，vector的基本用法，结构体，以及一些dfs与链表知识

图的存储

问题引入：

给定一个有向图，包含n个顶点和m条边，计算该图中连通分量的数量

输入格式：

第一行两个整数n,m

接下来m行，每行两个整数u,v.表示顶点u与顶点v之间有一条边

输出格式:

输出一个整数，表示联通分量的数量

输入

5 3
1 2
2 3
4 5

输出

2

解释

顶点1、2、3形成一个连通分量，顶点4、5形成另一个连通分量，因此共有2个连通分量。

初步阶段：直接存边

很明显，我们只需要联通分量的数量，那么什么是联通分量？

如果从某个顶点进行遍历，能够到达的所有顶点必然属于同一个联通变量

也就是说连通性=可达性

那我们就有了一个朴素的思想，dfs探索可达性

准备阶段，我们用一个数组来记录每一条边，数组的每个元素包含起点终点。再用另一个数组标记顶点是否被访问。

struct edge{
	int u,v;//边的起点和终点
};

vector<edge>e;//存储所有边的数组
vector<bool>vis;//标记顶点是否被访问过
int main(){
    cin >>n>>m;
    vis.resize(n+1,0);
    e.resize(m+1);
    for(int i=1;i<=m;i++){
        cin >>e[i].u>>e[i].v;
    }
}

那么dfs部分怎么写呢？我写dfs的目的是什么，是我能通过一个u节点到达哪个节点。

那我遍历每一条边，找到所有以u为起点的边，再以访问到的边为起点继续递归访问，边访问边标记。如果访问到已经访问到的节点就直接返回。

void dfs(int u) {
  if (vis[u]) return;     // 基线条件：如果已访问，直接返回
  vis[u] = true;          // 标记当前顶点为已访问
  
  for (int i = 1; i <= m; ++i) {     // 遍历所有边
    if (e[i].u == u) {               // 找到以u为起点的边
      dfs(e[i].v);                   // 递归访问终点v
    }
  }
}

插一句题外话，可以遍历节点，那也可以遍历边来查找边。就像这样。(与本题无关)

bool find_edge(int u, int v) {
  for (int i = 1; i <= m; ++i) {    // 遍历所有边
    if (e[i].u == u && e[i].v == v) {
      return true;  // 找到从u到v的边
    }
  }
  return false;     // 未找到
}

好的，那么附上完整代码

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
  int u, v;
};

int n, m;
vector<Edge> e;
vector<bool> vis;

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = 1; i <= m; ++i) {
    if (e[i].u == u) {
      dfs(e[i].v);
    }
  }
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);
  e.resize(m + 1);

  for (int i = 1; i <= m; ++i) {
    cin >> e[i].u >> e[i].v;
  }

  int count = 0;  // 连通分量计数器
  
  // 遍历所有顶点
  for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {  // 如果顶点未被访问过
      count++;      // 发现一个新的连通分量
      dfs(i);       // 遍历整个连通分量
    }
  }

  cout << count << endl;

  return 0;
}

观察一下这个做法的时间复杂度：

查询是否存在某条边：𝑂(𝑚) O(m) 。

遍历一个点的所有出边：𝑂(𝑚) O(m) 。

遍历整张图：𝑂(𝑛𝑚) O(nm) 。

空间复杂度：𝑂(𝑚) O(m) 。

每一次都要遍历图，时间复杂度还是不小的。因此人们提出了另一种思想

中级阶段：邻接矩阵

由于每条边都有两个节点，两个节点间只存在两个状态——有边和无边。

我们自然的想到可以建一个二维数组，用对应位置的0/1来表示有无边连接。

假设关系：A认识B, A认识C, B认识D, C认识D

那么对应的邻接矩阵就是这样的

所以它的精髓就是，用二维表格清晰表达顶点间关系，通过行列索引判断连通性。

所以有了一个最显著的优点，o1判断是否存在边

1	bool find_edge(int u,int v){return adj[u][v];}

我们仍然用vector来进行矩阵的定义和初始化

vector<vector<bool>>adj;//邻接矩阵
adj.resize(n+1,vector<bool>(n+1,false));//创建n*n矩阵，初始没有边连接
for(int i=1;i<=m;i++){
    int u,v;
    cin >>u>>v;
    adj[u][v]==true;//标记边存在
}

有了邻接矩阵，我们的dfs也可以优化了。因为我们要找节点u能到达的，实际只需要横着找一遍

void dfs(int u){
	if(vis[u]) return;
	vis[u]==true;
	for(int v=1;v<=n;v++){
        if(adj[u][v] && !vis[v]){
            dfs(v);
        }
    }
}

附上完整代码~

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<bool>> adj;  // 邻接矩阵
vector<bool> vis;

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    
    // 有向图：只遍历从u出发的边（u→v方向）
    for (int v = 1; v <= n; ++v) {
        if (adj[u][v] && !vis[v]) {  // 存在边 u→v 且v未访问
            dfs(v);
        }
    }
}

int main() {
    cin >> n >> m;
    
    // 初始化邻接矩阵（n+1)×(n+1)，全部为false
    adj.resize(n + 1, vector<bool>(n + 1, false));
    vis.resize(n + 1, false);
    
    // 输入有向边
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;  // 只标记u→v方向
        // 注意：这里没有 adj[v][u] = true（有向图的关键区别！）
    }
    
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            count++;
            dfs(i);
        }
    }
    
    cout << "有向图连通分量数量: " << count << endl;
    return 0;
}

插一句题外话，其实有向图和无向图的差别只在于

无向图的边是双向的，要考虑两个方向

// 输入无向边时，同时标记两个方向
for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u][v] = true;  // u→v
    adj[v][u] = true;  // v→u （关键！让矩阵对称）
}
// DFS遍历保持不变（因为矩阵已经对称）
for (int v = 1; v <= n; ++v) {
    if (adj[u][v]) {  // 现在只需要检查一个方向
        dfs(v);
    }
}

同样的附上时间复杂度

查询是否存在某条边：𝑂(1) O(1) 。

遍历一个点的所有出边：𝑂(𝑛) O(n) 。

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

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

[!NOTE]

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以 𝑂(1) 查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

高级阶段：邻接表

如果说邻接矩阵的问人方式，是问遍所有人你认不认识张三，那么邻接表的问人方式像是直接查看张三的通讯录，只看张三认识的人。我们只用把每个人的认识的人都存在他的通讯录下，就可以实现高效拆查询。这里我们仍然用到vector(太好用了！)

直观的说大概是这样的。

vector<vector<int>>adj;
//示例，顶点1认识2，3，顶点2认识4
adj[1]={2,3};
adj[2]={4};
adj[3]={};

那邻接表怎么dfs遍历，和构建邻接表呢

void dfs(int u){
	if(vis[u])return;
	vis[u]=true;
	//直接访问u的邻居链表
    for(int v:adj[u]){
        if(!vis[v]){
            dfs(v);
        }
    }
}

for(int i=1;i<=m;i++){
    int u,v;
    cin >>u>>v;
    adj[u],push_back(v);//只在u的列表中添加v
    //注意：有向图不添加adj[v].push_back(u)
}

好的，附上完整代码

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> adj;  // 邻接表
vector<bool> vis;

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = true;
    
    // 邻接表遍历：直接访问u的所有邻居
    for (int v : adj[u]) {        // 遍历u的邻居列表
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    cin >> n >> m;
    
    // 初始化：n+1个空列表
    adj.resize(n + 1);
    vis.resize(n + 1, false);
    
    // 构建邻接表
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // 只在u的列表中添加v
        // 注意：有向图，不添加adj[v].push_back(u)
    }
    
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            count++;
            dfs(i);
        }
    }
    
    cout << "有向图连通分量数量: " << count << endl;
    return 0;
}

当然，这个简单的问题其实不能很好的体现邻接表的作用。（后面会补上完整邻接表板子）

复杂度

查询是否存在 𝑢 到 𝑣 的边：𝑂(𝑑+(𝑢)) O(d^+(u)) （如果事先进行了排序就可以使用二分查找做到 𝑂(log⁡(𝑑+(𝑢))) $O(\log(d^+(u)))$ ）。

遍历点 𝑢的所有出边：𝑂(𝑑+(𝑢)) O(d^+(u)) 。

遍历整张图：𝑂(𝑛 +𝑚) O(n+m) 。

空间复杂度：𝑂(𝑚) O(m) 。

应用

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

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

同样高级的阶段：链式前向星

传统邻接表其实有一个很明显的问题，每个顶点都有一个vector。所以内存不连续，缓存不友好。

那么聪明的先人就发明出了链式前向星算法！

用数组模拟链表，所有边存储在一个大数组中

数据结构设计如下

#include <iostream>
#include <cstring>  // for memset
using namespace std;

const int MAXN = 100010;  // 最大顶点数
const int MAXM = 200010;  // 最大边数（无向图要×2）

// 链式前向星的三要素
struct Edge{
    int to; //边的终点
    int next; //下一条边的索引
    // int weight; 边的权重（可选）
}edge[MAXM]; //边数组

int head[MAXN]; //head[u],顶点u的第一条边在edge数组中的索引
int cnt=0;//边计数器，当前边的数量

添加边的函数

void addedge(int u,int v){
    edge[++cnt].to=v;//新边的终点是u
    edge[cnt].next=head[u];//新边的下一条边u是原来的第一条边
    head[u]=cnt;//u的第一条边更新为新边
}

看不懂其实很正常，举个例子会好很多，假设我要依次添加边

1->2 ,1->3, 2->4

添加1-2

初始化：head[1]=0,cnt=0
 添加边1->2
 edge[1].to=2
 edge[1].next=head[1]=0
 head[1]=1
 
 结果：head[1]->edge[1](to=2,next=0)

添加边1-3

edge[2].to=3
edge[2].next=head[1]=1
head[1]=2

结果：
head[1]->edge[2](to=3,next=1)->edge[1](to=2,next=0)->null

添加边2->4

edge[3].to = 4
edge[3].next = head[2] = 0
head[2] = 3

结果:
head[1] → edge[2] → edge[1] → NULL
head[2] → edge[3] → NULL

遍历方式与过程解析

// 遍历u的所有邻居
for (int i = head[u]; i != 0; i = edge[i].next) {
    int v = edge[i].to;  // 邻居顶点v
    // 处理v...
}

以顶点1为例
head[1] = 2
第一次循环: i=2, v=edge[2].to=3
第二次循环: i=edge[2].next=1, v=edge[1].to=2  
第三次循环: i=edge[1].next=0, 结束

完整代码如下

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100010;
const int MAXM = 200010;

struct Edge {
    int to;
    int next;
    // int weight;  // 如果需要边权
} edge[MAXM];

int head[MAXN];
int cnt = 0;

// 初始化
void init() {
    memset(head, 0, sizeof(head));  // 初始化为0
    cnt = 0;
}

// 添加边
void addEdge(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

// 添加带权边
void addEdge(int u, int v, int w) {
    edge[++cnt].to = v;
    // edge[cnt].weight = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

// DFS遍历
void dfs(int u, bool visited[]) {
    visited[u] = true;
    cout << u << " ";
    
    for (int i = head[u]; i != 0; i = edge[i].next) {
        int v = edge[i].to;
        if (!visited[v]) {
            dfs(v, visited);
        }
    }
}

// 打印图的邻接关系
void printGraph(int n) {
    cout << "链式前向星表示的图:" << endl;
    for (int u = 1; u <= n; u++) {
        cout << u << ": ";
        for (int i = head[u]; i != 0; i = edge[i].next) {
            cout << edge[i].to << " ";
        }
        cout << endl;
    }
}

int main() {
    init();
    
    int n = 5;
    // 添加边: 1→2, 1→3, 2→4, 3→4, 4→5
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(3, 4);
    addEdge(4, 5);
    
    printGraph(n);
    
    cout << "DFS遍历(从1开始): ";
    bool visited[MAXN] = {false};
    dfs(1, visited);
    cout << endl;
    
    return 0;
}

应用

存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。

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

dfs

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

DFS 最显著的特征在于其 递归调用自身。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次。符合以上两条规则的函数，便是广义上的 DFS。

具体地说，DFS 大致结构如下

DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
  在 v 上打访问标记
  for u in v 的相邻节点
    if u 没有打过访问标记 then
      DFS(u)
    end
  end
end

我们可以递归实现dfs，也可以栈。

递归实现

vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(const int u) {
  vis[u] = true;
  for (int v : adj[u])
    if (!vis[v]) dfs(v)
}

栈实现

vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(int s) {
  stack<int> st;
  st.push(s);
  vis[s] = true;

  while (!st.empty()) {//当栈非空
    int u = st.top();//存储栈顶元素
    st.pop();//弹出栈顶元素

    for (int v : adj[u]) {
      if (!vis[v]) {//如果没被访问过
        vis[v] = true;  // 确保栈里没有重复元素
        st.push(v);
      }
    }
  }
}

（以后单开一篇文讲dfs,bfs实战，这里不做重点）

bfs

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

数据结构说明：

Q：队列，用于BFS遍历
vis[]：标记数组，记录节点是否被访问过
d[]：距离数组，记录每个节点到起点的最短距离
p[]：前驱数组，记录每个节点在最短路径上的前一个节点
head[]和e[]：图的邻接表存储结构

BFS执行流程：

初始化：清空队列，将起点加入队列并标记
循环处理：从队列中取出节点，遍历其所有未访问的邻居
更新信息：记录邻居节点的距离和前驱节点
继续扩展：将邻居节点加入队列等待处理

路径还原原理：

利用BFS树的性质，每个节点的前驱节点p[v]记录了到达该节点的最短路径上的前一个节点。通过从目标节点不断回溯前驱节点，就能得到完整的路径。

特点：

最短路径：BFS保证找到的是从起点到各点的最短路径（边权为1时）
层次遍历：按距离起点的层次顺序遍历节点
时间复杂度：O(V+E)，其中V是节点数，E是边数

// 广度优先搜索（BFS）函数，从起点u开始遍历
void bfs(int u) {
  while (!Q.empty()) Q.pop();  // 清空队列，确保队列为空
  Q.push(u);                   // 将起点加入队列
  vis[u] = 1;                  // 标记起点为已访问
  d[u] = 0;                    // 起点到自身的距离为0
  p[u] = -1;                   // 起点的前驱节点设为-1（表示无前驱）
  
  while (!Q.empty()) {         // 当队列不为空时继续搜索
    u = Q.front();             // 取出队首节点
    Q.pop();                   // 弹出队首节点
    
    // 遍历当前节点u的所有邻居节点
    for (int i = head[u]; i; i = e[i].nxt) {
      // 如果邻居节点未被访问过
      if (!vis[e[i].to]) {
        Q.push(e[i].to);       // 将邻居节点加入队列
        vis[e[i].to] = 1;      // 标记邻居节点为已访问
        d[e[i].to] = d[u] + 1; // 记录邻居节点到起点的距离（当前节点距离+1）
        p[e[i].to] = u;        // 记录邻居节点的前驱节点为当前节点u
      }
    }
  }
}

// 还原从起点到节点x的最短路径
void restore(int x) {
  vector<int> res;             // 存储路径的容器
  
  // 从目标节点x开始，沿着前驱指针回溯到起点
  for (int v = x; v != -1; v = p[v]) {
    res.push_back(v);          // 将路径上的节点加入容器
  }
  
  std::reverse(res.begin(), res.end());  // 反转容器，使路径从起点到终点
  
  // 输出路径
  for (int i = 0; i < res.size(); ++i) 
    printf("%d", res[i]);
  puts("");                    // 换行
}

应用

在一个无权图上求从起点到其他所有点的最短路径。
在 𝑂(𝑛 +𝑚) 时间内求出所有连通块。（我们只需要从每个没有被访问过的节点开始做 BFS，显然每次 BFS 会走完一个连通块)
如果把一个游戏的动作看做是状态图上的一条边（一个转移），那么 BFS 可以用来找到在游戏中从一个状态到达另一个状态所需要的最小步骤。
在一个有向无权图中找最小环。（从每个点开始 BFS，在我们即将抵达一个之前访问过的点开始的时候，就知道遇到了一个环。图的最小环是每次 BFS 得到的最小环的平均值。）
找到一定在 (𝑎,𝑏) 最短路上的边。（分别从 a 和 b 进行 BFS，得到两个 d 数组。之后对每一条边 (𝑢,𝑣)，如果 𝑑𝑎[𝑢] +1 +𝑑𝑏[𝑣] =𝑑𝑎[𝑏]，则说明该边在最短路上)
找到一定在 (𝑎,𝑏) 最短路上的点。（分别从 a 和 b 进行 BFS，得到两个 d 数组。之后对每一个点 v，如果 𝑑𝑎[𝑣] +𝑑𝑏[𝑣] =𝑑𝑎[𝑏]，则说明该点在某条最短路上）
找到一条长度为偶数的最短路。（我们需要一个构造一个新图，把每个点拆成两个新点，原图的边 (𝑢,𝑣) 变成 ((𝑢,0),(𝑣,1)) 和 ((𝑢,1),(𝑣,0))。对新图做 BFS，(𝑠,0) 和 (𝑡,0) 之间的最短路即为所求）
在一个边权为 0/1 的图上求最短路，见下方双端队列 BFS。