建图的三种方式
1.邻接矩阵
- 定义：是一个二维数组
matrix[n][n]，其中n是图中顶点的数量。对于无向图，如果顶点i和顶点j之间有边相连，则matrix[i][j]和matrix[j][i]的值为1（若边有权值，则存储权值），否则为0。对于有向图，若存在从顶点i到顶点j的边，则matrix[i][j]为1（或权值），matrix[j][i]为0。
- 优点：可以快速判断任意两个顶点之间是否有边相连，时间复杂度为$O(1)$。对于稠密图（边的数量接近顶点数量的平方），邻接矩阵的空间效率较高。
- 缺点：对于稀疏图（边的数量远小于顶点数量的平方），会浪费大量的空间，空间复杂度为$O(n^2)$。进行图的遍历等操作时，时间复杂度较高，例如遍历所有边需要$O(n^2)$的时间。
1
2
3
4
5
6
7
8
9
10
| int n, m // 节点数 n, 边数 m
cin >> n >> m;
vector<vector<int>> g(n + 1, vector<int>(n + 1, 0));
for(int i = 0; i < m; i++){
int uu, vv, ww;
cin >> uu >> vv >> ww;
// 有权无向图
g[uu][vv] = ww; // 所有的ww = 1时即为无权图
g[vv][uu] = ww; // 注释掉这一行即为有向图
}
|
2.邻接表
- 定义：是一种链表数组结构，对于图中的每个顶点，都有一个链表与之对应，链表中存储的是与该顶点相邻的顶点信息（包括顶点编号和边的权值等）。
- 优点：对于稀疏图，空间利用率高，只存储实际存在的边，空间复杂度为$O(n + m)$，其中
n是顶点数，m是边数。在进行图的遍历等操作时，时间复杂度通常较低，例如深度优先搜索和广度优先搜索的时间复杂度都为$O(n + m)$。
- 缺点：判断两个顶点之间是否有边相连的时间复杂度较高，最坏情况下需要遍历整个链表，时间复杂度为$O(d)$，
d是顶点的度（与该顶点相连的边的数量）。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int n, m; // 节点数 n, 边数 m
cin >> n >> m;
vector<vector<int>> g(n + 1);
for(int i = 0; i < m; i++){
int uu, vv, ww;
pair<int, int> pii;
cin >> uu >> vv >> ww;
pii = {vv, ww};
// 有权无向图
g[uu].push_back(pii); // 当ww = 1时即为无权图(即没有第三个参数时)
pii = {uu, ww};
g[vv].push_back(pii); // 注释掉这一行即为有向图
}
|
3.链式前向星
- 定义：是一种用数组模拟链表来存储图的方式。它通过几个数组来实现，通常有
head数组用于存储每个顶点的第一条边的编号，结构体Edge中，to数组存储边的终点，next数组存储与当前边同起点的下一条边的编号，w数组存储边的权值（如果有权值的话）。
- 优点：空间效率高，和邻接表类似，只存储实际存在的边，空间复杂度为$O(m)$。在遍历图的边时，代码实现相对简洁，且效率较高。
- 缺点：与邻接表类似，判断两个顶点之间是否有边相连的时间复杂度较高。代码实现相对邻接矩阵和邻接表来说，稍微复杂一些，需要对数组的操作有较好的理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const int MAXN = 1e5 + 10; // 节点数
const int MAXM = 2e5 + 10; // 边数
struct Edge{
int to; // 边的终点
int next; // 指向下一条边的编号
int w; // 边的权值
}edges[MAXM]; // 存储所有边
int head[MAXN]; // head[u] 表示以u为起点的第一条边在edges数组中的索引
int cnt = 0; // 边的数量
void addEdge(int u, int v, int w){ // 添加边
edges[cnt].to = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
}
|
总的来说，邻接矩阵适用于稠密图和需要快速判断边是否存在的场景；邻接表适用于稀疏图和需要频繁进行图遍历的场景；链式前向星则在一些对空间和代码实现效率有较高要求的图算法中较为常用。
