当前位置：首页 > news >正文

图论常见算法

news 2025/6/24 5:26:00

图论常见算法

算法
- prim算法
- Dijkstra算法
用途
- 最小生成树（MST）：
- 最短路径：
- 拓扑排序：
- 关键路径：

算法	用途	适用条件	时间复杂度
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（最小堆）来选择当前最小权重边对应的顶点。

初始化：
选择一个起始顶点，将其加入生成树。
初始化一个优先队列（最小堆），用于存储所有连接生成树和非生成树顶点的边，按权重排序。
初始化一个数组key，记录每个顶点到生成树的最小权重，起始顶点为0，其余顶点为无穷大（表示未连接）。
初始化一个数组inMST，用于标记每个节点是否已经加入MST中。
迭代过程
从优先队列中取出权重最小的边，将其对应的顶点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（最小堆）来选择最短距离对应的顶点。

初始化：
选择一个起点。
初始化一个优先队列，用于存储到起点的距离。
初始化一个数组dis，用于存储从起点到每个节点的最短距离。起始顶点为0，其余顶点为无穷大（表示未连接）。
初始化一个数组vis，用于标记每个节点是否已经被访问过（即是否已经找到从起点到该节点的最短路径）。
迭代过程
从优先队列中取出离起点的最短距离对应的顶点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});}}}
}