Skip to content

图的存储

1、边列表🧀

1
2
3
4
5
struct Edge {
    char *startVertex;
    char *endVertex;
    int weight;
};

1
2
3
4
5
6
7
8
class Edge {
    string startVertex;
    string endVertex;
    int weight;
};

string vertex_list[MAX_SIZE]; // 顶点表
Edge edge_list[MAX_SIZE];     // 边表

Danger

查找操作时间复杂度：\(O(E)=O(n^2)\)，复杂度太高

2、邻接矩阵🧀

使用一个二维数组 adj 来存边：

  • 若 adj[u][v] == 1，表示存在从 u 到 v 的边；
  • 若 adj[u][v] == 0，表示不存在从 u 到 v 的边。

对于带边权的图，可以在 adj[u][v] 中存储从 u 到 v 的边的边权。

Tip

无向图：邻接矩阵对称，度就是第几行 \(1\) 的个数

有向图：邻接矩阵不一定对称，缺点是 空间浪费 ；行代表出度，列代表入度

二维数组：graph[NUM][NUM]

无向图：graph[i][j]=graph[j][i]

有向图：graph[i][j]!=graph[j][i]

graph[i][j]=INF表示i,j无边。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
    int g[10][10] = {0};
    g[1][3] = 1, g[2][5] = 6;
    g[4][2] = 8, g[2][1] = 2;
    g[3][1] = 2;
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
}
/*
0 0 1 0 0
2 0 0 0 6
2 0 0 0 0
0 8 0 0 0
0 0 0 0 0
*/

Bug

储存效率低下，只适用于稠密图。邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

复杂度🧀

  • 查询是否存在某条边：\(O(1)\)
  • 遍历一个点的所有出边：\(O(n)\)
  • 遍历整张图：\(O(n^2)\)
  • 空间复杂度：\(O(n^2)\)

3、邻接表🧀

  • 类似于孩子链表表示法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100]; // 邻接表
int main() {
    v[0].push_back(3);
    v[1].push_back(0);
    v[1].push_back(2);
    v[2].push_back(0);
    v[2].push_back(1);
    for (int i = 0; i <= 3; i++) {
        cout << i << ":";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
}
/*
0:3
1:0 2
2:0 1
3:
*/

复杂度（邻接表）🧀

  • 查询是否存在从 \(u\) 到 \(v\) 的边：\(O(d^+(u))\)
  • 如果对邻接表进行排序，则可以使用二分查找，复杂度为 \(O(\log d^+(u))\)
  • 遍历点 \(u\) 的所有出边：\(O(d^+(u))\)
  • 遍历整张图：\(O(n + m)\)
  • 空间复杂度：\(O(m)\)

Note

\(d^+(u)\) 表示点 \(u\) 的出度（即从 \(u\) 出发的边的数量）；

\(n\) 表示点数，\(m\) 表示边数；

邻接表默认不存储所有 \(n\) 个点的空表时，也可以视为 \(O(n + m)\) 空间。