图论常见算法

算法	用途	适用条件	时间复杂度
Kruskal	最小生成树	无向图（稀疏图）	O(E log E)
Prim	最小生成树	无向图（稠密图）	O(V^2) 或 O(E log V)
Dijkstra	单源最短路径	非负权图	O(V^2) 或 O(E + V log V)
Floyd	多源最短路径	允许负权边（无负权环）	O(V^3)
AOV	拓扑排序	有向无环图（DAG）	O(V + E)
AOE	关键路径	有向无环图（DAG）	O(V + E)

算法

prim算法

key[MAXN]：存储从MST到每个顶点的最小权重（边）。
inMST[MAXN]：标记每个顶点是否已经在MST中。
优先队列：使用priority_queue（最小堆）来选择当前最小权重边对应的顶点。

1. 初始化：
   选择一个起始顶点，将其加入生成树。
   初始化一个优先队列（最小堆），用于存储所有连接生成树和非生成树顶点的边，按权重排序。
   初始化一个数组key，记录每个顶点到生成树的最小权重，起始顶点为0，其余顶点为无穷大（表示未连接）。
   初始化一个数组inMST，用于标记每个节点是否已经加入MST中。

2. 迭代过程
   从优先队列中取出权重最小的边，将其对应的顶点u加入生成树。
   遍历u的所有邻接顶点v：如果v未被加入生成树，且边(u, v)的权重小于key[v]，则更新key[v]为(u, v)的权重，并将v加入优先队列。

typedef pair<int, int> pii;  // 用于表示 (权重, 节点)
const int INF = INT_MAX;void prim(int n, vector<vector<pii>>& adj) {vector<int> key(n, INF);  // 存储到每个节点的最小边权vector<bool> inMST(n, false);  // 标记节点是否在生成树中priority_queue<pii, vector<pii>, greater<pii>> pq;  // 最小堆，存储 (边权, 节点)key[0] = 0;  // 从节点 0 开始pq.push({0, 0});  // 初始时将起点加入堆while (!pq.empty()) {int u = pq.top().second;  // 当前节点pq.pop();if (inMST[u]) continue;  // 如果已经在生成树中，跳过inMST[u] = true;  // 标记为在生成树中// 遍历 u 的邻接节点for (auto& edge : adj[u]) {int v = edge.first;int weight = edge.second;// 如果节点 v 不在生成树中且通过 u 到 v 的边更短if (!inMST[v] && weight < key[v]) {key[v] = weight;pq.push({key[v], v});  // 更新最小堆}}}
}

Dijkstra算法

dis[MAXN]：存储从起点到每个节点的最短距离。
vis[MAXN]：标记每个节点是否已被访问。
优先队列：使用priority_queue（最小堆）来选择最短距离对应的顶点。

1. 初始化：
   选择一个起点。
   初始化一个优先队列，用于存储到起点的距离。
   初始化一个数组dis，用于存储从起点到每个节点的最短距离。起始顶点为0，其余顶点为无穷大（表示未连接）。
   初始化一个数组vis，用于标记每个节点是否已经被访问过（即是否已经找到从起点到该节点的最短路径）。

2. 迭代过程
   从优先队列中取出离起点的最短距离对应的顶点u。
   遍历u的所有邻接顶点v：如果v未被访问，且(u, v)的距离小于dis[v]，则更新dis[v]为(u, v)的距离，并将v加入优先队列。

struct edge {int v, w;
};struct node {int dis, u;bool operator>(const node& a) const { return dis > a.dis; }
};vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;void dijkstra(int n, int s) {memset(dis, 0x3f, (n + 1) * sizeof(int));memset(vis, 0, (n + 1) * sizeof(int));dis[s] = 0;q.push({0, s});while (!q.empty()) {int u = q.top().u;q.pop();if (vis[u]) continue;vis[u] = 1;// BFSfor (auto ed : e[u]) {int v = ed.v, w = ed.w;if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;q.push({dis[v], v});}}}
}

用途

最小生成树（MST）：

用途：最小生成树用于找到一个连通图中所有节点的最小连接总成本的树。它被广泛应用于网络设计、构建最优电路、电力网络、交通规划等领域。
实际应用：如设计最小成本的通讯网络、城市间的最短道路规划等。

最短路径：

用途：最短路径算法用于寻找图中两个节点之间的最短路径。它广泛应用于导航系统、网络路由、物流调度等。
实际应用：如计算地图上的最短路线、在网络中寻找数据传输的最优路径等。

拓扑排序：

用途：拓扑排序是有向无环图（DAG）的一种排序方式，确保每个节点都在它依赖的节点之前。它通常用于任务调度、编译器优化、项目计划等。
实际应用：如任务调度中的优先级排序、编译过程中的模块依赖关系等。

关键路径：

用途：关键路径方法（CPM）用于项目管理中，帮助确定哪些任务是“关键”的，即那些对项目完成时间有直接影响的任务。它能帮助管理者合理安排资源，避免延误。
实际应用：如建筑工程的项目管理、软件开发的进度控制等。