干货分享｜图论的常见存储方式之邻接表

示意图

数据结构

以第一维度作为出度的点。每个数据结构的单元作为动态数组或链表的头部，进行延申存储。

struct Edge { int to; // 入度点 int val; // 权值 }; // 假设共有n个点 // 可动态延申的数据结构即可 vector<vector<Edge>> graph; vector<list<Edge>> graph; vector<Edge> graph[n];

操作

在存储中，根据需要不断添加，不会存在多余空间。因此在遍历时也可以保证这是必然村子的边。

// u出度点，v入度点，w权值
[u, v, w]

// 存储
graph[u].push_back({v, w});

// 遍历访问
for (int i = 0; i < graph[u].size(); i += 1) {
v = graph[u][i].v;
w = graph[u][i].w;
}

实战应用

class Solution { private: static constexpr int INF = 0x3f3f3f3f; struct Edge { int to; int val; }; public: int networkDelayTime(vector<vector<int>>& times, int n, int k) { // 邻接表，建图 auto graph = vector<vector<Edge>>(n + 1); for (auto&& edge : times) { int u = edge[0], v = edge[1], w = edge[2]; graph[u].push_back({v, w}); } // dijkstra 最短路算法 auto dis = vector<int>(n + 1, INF); auto vis = vector<bool>(n + 1, false); dis[k] = 0; int pointCnt = n; while (pointCnt--) { int nex = -1; int nexVal = INF; for (int i = 1; i <= n; i += 1) { if (vis[i] == false && dis[i] < nexVal) { nex = i; nexVal = dis[i]; } } if (nex == -1) { break; } vis[nex] = true; // 遍历邻接表 for (auto&& [to, val] : graph[nex]) { dis[to] = min(dis[to], dis[nex] + val); } }