图论入门：基本概念与代码实现（邻接矩阵、邻接表、DFS/BFS）

路径

简单路径与回路

路径长度和带权路径长度

子图

G1_1 和 G1_2 为无向图 G1 的子图，G1_1 为 G1 的生成子图（G1_1包含G1的所有顶点）。 G2_1 和 G2_2 为有向图 G2 的子图，G2_1 为 G2 的生成子图（G2_1包含G2的所有顶点）。

连通图与连通分量

1. 连通（连通性） 定义：在无向图中，如果从顶点 v1 到 v2 存在路径，就称 v1 和 v2 是连通的。 连通图：如果图中任意两个顶点都连通，这个图就是连通图；否则是非连通图。 判定条件：若一个有 n 个顶点的图，边数小于 n−1，则它一定是非连通图。
2. 极大连通子图 定义：在无向图中，一个子图如果满足： 它本身是连通的； 再加入图中任何其他顶点或边，它就不再连通。那么这个子图就是极大连通子图。
3. 连通分量 定义：无向图中的极大连通子图，就称为该图的连通分量。 直观理解：一个非连通图可以被拆分成若干个互不相交的连通子图，每一个这样的子图就是一个连通分量。例如，图中的无向图 G 就被拆分成了 3 个连通分量。

概念关系总结 连通是顶点之间的二元关系。 连通图是满足'任意两顶点都连通'这一整体性质的图。 极大连通子图是从图中'抠'出来的、不能再大的连通子图。 连通分量就是无向图中的所有极大连通子图，是对非连通图结构的分解。

生成树

简单理解就是把原始图所有顶点拿出来在保证所有顶点都连通的前提下，用最少的边把它们连起来串成一颗 1 对多的树。

二、图的存储

图的存储有两种：邻接矩阵和邻接表：

• 其中，邻接表的存储方式与树的孩子表示法完全一样。因此，用 vector 数组以及链式前向星就能实现。
• 而邻接矩阵就是用二维数组，其中 edges[i][j] 存储顶点 i 与顶点 j 之间，边的信息。

图的遍历分两种：DFS 和 BFS，和树的遍历方式以及实现方式完全一样。因此，可以仿照树这个数据结构来学习。

邻接矩阵

邻接矩阵，指用一个矩阵 (即二维数组) 存储图中边的信息 (即各个顶点之间的邻接关系)，存储顶点之间邻接关系的矩阵称为邻接矩阵。 对于带权图而言，若顶点 vi 和 vj 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点 vi 和 vj 不相连，则用 ∞（若权值都为正数，也可用 -1）来代表这两个顶点之间不存在边。 对于不带权的图，可以创建一个二维的 bool 类型的数组，来标记顶点 vi 和 vj 之间有边相连。

矩阵中元素个数为 n×n，即空间复杂度为 O(n^2)，n 为顶点个数，和实际边的条数无关，适合存储稠密图。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010; // 结点个数、边的个数
int n, m; // i 到 j 有一条权值为 edges[i][j] 的边
int edges[N][N];

int main(){
    memset(edges, -1, sizeof edges);
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= n; i++){
        int a, b, c;
        cin >> a >> b >> c; // a - b 有一条边，权值为 c
        edges[a][b] = c;
        // 如果是无向边，需要反过来再存一下
        edges[b][a] = c;
    }
    return 0;
}

邻接表

用邻接表存储图类似于我们之前存储树的孩子表示法，孩子表示法是把某个结点的所有孩子结点以链表的形式挂在该节点后面，而对于图来说就是把和某个结点相邻的全部结点以链表的形式挂在该节点后面。

vector 数组

和树的存储一模一样，只不过如果存在边权的话，我们的 vector 数组里面放一个结构体或者是 pair 即可。

#include <iostream>
#include <vector>
using namespace std;
// <与哪条边相连，该边的权值>
typedef pair<int,int> PII;
const int N = 1e5+10; // 结点个数、边的个数
int n, m;
// 结点 i 到结点 edges[i].first 有一条权值为 edges[i].second 的边
vector<PII> edges[N];

int main(){
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a 和 b 之间有一条边，权值为 c
        edges[a].push_back({b, c});
        // 如果是无向边，需要反过来再存一下
        edges[b].push_back({a, c});
    }
    return 0;
}

链式前向星

和树的存储一模一样，只不过如果存在边权的话，我们多创建一维数组 w，用来存储边的权值即可。

#include <iostream>
using namespace std;
const int N = 1e5+10; // 链式前向星
int h[N], e[N * 2], ne[N * 2], w[N * 2], id;
int n, m;

// 其实就是把 b 头插到 a 所在的链表后面
void add(int a, int b, int c){
    id++;
    e[id] = b;
    w[id] = c; // 多存一个权值信息
    ne[id] = h[a];
    h[a] = id;
}

int main(){
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a 和 b 之间有一条边，权值为 c
        add(a, b, c);
        add(b, a, c);
    }
    return 0;
}

数组含义 h[N]：表头数组，h[a] 表示从节点 a 出发的第一条边在 e 数组中的下标。初始值为 -1（表示没有边）。 e[N2]：存储每条边指向的终点节点编号。 ne[N2]：存储同一起点的下一条边的下标，用于构成链表。 w[N*2]：存储每条边的权值。 id：全局计数器，用于分配边的下标。

add 函数 这个函数的作用是在图中添加一条从 a 指向 b，权值为 c 的有向边。它采用'头插法'将新边插入到以 a 为起点的链表头部： id++：为新边分配一个唯一的下标。 e[id] = b：记录这条边指向的终点是 b。 w[id] = c：记录这条边的权值是 c。 ne[id] = h[a]：让新边的 ne 指针指向原来的表头，建立链表连接。 h[a] = id：更新表头，让新边成为从 a 出发的第一条边。

main 函数 首先读入节点数 n 和边数 m。 然后循环 m 次，每次读入一条边的两个端点 a、b 和权值 c。 因为是无向图，所以需要调用两次 add 函数： add(a, b, c)：添加一条从 a 到 b 的边。 add(b, a, c)：添加一条从 b 到 a 的边，以表示双向连通。

三、图的遍历

DFS

以上图为例，用 dfs 带大家走一遍： 递归：1——>2——>5——>6——>4 此时和 4 相邻的 1、2 都遍历过了，所以要递归返回：4——>6，对于 6 来说 6 相邻的 2、5 都遍历过了，故该结点是叶子结点，要继续返回（后续递归返回的结点 5、2 也是与之相邻的结点都遍历过了，直接返回，就不一一说明了）：6——>5——>2——>1 此时对于 1 来说还有 3 没遍历过，所以继续递归：1——>3，3 也是叶子结点，递归返回：3——>1.递归结束。

// 邻接矩阵
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int n, m;
int edges[N][N];
bool st[N]; // 标记哪些点已经访问过

void dfs(int u){
    cout << u << endl;
    st[u] = true;
    // 遍历所有孩子
    for(int v = 1; v <= n; v++){
        // 如果存在 u->v 的边，并且没有遍历过
        if(edges[u][v] != -1 && !st[v]){
            dfs(v);
        }
    }
}

int main(){
    memset(edges, -1, sizeof edges);
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a - b 有一条边，权值为 c
        edges[a][b] = c;
        // 如果是无向边，需要反过来再存一下
        edges[b][a] = c;
    }
    return 0;
}

// 邻接表——vector 数组
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int n, m;
vector<PII> edges[N];
bool st[N]; // 标记哪些点已经访问过

void dfs(int u){
    cout << u << endl;
    st[u] = true;
    // 遍历所有孩子
    for(auto& t : edges[u]){
        // u->v 的一条边，权值为 w
        int v = t.first, w = t.second;
        if(!st[v]){
            dfs(v);
        }
    }
}

int main(){
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a 和 b 之间有一条边，权值为 c
        edges[a].push_back({b, c});
        // 如果是无向边，需要反过来再存一下
        edges[b].push_back({a, c});
    }
    return 0;
}

// 邻接表——链式向前星
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5+10; // 链式前向星
int h[N], e[N * 2], ne[N * 2], w[N * 2], id;
int n, m;

// 其实就是把 b 头插到 a 所在的链表后面
void add(int a, int b, int c){
    id++;
    e[id] = b;
    w[id] = c; // 多存一个权值信息
    ne[id] = h[a];
    h[a] = id;
}

bool st[N];
void dfs(int u){
    cout << u << endl;
    st[u] = true;
    // 遍历所有的孩子
    for(int i = h[u]; i; i = ne[i]){
        // u->v 的一条边
        int v = e[i];
        if(!st[v]){
            dfs(v);
        }
    }
}

int main(){
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a 和 b 之间有一条边，权值为 c
        add(a, b, c);
        add(b, a, c);
    }
    return 0;
}

BFS

// 临接矩阵
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int n, m;
int edges[N][N];
bool st[N]; // 标记哪些点已经访问过

void bfs(int u){
    queue<int> q;
    q.push(u);
    st[u] = true;
    while(q.size()){
        auto a = q.front();
        q.pop();
        cout << a << endl;
        for(int b = 1; b <= n; b++){
            if(edges[a][b] != -1 && !st[b]){
                q.push(b);
                st[b] = true;
            }
        }
    }
}

int main(){
    memset(edges, -1, sizeof edges);
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a - b 有一条边，权值为 c
        edges[a][b] = c;
        // 如果是无向边，需要反过来再存一下
        edges[b][a] = c;
    }
    return 0;
}

// 邻接表——vector 数组
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int n, m;
vector<PII> edges[N];
bool st[N]; // 标记哪些点已经访问过

void bfs(int u){
    queue<int> q;
    q.push(u);
    st[u] = true;
    while(q.size()){
        auto a = q.front();
        q.pop();
        cout << a << endl;
        for(auto& t : edges[a]){
            int b = t.first, c = t.second;
            if(!st[b]){
                q.push(b);
                st[b] = true;
            }
        }
    }
}

int main(){
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a 和 b 之间有一条边，权值为 c
        edges[a].push_back({b, c});
        // 如果是无向边，需要反过来再存一下
        edges[b].push_back({a, c});
    }
    return 0;
}

// 邻接表——链式向前星
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5+10; // 链式前向星
int h[N], e[N * 2], ne[N * 2], w[N * 2], id;
int n, m;

// 其实就是把 b 头插到 a 所在的链表后面
void add(int a, int b, int c){
    id++;
    e[id] = b;
    w[id] = c; // 多存一个权值信息
    ne[id] = h[a];
    h[a] = id;
}

bool st[N];
void bfs(int u){
    queue<int> q;
    q.push(u);
    st[u] = true;
    while(q.size()){
        auto a = q.front();
        q.pop();
        cout << a << endl;
        for(int i = h[a]; i; i = ne[i]){
            int b = e[i], c = w[i];
            if(!st[b]){
                q.push(b);
                st[b] = true;
            }
        }
    }
}

int main(){
    cin >> n >> m; // 读入结点个数以及边的个数
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c; // a 和 b 之间有一条边，权值为 c
        add(a, b, c);
        add(b, a, c);
    }
    return 0;
}