1. 理论

1.1 稠密图和稀疏图

在图论中，稠密图和稀疏图是对图中边的分布情况的一种描述

根据边数量和节点数量分辨

对于一个具有 n 个顶点的图

• 如果是有向图，其边数最多为 n(n - 1)
• 如果是无向图，其边数最多为 n(n - 1) / 2

那么可以大致根据边数可以粗略分辨一个图是稠密还是稀疏

• 如果是有向图，其边数无限接近 n(n - 1)，则为稠密图，反之稀疏
• 如果是无向图，其边数无限接近 n(n - 1) / 2，则为稠密图，反之稀疏

根据存储方式和空间复杂度分辨

• 如果使用邻接矩阵来存储图时所占用的空间与使用邻接表存储时相差不大，甚至邻接矩阵更优，那么该图大概率是稠密图。因为邻接矩阵的空间复杂度为O(n ^ 2) ，而邻接表的空间复杂度为O(n + 边数)，如果边数无限接近 n，那么邻接表的空间复杂度也是O(n ^ 2)

根据算法效率和时间复杂度分辨

一般来说，如果一幅图中不同的边的数 量在顶点总数 n 的一个小的常数倍以内（< n^2），那么我们就认为这幅图是稀疏的，否则则是稠密的。
在 单源最短路 - Dijkstra 算法中，根据节点数量 n 和边的实际数量 m 决定这个图是稠密还是稀疏

• 比较 n^2 和 m * logm 的大小
• 如果 n ^ 2 比较小，说明是稠密图
• 如果 m * logm 比较小，说明是稀疏图

1.2 邻接矩阵和邻接表

• 邻接矩阵和邻接表是图论中两种常用的"表示图"的数据结构

邻接矩阵

存储方式

• 用一个二维数组 arr 存储图（大小为 n * n，n为图的节点数量）
• 如果 x 至 y 存在一条边，arr[x][y] 对应的点意思是从 x 节点 到 y 节点的权值
• 如果 x 至 y 不存在边，可以放 0 或者 其他值。

特点

• 直观性：能够直观地表示图中顶点之间的连接关系，通过矩阵的行列对应顶点，元素值表示边的存在与否或边的权值，易于理解和实现。
• 易于判断顶点间的连接性：要判断顶点和是否有边相连，只需查看矩阵中的值即可，时间复杂度为 O(1)。
• 适合稠密图：对于边数相对较多的稠密图，邻接矩阵能够高效地存储和处理图的信息，不会浪费过多的存储空间。

示例代码

vector<vector<int>> g(n,vector<int>(n));  //二维数组
.... // 根据题给出的边输入到对应的坐标中

邻接表

存储方式

• 邻接表是一种链式存储结构，用于表示图中每个顶点的邻接顶点集合

1. 首先需要一个长度为 n 的一维数组
2. 其次数组每个元素底下挂的不同长度的集合（集合每个元素存放的是（连接的节点 和 边的权值））

特点

• 高效存储稀疏图：对于边数较少的稀疏图，邻接表只存储实际存在的边，相比邻接矩阵能够节省大量的存储空间，空间复杂度为（n + m），其中 n 是顶点数，m 是边数。
• 方便遍历顶点的邻接点：通过遍历顶点对应的链表，可以快速获取该顶点的所有邻接顶点

示例代码

 typedef pair<int,int> pii; //利用pair存放 y 和 权值vector<vector<pii>> g(n + 1);  // 数组成员类型也可以是 list<pii>

1.3 易错点

重边

• 如果题目给的数据中，两个节点可能有多个边，邻接矩阵根据题意取最大值或者最小值，邻接表无需改变。

数据量

• 实际上大部分的题都是稀疏图，节点数量也可会很大，往往使用邻接矩阵会超出内存限制，因此首选用节省空间的邻接表构图比较稳妥，但不一定时间复杂度占优。

无向图的建图

• 在无向图中建图时需要注意，如果 x -> y 如果存在边
• 无论是邻接矩阵还是邻接表，都需要添加 x->y 和 y->x 的权值

743. 网络延迟时间（medium）

https://leetcode.cn/problems/network-delay-time/description/

• 邻接矩阵写法

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {int m = INT_MAX/2;//本题节点不多，可以构造邻接矩阵，g[i][j] 表示从i到j的边权值，如果到不了则为一个较大值vector<vector<int>> g(n + 1,vector<int>(n + 1,m)); for(auto& t : times) g[t[0]][t[1]] = t[2];//存从起点开始到当前点位的最短路径vector<int> dis(n + 1,m);  //起点路径长度设0dis[k] = 0; //每找到一个节点的最短路径，设为truevector<bool> fis(n +1); //记录找到最短路径节点的数量int count = 0; while(true){//1. 通过遍历找起点int x = -1;for(int i = 1;i<=n;i++){if(!fis[i] && (x == -1 || dis[i] < dis[x]))x = i;}//2. 判断起点是否合法if(dis[x] == m) return -1;//3. 如果能作为起点，说明此点已经有最短路径fis[x] = true;count++;//4. 如果count表示计数完毕，说明这个点已经是最后一个点，返回即可if(count == n) return dis[x];//5. 上面如果都没返回，这里更新每个点位的最短路径for(int i= 1;i<=n;i++){dis[i] = min(dis[i],dis[x] + g[x][i]);}}return -1;}
};

• 邻接表写法

class Solution {
public:typedef pair<int,int> pii;int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pii>> g(n + 1);for(auto& t:times)  g[t[0]].emplace_back(t[1],t[2]);priority_queue<pii,vector<pii>,greater<>> qe;qe.emplace(0,k);vector<int> dis(n + 1, -1);dis[k] = 0;int count = 0;while(qe.size()){auto [v,x] = qe.top();qe.pop();if(v > dis[x]) continue;if(++count == n) return v;for(auto &[y, len] : g[x]){int newdis = v + len;if(dis[y] == -1 || dis[y] > newdis){qe.emplace(newdis,y);dis[y] = newdis;}}}return -1;} 
};

3112. 访问消失节点的最少时间（medium）

https://leetcode.cn/problems/minimum-time-to-visit-disappearing-nodes/

class Solution {
public:typedef pair<int,int> pii;vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {vector<vector<pii>> g(n); //本题节点较多，适合构造邻接表for(auto &e : edges){//对于无向边，节点互相连通g[e[0]].emplace_back(e[1],e[2]);g[e[1]].emplace_back(e[0],e[2]);} //优化- 小根堆寻找起点priority_queue<pii,vector<pii>,greater<>> qe; qe.emplace(0,0);//记录 0 到所有节点的最短路径vector<int> dis(n, - 1); dis[0] = 0;while(qe.size()){//1. 寻找起点auto [l,x] = qe.top();qe.pop();//2. 这个点已经有存在更短路径，跳过下面步骤if(dis[x] < l)  continue;//3. 遍历以x做起点，到达其他节点的时间for(auto &[a,b] : g[x]){//计算从 0 到达这个点的总时长int newdis = dis[x] + b;//必须保证这个点不是最优状态，并且没消失if(newdis < disappear[a]){if(dis[a] == -1 || dis[a] > newdis){qe.emplace(newdis,a);dis[a] = newdis;}}} }return dis;}
};

3341. 到达最后一个房间的少时间 I（medium）

https://leetcode.cn/problems/find-minimum-time-to-reach-last-room-i/

class Solution {
public:int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};typedef tuple<int,int,int> tp;int minTimeToReach(vector<vector<int>>& moveTime) {int n = moveTime.size();int m = moveTime[0].size();//记录从（0,0）到所有点位的耗时vector<vector<int>> dis(n,vector<int>(m, -1));dis[0][0] = 0;//优化每次寻找起点的时间priority_queue<tp,vector<tp>,greater<>> qe;qe.emplace(0,0,0);while(qe.size()){//1. 找起点auto [t,x,y] = qe.top(); qe.pop();//2. if(dis[x][y] < t) continue; if(x == n - 1 && y == m - 1) return t;for(int i = 0;i<4;i++){int x1 = dx[i] + x;int y1 = dy[i] + y;if(x1>=0 && x1<n && y1>=0 && y1< m){int newtime = max(moveTime[x1][y1], dis[x][y]) + 1;if(dis[x1][y1] == -1 || dis[x1][y1] > newtime){dis[x1][y1] = newtime;qe.emplace(newtime,x1,y1);}}}}   return dis[n - 1][m - 1];}
};

3342. 到达最后一个房间的少时间 II（medium）

https://leetcode.cn/problems/find-minimum-time-to-reach-last-room-ii/

class Solution {
public:int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};typedef tuple<int,int,int> tp;int minTimeToReach(vector<vector<int>>& moveTime) {int n = moveTime.size();int m = moveTime[0].size();vector<vector<int>> dis(n,vector<int>(m, -1)); dis[0][0] = 0;priority_queue<tp,vector<tp>,greater<>> qe; qe.emplace(0,0,0);while(qe.size()){auto [t,x,y] = qe.top(); qe.pop();if(dis[x][y] < t) continue;if(x == n - 1 && y == m - 1) return t;for(int i = 0;i<4;i++){int x1 = dx[i] + x;int y1 = dy[i] + y;if(x1>=0 && x1<n && y1>=0 && y1< m){//除开第0个房间，其他房间横竖坐标相加为奇数则额外耗时1，否则额外耗时2int newtime = max(moveTime[x1][y1], dis[x][y]) + (x1 + y1 + 1)%2 + 1;if(dis[x1][y1] == -1 || dis[x1][y1] > newtime){dis[x1][y1] = newtime;qe.emplace(newtime,x1,y1);}}}}   return dis[n - 1][m - 1];}
};

2642. 设计可以求最短路径的图类（hard）

https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/

class Graph {typedef pair<int,int> pii;
public:Graph(int n, vector<vector<int>>& edges):_n(n){g.resize(_n);for(auto& e: edges) g[e[0]].emplace_back(e[1],e[2]);}void addEdge(vector<int> edge) {g[edge[0]].emplace_back(edge[1], edge[2]);}int shortestPath(int node1, int node2) {priority_queue<pii,vector<pii>,greater<>> qe;qe.emplace(0,node1);vector<int> dis(_n,-1);dis[node1] = 0;while(qe.size()){auto [v,x] = qe.top(); qe.pop();if(v > dis[x]) continue;if(x == node2) return v;for(auto&[y,len] : g[x]){   int newdis = v + len;if(dis[y] == -1 || dis[y] > newdis){dis[y] = newdis;qe.emplace(newdis,y);}}}  return -1;}
private:vector<vector<pii>> g; //邻接矩阵int _n = 0; //节点数量
};

1514. 概率最大的路径（medium）

https://leetcode.cn/problems/path-with-maximum-probability/

class Solution {
public:typedef pair<double,int> pdi;double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {vector<vector<pdi>> g(n);for(int i = 0;i<edges.size();i++) {g[edges[i][0]].emplace_back(succProb[i],edges[i][1]);g[edges[i][1]].emplace_back(succProb[i],edges[i][0]);}priority_queue<pdi> qe;qe.emplace(1,start_node);vector<double> dis(n, -1);dis[start_node] = 1;while(qe.size()){auto [v, x] = qe.top(); qe.pop();if(v < dis[x]) continue;if(x == end_node) return v;for(auto& [len, y] : g[x]){double newdis = v * len;if(dis[y] == -1 || dis[y] < newdis){dis[y] = newdis;qe.emplace(newdis,y);}}}return 0;}
};

1631. 最小体力消耗路径（medium）

https://leetcode.cn/problems/path-with-minimum-effort/

class Solution {
public:typedef tuple<int,int,int> tp;int dx[4] = {1,-1,0,0};int dy[4] = {0,0,1,-1};int minimumEffortPath(vector<vector<int>>& heights) {priority_queue<tp,vector<tp>,greater<>> qe;qe.emplace(0,0,0);int row = heights.size();int col = heights[0].size();vector<vector<int>> dis(row,vector<int>(col,-1));dis[0][0] = 0;while(qe.size()){auto [v, x, y] = qe.top();qe.pop();if(v > dis[x][y]) continue;if(x == row - 1 && y == col - 1) return v;for(int i = 0;i<4;i++){int x1 = dx[i] + x;int y1 = dy[i] + y;if(x1 >=0 && x1 < row && y1>=0 && y1 < col){int newdis = abs(heights[x1][y1] - heights[x][y]);newdis = max(newdis, v);if(dis[x1][y1] == -1 || dis[x1][y1] > newdis){dis[x1][y1] = newdis;qe.emplace(newdis,x1,y1);}}}}return -1;}
};

1786. 从第一个节点出发到最后一个节点的受限路径数（medium）

https://leetcode.cn/problems/number-of-restricted-paths-from-first-to-last-node/

class Solution {
public:typedef pair<int, int> pii;int N = 1e9 + 7;int countRestrictedPaths(int n, vector<vector<int>>& edges) {//找列出最小路径vector<vector<pii>> g(n + 1);for (auto& e : edges) {g[e[0]].emplace_back(e[1], e[2]);g[e[1]].emplace_back(e[0], e[2]);}priority_queue<pii, vector<pii>, greater<>> qe;qe.emplace(0, n);vector<int> dis(n + 1, -1);dis[n] = 0;while (qe.size()) {auto [v, x] = qe.top();qe.pop();if (dis[x] < v)continue;for (auto& [y, l] : g[x]) {int newdis = v + l;if (dis[y] == -1 || dis[y] > newdis) {dis[y] = newdis;qe.emplace(newdis, y);}}}// dpvector<int> index(n + 1);for (int i = 1; i <= n; i++)index[i] = i;sort(index.begin() + 1, index.end(),[&](int i, int j) { return dis[i] < dis[j]; });vector<int> dp(n + 1, 0);dp[n] = 1;for (int i = 2;;i++) {int a = index[i];for (auto& [node, l] : g[a])if (dis[a] > dis[node]) {dp[a] += dp[node];dp[a] %= N;}if (a == 1)break;}return dp[1] % N;}
};