准备

再次之前,你需要知道:

C++基础语法知识

简单地递归

图的存储(可以看我博客的文章"[图论]图的存储")

DFS和BFS(不需要深入了解,知道原理或者只知道一些概念)

除此之外

如果两点之间存在一条边连接就代表着这两点之间可以一步抵达

定义一下变量名:

• $n$ :表示所有点的数量

• $m$:表示所有边的数量

• $visited$:存储已访问的点

• $adj$存储图的数组

• $Src$:表示起点,是Source的缩写

• $Dest$:表示终点,是Destination的缩写

简介

图的遍历有两种形式:DFS和BFS,即深度优先遍历和广度优先遍历.遍历等同于搜索.

1.DFS

首先我们要了解DFS的逻辑,通过之前的学习,大致可以归类为以下几个步骤,其中DFS(x)表示从点x开始进行搜索

逻辑大概是这样,在图中我们该怎么办那?

很容易想到只要解决掉寻找点的步骤,整个问题就会迎刃而解.因为图有三种存储方式,所以我会提供三种遍历方式,但是核心逻辑是不变的.

1.1邻接矩阵(不推荐)

回忆一下邻接矩阵的存储方式,我们用 adj[u][v]=w 表示点 u 到点 v 这条边的权值为 w ,
现在我们知道点 Src ,想要知道它和哪一个点存在边,我们可以枚举每一个 adj[Src][i] 其中 i 是要枚举的点.然后根据 adj[Src][i] 的值来判断点 Src 到点 i 之间是否存在一条边.

这里如果没有非正数权值就可以把 adj 的所有元素初始化为0 ,这样对于任意 adj[i][j] 如果 adj[i][j]=0 就代表着点 i 到点 j 之间不存在边.

当任意一点u到点v之间有边,就代表着从点u可以一步抵达点v.这时候我们把点v标记到visited数组防止下次重复访问造成死循环,为此我们还需要特别判断这个点是否被visist数组标记.

那么通过一个for 循环就可以实现对adj[u][i]中i的枚举.

那么,话就说这么多,我们来看看代码怎么写:

#include<bits/stdc++.h>
using namespace std;
int n, m;//n为点数，m为边数
int Src;
vector<vector<int> >adj;//二维vector,两个'>'之间要有空格
vector<int> visited;//记录每个点是否被访问过
void dfs(int x) {//dfs(x)表示从点x开始进行搜索
    visited[x] = 1;
    cout << "访问节点:" << x << endl;
    for (int i = 0;i < adj[x].size();i++) {//从节点0开始,你可以根据题目自行修改
        if (adj[x][i] > 0 && !visited[i]) {//如果点x与点i相连且点i未被访问过
            dfs(i);//从点i开始进行搜索
        }
    }
}
int main() {
    int u, v, w;
    cin >> Src;//输入起点
    cin >> n >> m;//输入点数和边数
    adj.resize(n + 1, vector<int>(n + 1, 0));//初始化二维vector
    visited.resize(n + 1, 0);//初始化记录数组，初始时所有点都未被访问过
    for (int i = 0;i < m;i++) {
        cin >> u >> v >> w;
        adj[u][v] = w;//u到v的边权为w
        adj[v][u] = w;//如果无向图
    }
    dfs(Src);
    return 0;
}

输入:
1
6 8
0 2 1
0 4 1
0 5 1
1 4 1
1 5 1
2 3 1
2 4 1 
4 5 1
输出:
访问节点:1
访问节点:4
访问节点:0
访问节点:2
访问节点:3
访问节点:5

1.1.1分析

时间复杂度$O(n^2)$

空间复杂度$O(n^2)$

不建议拿来做题,作为了解就好

1.2邻接表(推荐)

邻接表的存储方式:$adj[u][i].v$表示以点$u$为起点的第$i$ 条边的终点.$adj[u][i].w$表示以点$u$为起点的第$i$ 条边的权值.

struct node{
  int v;//这条边的终点
  int w;//权值
};
vector<node>adj[MAXN];

那么这就好办了,我们不需要再像邻接矩阵那样枚举合法的点,不需要判断是否存在边,只需要特别判断一下这个点有没有被$visited$标记过.

利用for 循环,我们遍历$adj[u][i]$,其中因为$adj[u]$是一个vector,所以可以直接得到$i≤adj[u].size()$.

那么如果存在$adj[u][i]$,则直接dfs(adj[u][i].v) 就好.

邻接表这没啥好讲的,dfs的核心思想你也掌握了,那么我们就直接上代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;//数组大小
struct node {
    int v;
    int w;
};
vector<node>adj[MAXN];
bool visited[MAXN];//标记是否访问过的数组
int n, m;//n个点m条边
int Src;//起点
void dfs(int u) {//dfs(u)表示从点u开始进行搜索
    visited[u] = 1;//标记已访问
    cout << "访问节点:" << u << endl;
    for (int i = 0;i < adj[u].size();i++) {//遍历u的所有邻接点
        if (!visited[adj[u][i].v])//如果v未访问过
            dfs(adj[u][i].v);//递归访问
    }
}
int main() {
    int u, v, w;//起点,终点,权值
    cin >> Src;//输入起点
    cin >> n >> m;//输入点数和边数
    for (int i = 1;i <= m;i++) {
        cin >> u >> v >> w;
        adj[u].push_back((node) { v, w });
        adj[v].push_back((node) { u, w });//无向图
    }
    dfs(Src);//从起点开始遍历
    return 0;
}

然后测试一下对不对

输入:
1
6 8
0 2 1
0 4 1
0 5 1
1 4 1
1 5 1
2 3 1
2 4 1 
4 5 1
输出:
访问节点:1
访问节点:4
访问节点:0
访问节点:2
访问节点:3
访问节点:5

1.2.1分析

时间复杂度:$O(n + m)$，其中$n$是顶点数，$m$是边数

空间复杂度:$O(n)$

1.3链式前向星(中等)

还记得链式前向星的存储格式吗?定义一个数组head和edge ,head[i]存储以节点i为起点的所有边的起始位置,edge[i]存储第i条边的信息.

struct Edge {
    int to, w, nxt;//to是这条边的终点，w是这条边的权值，nxt是下一条边的编号
}edge[MAXN];
int head[MAXN], cnt;//head存每个点的第一条边，cnt存边的数量

链式前向星因为是链式结构,所以也不需要像邻接矩阵那样枚举点,因为有nxt 存储下一边的编号,当nxt=-1时,就代表着这个点的所有邻接点都被访问过了.

那么对于这个for 循环,我们需要改进一下,将i初始化为head[u],u是DFS(u)正在处理的点,让i一直等于nxt[i],这样直到i=-1就可以终止循环了,根据for循环的格式,容易得到

for (int i = head[u]; i != -1; i = edge[i].nxt) {//从head[u]开始,寻找所有关于u的邻接点
        int v = edge[i].to;//获取下一个点
        if (!visited[v]) {//如果未标记
            dfs(v);
        }
    }

进一步我们可以写出代码了

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
struct Edge {
    int to, w, nxt;//目标点，权值，下一条边的编号
}edge[MAXN];
int head[MAXN], cnt;//head[i]表示i号点的第一条边，cnt表示边的数量的一个计数器
bool visited[MAXN];//标记数组，表示是否访问过
int n, m;//n个点，m条边
int Src;//起点
void add(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];//将这条边添加到链表的前面
    head[u] = cnt++;//更新第一条边的编号
}
void dfs(int u) {
    visited[u] = 1;//标记为已访问
    cout << "访问节点:" << u << endl;
    for (int i = head[u]; i != -1; i = edge[i].nxt) {//从head[u]开始,寻找所有关于u的邻接点
        int v = edge[i].to;//获取下一个点
        if (!visited[v]) {//如果未标记
            dfs(v);
        }
    }
}
int main() {
    memset(head, -1, sizeof(head));//初始化head数组为-1
    int u, v, w;
    cin >> Src >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);//无向图
    }
    dfs(Src);
    return 0;
}

那么我们也测试一下样例

输入:
1
6 8
0 2 1
0 4 1
0 5 1
1 4 1
1 5 1
2 3 1
2 4 1
4 5 1
输出:
访问节点:1
访问节点:5
访问节点:4
访问节点:2
访问节点:3
访问节点:0

1.3.1分析

时间复杂度$O(n + m)$，其中 n 表示图中的顶点数，m 表示图中的边数

空间复杂度$O(n + m)$

2.BFS

BFS对比DFS突出的特点就是先找到所有合法的点,然后一个个进行搜索,对于一些复杂的图会比较有优势.

BFS需要用到队列.

2.1邻接矩阵(不推荐)

对列名.empty() 返回队列是否为空,为空返回1,不为空返回0

一些细节我讲不再重复(真是不知道该说啥了),直接上代码吧,我觉得根据注释很好理解

#include<bits/stdc++.h>
using namespace std;
int n, m;//n个点，m条边
vector<vector<int> >adj;
vector<bool>visited;
int Src;//起点
void bfs(int x) {
    queue<int>q;//队列
    q.push(x);//将起点加入队列
    visited[x] = 1;//标记起点已访问
    while (!q.empty()) {//只有队列不为空才循环
        int u = q.front();//取出队首元素
        q.pop();//将队首元素移出队列
        cout << "访问节点:" << u << endl;
        for (int i = 0;i < n;i++) {//将所有的相邻节点放入队列
            if (adj[u][i] > 0 && !visited[i]) {//枚举合法的相邻节点
                visited[i] = 1;//标记该节点已访问
                q.push(i);//将相邻节点加入队列
            }
        }
    }
}
int main() {
    int u, v, w;
    cin >> Src;//输入起点
    cin >> n >> m;//输入点数和边数
    adj.resize(n, vector<int>(n, 0));//初始化二维vector
    visited.resize(n, 0);
    for (int i = 0;i < m;i++) {
        cin >> u >> v >> w;
        adj[u][v] = w;
        adj[v][u] = w;//无向图
    }
    bfs(Src);
    return 0;
}

输入:
1
7 9
0 2 1
0 1 1
0 3 1
1 4 1
1 5 1
2 4 1
3 5 1
4 6 1
5 6 1
输出:
访问节点:1
访问节点:0
访问节点:4
访问节点:5
访问节点:2
访问节点:3
访问节点:6

可以看到,对比DFS,BFS是层次上的遍历,先访问一个点,逐渐向外均匀地扩张

2.2 邻接表（推荐）

邻接表的BFS实现更加高效，不需要像邻接矩阵那样遍历所有节点。通过遍历邻接表中存储的邻接点，可以快速找到所有可达节点。

 #include <bits/stdc++.h>
 using namespace std;
 const int MAXN = 100005;
 ​
 struct node {
     int v;
     int w;
 };
 ​
 vector<node> adj[MAXN];  // 邻接表存储图
 bool visited[MAXN];      // 访问标记数组
 int n, m;                // 点数、边数
 int Src;                 // 起点
 ​
 void bfs(int start) {
     queue<int> q;
     q.push(start);
     visited[start] = true;
     
     while (!q.empty()) {
         int u = q.front();
         q.pop();
         cout << "访问节点:" << u << endl;
         
         // 遍历所有邻接点
         for (int i = 0; i < adj[u].size(); ++i) {
             int v = adj[u][i].v;
             if (!visited[v]) {
                 visited[v] = true;
                 q.push(v);
             }
         }
     }
 }
 ​
 int main() {
     memset(visited, 0, sizeof(visited));
     cin >> Src >> n >> m;
     
     // 构建邻接表
     for (int i = 0; i < m; ++i) {
         int u, v, w;
         cin >> u >> v >> w;
         adj[u].push_back({v, w});
         adj[v].push_back({u, w});  // 无向图需双向添加
     }
     
     bfs(Src);
     return 0;
 }
 ​

输入（与DFS示例相同结构）：

 1
 6 8
 0 2 1
 0 4 1
 0 5 1
 1 4 1
 1 5 1
 2 3 1
 2 4 1 
 4 5 1

输出：

 访问节点:1
 访问节点:4
 访问节点:5
 访问节点:0
 访问节点:2
 访问节点:3

复杂度分析

• 时间复杂度：$O(n + m)$

• 空间复杂度：$O(n)$

核心逻辑说明

1. 初始化队列：将起点加入队列并标记

2. 循环处理队列：

   • 取出队首节点并访问

   • 将其所有未访问邻接节点入队

3. 终止条件：当队列为空时，说明所有可达节点都已访问

2.3 链式前向星（中等）

链式前向星的BFS实现与邻接表类似，核心差异在于邻接点的遍历方式。我们通过head[u]获取首条边的编号，再通过nxt指针遍历所有邻接边。

代码实现

 #include<bits/stdc++.h>
 using namespace std;
 const int MAXN = 100000;
 struct Edge {
     int to, w, nxt; // 目标点，权值，下一条边的编号
 }edge[MAXN];
 int head[MAXN], cnt; // head初始化为-1，cnt记录边数
 bool visited[MAXN];  // 访问标记数组
 int n, m;            // 顶点数和边数
 int Src;             // 起点
 ​
 void add(int u, int v, int w) {
     edge[cnt].to = v;
     edge[cnt].w = w;
     edge[cnt].nxt = head[u]; // 新边插入链表头部
     head[u] = cnt++;         // 更新头指针
 }
 ​
 void bfs(int start) {
     queue<int> q;
     visited[start] = true; // 标记起点已访问
     q.push(start);         // 起点入队
 ​
     while (!q.empty()) {
         int u = q.front(); // 取出队首节点
         q.pop();
         cout << "访问节点:" << u << endl;
 ​
         // 遍历u的所有邻接边
         for (int i = head[u]; i != -1; i = edge[i].nxt) {
             int v = edge[i].to;
             if (!visited[v]) {
                 visited[v] = true; // 标记访问
                 q.push(v);         // 邻接点入队
             }
         }
     }
 }
 ​
 int main() {
     memset(head, -1, sizeof(head)); // 初始化head数组
     int u, v, w;
     cin >> Src >> n >> m;
 ​
     // 添加边（无向图需添加两次）
     for (int i = 0; i < m; i++) {
         cin >> u >> v >> w;
         add(u, v, w);
         add(v, u, w); // 无向图反向边
     }
 ​
     bfs(Src);
     return 0;
 }
 ​

测试样例

输入：

 1
 6 8
 0 2 1
 0 4 1
 0 5 1
 1 4 1
 1 5 1
 2 3 1
 2 4 1
 4 5 1

输出（因链式前向星头插法顺序不同，层次遍历顺序可能变化）：

 访问节点:1
 访问节点:4
 访问节点:5
 访问节点:0
 访问节点:2
 访问节点:3

算法分析

• 时间复杂度：$O(n + m)$，每个顶点和边被访问一次

• 空间复杂度：$O(n + m)$，用于存储图结构和队列

4. 应用场景建议

• 推荐使用BFS：

  • 寻找无权图最短路径

  • 社交网络好友推荐（三度人脉）

  • 网页爬虫层级抓取

• 推荐使用DFS：

  • 拓扑排序

  • 寻找连通分量

  • 检测环路

  • 棋盘类问题（八皇后、数独）

DFS与BFS对比