最小生成树克鲁斯卡尔算法c++

时间: 2023-10-12 15:22:11 浏览: 35
克鲁斯卡尔算法是一种求解最小生成树的贪心算法,其基本思想是将所有边按照权值从小到大排序,然后依次加入到生成树中,如果加入一条边会形成环,则不加入这条边,直到生成树中包含所有的点为止。 下面是克鲁斯卡尔算法的 C 语言实现: ```c #include <stdio.h> #include <stdlib.h> #define MAX_N 1000 #define MAX_M 10000 typedef struct { int u, v, w; } Edge; Edge edges[MAX_M]; int fa[MAX_N]; int cmp(const void *a, const void *b) { return ((Edge *) a)->w - ((Edge *) b)->w; } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < m; ++i) { scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w); } qsort(edges, m, sizeof(Edge), cmp); for (int i = 1; i <= n; ++i) { fa[i] = i; } int ans = 0, cnt = 0; for (int i = 0; i < m; ++i) { int u = edges[i].u, v = edges[i].v, w = edges[i].w; int fu = find(u), fv = find(v); if (fu != fv) { fa[fu] = fv; ans += w; ++cnt; if (cnt == n - 1) break; } } printf("%d\n", ans); return 0; } ``` 首先定义了一个 `Edge` 结构体,用来表示边,其中 `u` 和 `v` 表示边的两个端点,`w` 表示边的权值。接下来定义了一个 `cmp` 函数,用来对边按照权值从小到大排序。然后定义了一个 `find` 函数,用来查找某个点所在的集合。`fa` 数组用来记录每个点所在的集合的根节点。 在 `main` 函数中,首先读入点数和边数,然后读入每条边的信息,并将所有边按照权值从小到大排序。接着初始化每个点所在的集合,然后依次将每条边加入生成树中,如果加入一条边会形成环,则不加入这条边,直到生成树中包含所有的点为止。最后输出生成树的权值和即可。

相关推荐

下面是克鲁斯卡尔最小生成树算法的C++代码示例: cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 边的结构体 struct Edge { int src, dest, weight; }; // 并查集的结构体 struct Subset { int parent, rank; }; // 比较函数,用于按边的权重进行排序 bool compare(Edge a, Edge b) { return a.weight < b.weight; } // 查找操作,寻找元素所属集合的根节点 int find(vector<Subset>& subsets, int i) { if (subsets[i].parent != i) { subsets[i].parent = find(subsets, subsets[i].parent); } return subsets[i].parent; } // 合并操作,将两个集合进行合并 void unionSet(vector<Subset>& subsets, int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); if (subsets[xroot].rank < subsets[yroot].rank) { subsets[xroot].parent = yroot; } else if (subsets[xroot].rank > subsets[yroot].rank) { subsets[yroot].parent = xroot; } else { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } // 克鲁斯卡尔最小生成树算法 void kruskalMST(vector<Edge>& edges, int V) { vector<Edge> result; // 存储最小生成树的边 // 按照边的权重进行排序 sort(edges.begin(), edges.end(), compare); vector<Subset> subsets(V); for (int i = 0; i < V; i++) { subsets[i].parent = i; subsets[i].rank = 0; } int e = 0; // 用于控制结果数组的下标 int i = 0; // 用于控制排序后的边数组的下标 while (e < V - 1 && i < edges.size()) { Edge nextEdge = edges[i++]; int x = find(subsets, nextEdge.src); int y = find(subsets, nextEdge.dest); if (x != y) { result.push_back(nextEdge); unionSet(subsets, x, y); e++; } } // 输出最小生成树的边及其权重 cout << "最小生成树的边:" << endl; for (int i = 0; i < result.size(); i++) { cout << result[i].src << " - " << result[i].dest << ",权重:" << result[i].weight << endl; } } int main() { int V, E; cout << "请输入顶点数:"; cin >> V; cout << "请输入边数:"; cin >> E; vector<Edge> edges(E); for (int i = 0; i < E; i++) { cout << "请输入第 " << i + 1 << " 条边的起点、终点和权重:"; cin >> edges[i].src >> edges[i].dest >> edges[i].weight; } kruskalMST(edges, V); return 0; } 这段代码实现了克鲁斯卡尔最小生成树算法,通过输入顶点数和边数,然后逐条输入边的起点、终点和权重,最后输出最小生成树的边及其权重。注意,该代码中使用了并查集来判断是否形成环路,并使用了排序算法进行边的排序。
以下是一个使用克鲁斯卡尔算法实现最小生成树的C++代码示例: cpp #include <iostream> #include <algorithm> using namespace std; struct Edge { int from; int to; int weight; }; bool compare(Edge a, Edge b) { return a.weight < b.weight; } class KruskalMST { private: Edge* edges; int numEdges; int numVertices; int* parent; public: KruskalMST(Edge* edges, int numEdges, int numVertices) { this->edges = edges; this->numEdges = numEdges; this->numVertices = numVertices; parent = new int[numVertices]; for (int i = 0; i < numVertices; i++) { parent[i] = i; } } int find(int vertex) { if (parent[vertex] != vertex) { parent[vertex] = find(parent[vertex]); } return parent[vertex]; } void unionSets(int x, int y) { int rootX = find(x); int rootY = find(y); parent[rootX] = rootY; } void kruskal() { sort(edges, edges + numEdges, compare); Edge* result = new Edge[numVertices - 1]; int count = 0; int i = 0; while (count < numVertices - 1) { Edge currentEdge = edges[i]; int fromRoot = find(currentEdge.from); int toRoot = find(currentEdge.to); if (from != toRoot) { result[count] = currentEdge; unionSets(fromRoot,Root); count++; } i++; } cout << "最小生成树的边:" << endl; for (int i = 0; i < numVertices - 1; i++) { cout << result[i].from << " - " << result[i].to << " 权重:" << result[i].weight << endl; } } }; int main() { int numVertices; int numEdges; cout << "输入顶点个数:" << endl; cin >> numVertices; cout << "输入边的个数:" << endl; cin >> numEdges; Edge* edges = new Edge[numEdges]; for (int i = 0; i < numEdges; i++) { cout << "第" << i + 1 << "条路径:" << endl; cin >> edges[i].from; cin >> edges[i].to; cin >> edges[i].weight; } KruskalMST mst(edges, numEdges, numVertices); mst.kruskal(); return 0; }
以下是使用克鲁斯卡尔算法求最小生成树的C++代码: cpp #include <iostream> #include <algorithm> using namespace std; // 边的结构体,包含起点、终点和边权值 struct Edge { int u, v, w; }; const int MAXN = 1005; // 最大点数 Edge edges[MAXN]; // 存储所有边的数组 int father[MAXN]; // 并查集数组,用于判断连通性 // 比较两条边的权值,按从小到大排序 bool cmp(Edge a, Edge b) { return a.w < b.w; } // 并查集查找祖先节点 int find(int x) { if (father[x] == x) return x; return father[x] = find(father[x]); } int main() { int n, m; // n表示点数,m表示边数 cin >> n >> m; // 读入所有边,并按权值从小到大排序 for (int i = 0; i < m; i++) { cin >> edges[i].u >> edges[i].v >> edges[i].w; } sort(edges, edges + m, cmp); // 初始化并查集数组 for (int i = 1; i <= n; i++) { father[i] = i; } int ans = 0; // 最小生成树的边权值之和 int count = 0; // 已加入最小生成树的边数 for (int i = 0; i < m; i++) { int u = edges[i].u, v = edges[i].v, w = edges[i].w; int fu = find(u), fv = find(v); // 查找u和v的祖先节点 if (fu != fv) { // 如果u和v不在同一连通块中 father[fu] = fv; // 将u所在连通块合并到v所在连通块中 ans += w; // 将该边加入最小生成树 count++; if (count == n - 1) break; // 已经加入n-1条边,最小生成树已完成 } } cout << ans << endl; // 输出最小生成树的边权值之和 return 0; } 该代码使用了并查集来判断连通性,并按边权值从小到大排序后逐条加入最小生成树中。
以下是克鲁斯卡尔算法的C++代码实现: cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 定义边的结构体 struct Edge { int src, dest, weight; }; // 比较函数,用于对边按权重进行排序 bool compare(Edge a, Edge b) { return a.weight < b.weight; } // 并查集的初始化 void init(vector<int>& parent, int n) { for (int i = 0; i < n; i++) { parent[i] = i; } } // 查找祖宗节点 int find(vector<int>& parent, int x) { if (x != parent[x]) { parent[x] = find(parent, parent[x]); } return parent[x]; } // 合并两个集合 void merge(vector<int>& parent, int a, int b) { int rootA = find(parent, a); int rootB = find(parent, b); if (rootA != rootB) { parent[rootA] = rootB; } } // 克鲁斯卡尔算法 void kruskal(vector<Edge>& edges, int n) { // 对边按权重进行排序 sort(edges.begin(), edges.end(), compare); vector<int> parent(n); init(parent, n); vector<Edge> result; int cost = 0; for (Edge edge : edges) { int srcRoot = find(parent, edge.src); int destRoot = find(parent, edge.dest); // 如果两个顶点的祖宗节点不同,说明不会形成环,可以加入最小生成树 if (srcRoot != destRoot) { result.push_back(edge); cost += edge.weight; merge(parent, srcRoot, destRoot); } } // 输出最小生成树的边和总权重 for (Edge edge : result) { cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl; } cout << "Total cost: " << cost << endl; } int main() { int n = 6; // 顶点的个数 vector<Edge> edges = { {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2}, {2, 3, 4}, {3, 4, 2}, {4, 5, 6} }; kruskal(edges, n); return 0; }
以下是克鲁斯卡尔算法的C语言代码实现: #include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 // 最大顶点数 #define MAX_EDGE_NUM 100 // 最大边数 typedef char VertexType; // 顶点类型 typedef int EdgeType; // 权值类型 typedef struct { VertexType vertexes[MAX_VERTEX_NUM]; // 顶点集合 EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 边集合 int vertex_num; // 顶点数 int edge_num; // 边数 } Graph; typedef struct { int begin; // 起点 int end; // 终点 EdgeType weight; // 权值 } Edge; int find(int *parent, int f) { while (parent[f] > 0) { f = parent[f]; } return f; } void kruskal(Graph *g) { Edge edges[MAX_EDGE_NUM]; int parent[MAX_VERTEX_NUM] = {0}; // 初始化边集合 int k = 0; for (int i = 0; i < g->vertex_num; i++) { for (int j = i + 1; j < g->vertex_num; j++) { if (g->edges[i][j] != 0) { edges[k].begin = i; edges[k].end = j; edges[k].weight = g->edges[i][j]; k++; } } } // 按权值升序排序 for (int i = 0; i < g->edge_num - 1; i++) { for (int j = i + 1; j < g->edge_num; j++) { if (edges[i].weight > edges[j].weight) { Edge tmp = edges[i]; edges[i] = edges[j]; edges[j] = tmp; } } } // 初始化parent数组 for (int i = 0; i < g->vertex_num; i++) { parent[i] = 0; } // 遍历边集合 printf("Kruskal Algorithm:\n"); for (int i = 0; i < g->edge_num; i++) { int begin = edges[i].begin; int end = edges[i].end; int weight = edges[i].weight; int root1 = find(parent, begin); int root2 = find(parent, end); if (root1 != root2) { parent[root1] = root2; printf("(%c, %c) %d\n", g->vertexes[begin], g->vertexes[end], weight); } } } int main() { Graph g = { {'A', 'B', 'C', 'D', 'E', 'F', 'G'}, { {0, 12, 0, 0, 0, 16, 14}, {12, 0, 10, 0, 0, 7, 0}, {0, 10, 0, 3, 5, 6, 0}, {0, 0, 3, 0, 4, 0, 0}, {0, 0, 5, 4, 0, 2, 8}, {16, 7, 6, 0, 2, 0, 9}, {14, 0, 0, 0, 8, 9, 0}, }, 7, 12 }; kruskal(&g); return 0; } 这里我们采用邻接矩阵的方式存储图,并实现了一个find函数来查找某个节点的根节点。kruskal函数中首先初始化了边集合,然后按照权值升序排序。接着初始化parent数组,然后遍历边集合,对于每一条边,我们分别找到它两个节点的根节点,如果根节点不同,说明这两个节点不在同一个连通分量中,我们将它们合并,并输出这条边。最终输出的就是最小生成树的边集合。
克鲁斯卡尔算法是一种求解最小生成树的贪心算法,其基本思想是按照边的权值从小到大排序,依次选择权值最小且不构成环的边加入生成树中,直到生成树中有 n-1 条边为止。下面是 C++ 实现克鲁斯卡尔算法的示例代码: c++ #include <iostream> #include <algorithm> using namespace std; const int MAXN = 1000; // 最大顶点数 const int MAXM = 10000; // 最大边数 int n, m; // 顶点数和边数 int fa[MAXN]; // 并查集数组 struct edge { int u, v, w; // 边的起点、终点和权值 } e[MAXM]; // 存储边的数组 bool cmp(edge a, edge b) { // 排序函数,按边权升序排序 return a.w < b.w; } int find(int x) { // 并查集查找函数 return fa[x] == x ? x : fa[x] = find(fa[x]); } int kruskal() { // 克鲁斯卡尔算法函数 int ans = 0, cnt = 0; for (int i = 1; i <= n; ++i) fa[i] = i; // 初始化并查集 sort(e + 1, e + m + 1, cmp); // 对边按权值升序排序 for (int i = 1; i <= m; ++i) { // 枚举所有边 int u = find(e[i].u), v = find(e[i].v); if (u != v) { // 如果不在同一个连通块中 fa[u] = v; // 合并连通块 ans += e[i].w; // 计算最小生成树的权值 ++cnt; if (cnt == n - 1) break; // 边数达到最大值,退出循环 } } return ans; } int main() { cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> e[i].u >> e[i].v >> e[i].w; } int ans = kruskal(); cout << ans << endl; return 0; } 在该程序中,使用结构体 edge 存储边的起点、终点和权值,使用并查集维护连通块,使用排序函数 cmp 将边按权值升序排序,使用函数 kruskal 实现克鲁斯卡尔算法,并返回最小生成树的权值。在主函数中,输入顶点数和边数,读入边的信息,调用函数 kruskal,输出最小生成树的权值。
下面是使用C++语言实现的Kruskal算法代码: c++ #include <iostream> #include <vector> #include <algorithm> using namespace std; struct Edge { int u, v, w; Edge(int a, int b, int c) { u = a; v = b; w = c; } }; bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; } class DisjointSet { public: vector<int> parent, rank; DisjointSet(int n) { parent.resize(n); rank.resize(n); for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } } int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unite(int x, int y) { int px = find(x); int py = find(y); if (px == py) return; if (rank[px] < rank[py]) { parent[px] = py; } else if (rank[px] > rank[py]) { parent[py] = px; } else { parent[py] = px; rank[px]++; } } }; class Kruskal { public: int n; vector<Edge> edges; Kruskal(int n) { this->n = n; } void addEdge(int u, int v, int w) { edges.push_back(Edge(u, v, w)); } vector<Edge> mst() { sort(edges.begin(), edges.end(), cmp); DisjointSet ds(n); vector<Edge> tree; for (int i = 0; i < edges.size(); i++) { Edge e = edges[i]; if (ds.find(e.u) != ds.find(e.v)) { ds.unite(e.u, e.v); tree.push_back(e); } } return tree; } }; int main() { Kruskal k(5); k.addEdge(0, 1, 2); k.addEdge(0, 3, 6); k.addEdge(1, 2, 3); k.addEdge(1, 3, 8); k.addEdge(1, 4, 5); k.addEdge(2, 4, 7); k.addEdge(3, 4, 9); vector<Edge> tree = k.mst(); for (int i = 0; i < tree.size(); i++) { printf("%d - %d : %d\n", tree[i].u, tree[i].v, tree[i].w); } return 0; } 这是一个简单的Kruskal实现,可以添加边然后计算最小生成树。这个实现使用了一个自定义的DisjointSet类来实现并查集。
以下是使用Prim算法求解无向图的最小生成树的C++代码: c++ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN=1e3+10; const int INF=0x3f3f3f3f; int n,m,ans; int vis[MAXN],dis[MAXN]; int g[MAXN][MAXN]; void prim() { memset(vis,0,sizeof(vis)); memset(dis,INF,sizeof(dis)); for(int i=1;i<=n;i++) dis[i]=g[1][i]; vis[1]=1;ans=0; for(int i=1;i<n;i++) { int pos,minn=INF; for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]<minn) minn=dis[j],pos=j; vis[pos]=1;ans+=dis[pos]; for(int j=1;j<=n;j++) if(!vis[j]) dis[j]=min(dis[j],g[pos][j]); } } int main() { while(~scanf("%d%d",&n,&m)) { memset(g,INF,sizeof(g)); for(int i=1;i<=m;i++) { int u,v,c; scanf("%d%d%d",&u,&v,&c); g[u][v]=g[v][u]=c; } prim(); printf("%d\n",ans); } return 0; } 以下是使用Kruskal算法求解无向图的最小生成树的C++代码: c++ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN=1e3+10; const int INF=0x3f3f3f3f; int n,m,ans; int fa[MAXN]; struct edge { int u,v,c; bool operator < (const edge& e) const { return c<e.c; } }e[MAXN*MAXN]; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void kruskal() { sort(e+1,e+m+1); int cnt=0; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int u=e[i].u,v=e[i].v,c=e[i].c; int x=find(u),y=find(v); if(x!=y) { fa[x]=y;ans+=c; cnt++; if(cnt==n-1) break; } } } int main() { while(~scanf("%d%d",&n,&m)) { memset(fa,0,sizeof(fa)); memset(e,0,sizeof(e)); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c); kruskal(); printf("%d\n",ans); } return 0; }
以下是使用C++实现Prim算法和Kruskal算法求解带权连通图的最小生成树的程序: c++ #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 1001; const int INF = 0x3f3f3f3f; struct Edge{ int u, v, w; }edge[MAXN*MAXN/2]; int n, m; // n为节点数,m为边数 int G[MAXN][MAXN]; // 邻接矩阵存图 int d[MAXN], vis[MAXN]; // d数组记录节点到生成树的最短距离,vis数组记录节点是否已加入生成树 int pre[MAXN]; // 记录每个节点在生成树中的前驱节点 // Prim算法 void Prim(int s){ memset(d, INF, sizeof(d)); // 初始化d数组 memset(vis, 0, sizeof(vis)); // 初始化vis数组 d[s] = 0; // 节点s到生成树的最短距离为0 for(int i=0; i<n; i++){ int u = -1; // u表示当前离生成树最近的节点 for(int j=0; j<n; j++){ if(!vis[j] && (u==-1 || d[j]<d[u])){ u = j; } } vis[u] = true; for(int v=0; v<n; v++){ if(!vis[v] && d[v]>G[u][v]){ d[v] = G[u][v]; pre[v] = u; } } } } // Kruskal算法 int fa[MAXN]; // 并查集数组 bool cmp(Edge a, Edge b){ return a.w < b.w; } int find(int x){ if(fa[x] == x) return x; return fa[x] = find(fa[x]); } void Kruskal(){ sort(edge, edge+m, cmp); // 将边按权值从小到大排序 for(int i=0; i<n; i++) fa[i] = i; // 初始化并查集数组 for(int i=0; i<m; i++){ int u = edge[i].u, v = edge[i].v, w = edge[i].w; int x = find(u), y = find(v); if(x != y){ // 如果不在同一个集合中,则加入生成树 pre[v] = u; fa[x] = y; } } } int main(){ cin >> n >> m; // 输入节点数和边数 memset(G, INF, sizeof(G)); // 初始化邻接矩阵为INF for(int i=0; i<m; i++){ int u, v, w; cin >> u >> v >> w; G[u][v] = G[v][u] = w; // 无向图 edge[i].u = u; edge[i].v = v; edge[i].w = w; } // Prim算法求解最小生成树 Prim(0); cout << "Prim Algorithm:\n"; for(int i=1; i<n; i++){ cout << pre[i] << " -> " << i << " : " << d[i] << "\n"; } // Kruskal算法求解最小生成树 Kruskal(); cout << "Kruskal Algorithm:\n"; for(int i=1; i<n; i++){ cout << pre[i] << " -> " << i << " : " << G[pre[i]][i] << "\n"; } return 0; } 程序中的Prim算法和Kruskal算法都使用了前驱节点数组pre来记录生成树的构造过程,输出最小生成树的边时只需按照pre数组输出即可。
以下是使用邻接矩阵实现图的算法和测试代码: c++ #include <iostream> #include <cstring> using namespace std; const int MAXN = 100; const int INF = 0x3f3f3f3f; int n; // 图中顶点数 int G[MAXN][MAXN]; // 邻接矩阵 // 普里姆算法生成最小生成树 void prim(int s) { int d[MAXN]; // 存储当前各个顶点到最小生成树的最短距离 bool vis[MAXN] = {false}; // 标记顶点是否已经在最小生成树中 memset(d, INF, sizeof(d)); // 初始化距离为无穷大 d[s] = 0; // 起点到自己的距离为0 for (int i = 0; i < n; i++) { int u = -1, min_d = INF; // 找到距离最小的顶点 for (int j = 0; j < n; j++) { if (!vis[j] && d[j] < min_d) { u = j; min_d = d[j]; } } if (u == -1) return; // 找不到可连接的顶点 vis[u] = true; // 将顶点加入最小生成树 for (int v = 0; v < n; v++) { if (!vis[v] && G[u][v] < d[v]) { d[v] = G[u][v]; // 更新最短距离 } } } } // 克鲁斯卡尔算法生成最小生成树 struct edge { int u, v, w; // 边的起点、终点和权值 bool operator<(const edge& E) const { return w < E.w; // 按照权值从小到大排序 } } edges[MAXN * MAXN]; // 存储所有边 int fa[MAXN]; // 并查集 int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void kruskal() { int cnt = 0; // 记录加入最小生成树的边数 for (int i = 0; i < n; i++) fa[i] = i; // 初始化并查集 sort(edges, edges + n * (n - 1) / 2); // 将边按照权值排序 for (int i = 0; i < n * (n - 1) / 2; i++) { int u = edges[i].u, v = edges[i].v, w = edges[i].w; int fu = find(u), fv = find(v); if (fu != fv) { // 如果不在同一个连通块中 fa[fu] = fv; // 合并连通块 cnt++; // 边数+1 if (cnt == n - 1) break; // 边数达到n-1,生成树完成 } } } // Dijkstra算法求单源最短路径 void dijkstra(int s, int d[]) { bool vis[MAXN] = {false}; // 标记顶点是否已经确定最短路径 memset(d, INF, sizeof(d)); // 初始化距离为无穷大 d[s] = 0; // 起点到自己的距离为0 for (int i = 0; i < n; i++) { int u = -1, min_d = INF; // 找到距离最小的顶点 for (int j = 0; j < n; j++) { if (!vis[j] && d[j] < min_d) { u = j; min_d = d[j]; } } if (u == -1) return; // 找不到可连接的顶点 vis[u] = true; // 将顶点加入最短路径 for (int v = 0; v < n; v++) { if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; // 更新最短距离 } } } } int main() { cin >> n; memset(G, INF, sizeof(G)); // 初始化邻接矩阵为无穷大 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int w; cin >> w; if (w != -1) G[i][j] = w; // 如果有边,存储边的权值 } } // 测试普里姆算法 prim(0); // 测试克鲁斯卡尔算法 kruskal(); // 测试Dijkstra算法 int s; cin >> s; int d[MAXN]; dijkstra(s, d); // 输出最小生成树和最短路径 cout << "最小生成树:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (G[i][j] != INF && find(i) == find(j)) { cout << i << " " << j << " " << G[i][j] << endl; } } } cout << "最短路径:" << endl; for (int i = 0; i < n; i++) { if (i == s) continue; cout << s << " " << i << " " << d[i] << endl; } return 0; }

最新推荐

http协议接口及代码解析(超详细).docx

Http定义了与服务器交互的不同方法,最基本的方法有4种,分别是GET,POST,PUT,DELETE。URL全称是资源描述符,我们可以这样认为:一个URL地址,它用于描述一个网络上的资源,而HTTP中的GET,POST,PUT,DELETE就对应着对这个资源的查,改,增,删4个操作。到这里,大家应该有个大概的了解了,GET一般用于获取/查询资源信息,而POST一般用于更新资源信息。 1.根据HTTP规范,GET用于信息获取,而且应该是安全的和幂等的。 2.根据HTTP规范,POST表示可能修改变服务器上的资源的请求。 (1).所谓安全的意味着该操作用于获取信息而非修改信息。换句话说,GET 请求一般不应产生副作用。就是说,它仅仅是获取资源信息,就像数据库查询一样,不会修改,增加数据,不会影响资源的状态.但在实际应用中,以上2条规定并没有这么严格。引用别人文章的例子:比如,新闻站点的头版不断更新。虽然第二次请求会返回不同的一批新闻,该操作仍然被认为是安全的和幂等的,因为它总是返回当前的新闻。从根本上说,如果目标是当用户打开一个链接时,他可以确信从自身的角度来看没有改变资源即可。

航班进出港管理系统.zip

① 系统环境:Windows/Mac ② 开发语言:Java ③ 框架:SpringBoot ④ 架构:B/S、MVC ⑤ 开发环境:IDEA、JDK、Maven、Mysql ⑥ JDK版本:JDK1.8 ⑦ Maven包:Maven3.6 ⑧ 数据库:mysql 5.7 ⑨ 服务平台:Tomcat 8.0/9.0 ⑩ 数据库工具:SQLyog/Navicat ⑪ 开发软件:eclipse/myeclipse/idea ⑫ 浏览器:谷歌浏览器/微软edge/火狐 ⑬ 技术栈:Java、Mysql、Maven、Springboot、Mybatis、Ajax、Vue等 最新计算机软件毕业设计选题大全 https://blog.csdn.net/weixin_45630258/article/details/135901374 摘 要 目 录 第1章 绪论 1.1选题动因 1.2背景与意义 第2章 相关技术介绍 2.1 MySQL数据库 2.2 Vue前端技术 2.3 B/S架构模式 2.4 ElementUI介绍 第3章 系统分析 3.1 可行性分析 3.1.1技术可行性 3.1.2经济可行性 3.1.3运行可行性 3.2 系统流程 3.2.1 操作信息流程 3.2.2 登录信息流程 3.2.3 删除信息流程 3.3 性能需求 第4章 系统设计 4.1系统整体结构 4.2系统功能设计 4.3数据库设计 第5章 系统的实现 5.1用户信息管理 5.2 图片素材管理 5.3视频素材管理 5.1公告信息管理 第6章 系统的测试 6.1软件测试 6.2测试环境 6.3测试测试用例 6.4测试结果

DAC简介及参考电路PPT学习教案.pptx

DAC简介及参考电路PPT学习教案.pptx

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

OceanBase数据库简介及原理解析

# 1. OceanBase数据库概述 ## 1.1 OceanBase数据库的发展历程 OceanBase数据库是由阿里巴巴集团自主研发的一款分布式关系型数据库系统,起源于阿里集团的业务需求和技术挑战。自2010年开始研发,经过多年的迭代和优化,OceanBase已经成为阿里巴巴集团重要的核心数据库产品之一。在实际的业务场景中,OceanBase已经被广泛应用于金融、电商、物流等各个领域。 ## 1.2 OceanBase数据库的特点和优势 OceanBase数据库具有以下特点和优势: - **分布式架构**:OceanBase采用多副本分布式架构,可以实现高可用和数据容灾。 -

python的pandas读取excel怎么将excel表里的列从1开始而不是0

在 Pandas 中,数据框的列默认从0开始编号,但我们可以通过自定义函数来进行数据列的转换。可以先将读取的数据框列的第一个值设为1,然后对后续列进行递增处理。 以下是示例代码: ```python import pandas as pd # 读取 Excel 文件 df = pd.read_excel('your_excel_file.xlsx') # 定义函数将列从1开始 def reset_column(x): return str(int(x) + 1) # 应用函数到所有列名 df = df.rename(columns=reset_column) # 打印数据框

第三章薪酬水平、薪酬系统的运行与控制.pptx

第三章薪酬水平、薪酬系统的运行与控制.pptx

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依

理解MVC架构:Laravel框架的核心设计

# 1. 第1章 项目立项与概述 ## 1.1 动机 随着互联网的快速发展,Web应用的开发需求不断增加。为了提高开发效率、代码可维护性和团队协作效率,我们决定采用MVC架构来设计我们的Web应用。 ## 1.2 服务器状态 我们的服务器环境采用了LAMP(Linux + Apache + MySQL + PHP)架构,满足了我们Web应用开发的基本需求,但为了更好地支持MVC架构,我们将对服务器进行适当的配置和优化。 ## 1.3 项目立项 经过团队讨论和决定,决定采用Laravel框架来开发我们的Web应用,基于MVC架构进行设计和开发,为此做出了项目立项。 ## 1.4 项目概况

如何将HDFS上的文件读入到Hbase,用java

要将HDFS上的文件读入到HBase,可以使用Java编写MapReduce程序实现,以下是实现步骤: 1. 首先需要创建一个HBase表,可使用HBase Shell或Java API创建; 2. 编写MapReduce程序,其中Map阶段读取HDFS上的文件,将数据转换成Put对象,然后将Put对象写入到HBase表中; 3. 在MapReduce程序中设置HBase表名、列族名、列名等参数; 4. 在程序运行前,需要将HBase相关的jar包和配置文件加入到classpath中; 5. 最后提交MapReduce任务运行即可。 以下是示例代码: ``` Configuration