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

示意图数据结构以第一维度作为出度的点。每个数据结构的单元作为动态数组或链表的头部进行延申存储。struct Edge { int to; // 入度点 int val; // 权值 }; // 假设共有n个点 // 可动态延申的数据结构即可 vectorvectorEdge graph; vectorlistEdge graph; vectorEdge 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(vectorvectorint times, int n, int k) { // 邻接表建图 auto graph vectorvectorEdge(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 vectorint(n 1, INF); auto vis vectorbool(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); } }