C++算法
图论入门：基本概念与代码实现（邻接矩阵、邻接表、DFS/BFS）
图论基础涵盖顶点边集定义、有向无向图区分及连通性分析。存储方案包含邻接矩阵与邻接表（Vector/链式前向星）。遍历算法提供 DFS 与 BFS 的 C++ 实现，适配不同存储结构。
图论基础涵盖顶点边集定义、有向无向图区分及连通性分析。存储方案包含邻接矩阵与邻接表（Vector/链式前向星）。遍历算法提供 DFS 与 BFS 的 C++ 实现，适配不同存储结构。
图 G 是由顶点集 V 和边集 E 组成，记为 G=(V,E)，其中 V(G) 表示图 G 中顶点的有限非空集；E(G) 表示图 G 中顶点之间的关系（边）集合。若 V={v1,v2,…,vn}，则用 |V| 表示图 G 中顶点的个数，也称图 G 的阶，E={(u,v)|u∈V,v∈V}，用 |E| 表示图 G 中边的条数。
图是较线性表和树更为复杂的数据结构。 线性表中，除第一个和最后一个元素外，每个元素只有一个唯一的前驱和唯一的后继结点，元素和元素之间是一对一的关系； 在树形结构中，数据元素之间有着明显的层次关系，每个元素有唯一的双亲，但可能有多个孩子，元素和元素之间是一对多的关系； 而图形结构中，元素和元素之间的关系更加复杂，结点和结点之间的关系是任意的，任意两个结点之间都可能相关，图中元素和元素之间是多对多的关系。
顶点 v 的度是指与它相关联的边的条数，记作 deg(v)。由该顶点发出的边称为顶点的出度，到达该顶点的边称为顶点的入度。
无向图中，顶点的度等于该顶点的入度（indeg）和出度（outdev），即 deg(v)=indeg(v)=outdeg(v)。 有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点 v 的入度 indeg(v) 是以 v 为终点的有向边的条数，顶点 v 的出度 outdeg(v) 是以 v 为起始点的有向边的条数，deg(v)=indeg(v)+outdeg(v)。
G1_1 和 G1_2 为无向图 G1 的子图，G1_1 为 G1 的生成子图（G1_1包含G1的所有顶点）。 G2_1 和 G2_2 为有向图 G2 的子图，G2_1 为 G2 的生成子图（G2_1包含G2的所有顶点）。
概念关系总结 连通是顶点之间的二元关系。 连通图是满足'任意两顶点都连通'这一整体性质的图。 极大连通子图是从图中'抠'出来的、不能再大的连通子图。 连通分量就是无向图中的所有极大连通子图，是对非连通图结构的分解。
简单理解就是把原始图所有顶点拿出来在保证所有顶点都连通的前提下，用最少的边把它们连起来串成一颗 1 对多的树。
图的存储有两种：邻接矩阵和邻接表：
图的遍历分两种：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 数组里面放一个结构体或者是 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 带大家走一遍： 递归：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;
}
// 临接矩阵
#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;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online