网站关键字怎么分割,新闻发布会,廊坊做网站优化,wordpress 主题 使用图论常见算法 算法prim算法Dijkstra算法 用途最小生成树#xff08;MST#xff09;#xff1a;最短路径#xff1a;拓扑排序#xff1a;关键路径#xff1a; 算法用途适用条件时间复杂度Kruskal最小生成树无向图#xff08;稀疏图#xff09;O(E log E)Prim最小生成树无… 图论常见算法 算法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拓扑排序有向无环图DAGO(V E)AOE关键路径有向无环图DAGO(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 pairint, int pii; // 用于表示 (权重, 节点)
const int INF INT_MAX;void prim(int n, vectorvectorpii adj) {vectorint key(n, INF); // 存储到每个节点的最小边权vectorbool inMST(n, false); // 标记节点是否在生成树中priority_queuepii, vectorpii, greaterpii 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; }
};vectoredge e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queuenode, vectornode, greaternode 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用于项目管理中帮助确定哪些任务是“关键”的即那些对项目完成时间有直接影响的任务。它能帮助管理者合理安排资源避免延误。 实际应用如建筑工程的项目管理、软件开发的进度控制等。
