- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
我已经根据维基百科使用不相交集数据结构在 C++ 中实现了 Kruskal 算法,如下所示:
#include <stdio.h>
#include <algorithm>
#define MAX_EDGES 10000000
#define MAX_VERTICES 200001
using namespace std;
int num_edges,num_vertices;
int total_cost=0;
struct edge{
int v1,v2;
int cost;
};
struct comp{
bool operator()(const edge& e1,const edge& e2){
return e1.cost<e2.cost;
}
};
edge edges[MAX_EDGES];
int parent[MAX_VERTICES];
int rank[MAX_VERTICES];
int findset(int x){
if(x!=parent[x]){
parent[x]=findset(parent[x]);
}
return parent[x];
}
void merge(int x,int y){
int px=findset(x),py=findset(y);
if(rank[px]>rank[py]){
parent[py]=px;
}else{
parent[px]=py;
}
if(rank[px]==rank[py]){
++rank[py];
}
}
int main(){
FILE* in=fopen("input","r");
FILE* out=fopen("output","w");
fscanf(in,"%d %d\n",&num_vertices,&num_edges);
for(int i=1;i<=num_vertices;++i){
parent[i]=i;
rank[i]=0;
}
for(int i=0;i<num_edges;++i){
fscanf(in,"%d %d %d\n",&edges[i].v1,&edges[i].v2,&edges[i].cost);
}
sort(edges,edges+num_edges,comp());
for(int i=0;i<num_edges;++i){
int s1=findset(edges[i].v1),s2=findset(edges[i].v2);
if(s1!=s2){
merge(s1,s2);
total_cost+=edges[i].cost;
}
}
fprintf(out,"%d\n",total_cost);
}
我的问题是:我需要这两行代码吗?如果是,它们的重要性是什么?
int px=findset(x),py=findset(y);
在合并中而不是 int px=parent[x],py=parent[y];
parent[x]=findset(parent[x]);
在findset 而不是 return
findset(父[x]);
最佳答案
1) findset(x)
返回 x 所在的集合的规范代表(其祖先树的根)。你需要这个来比较两个元素是否在同一个集合中(它们有相同的代表),parent[x]
只是返回树中 x 的父元素,这可能不是成为根。
1a) 您忘记在 merge
中测试 px 和 py 是否相同。
2) 这是一项优化,以便将来对 findset
的调用运行得更快。如果 parent[x]
用于指向其父对象,而父对象指向其集合树的根,则在此调用之后 parent[x]
将直接指向根。
关于c++ - Kruskal 算法和不相交集数据结构 : Do I need the following two lines of code?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5442275/
我正在尝试用 Python (scipy) 替换 Python 脚本中的一些 rpy2 代码。在这种情况下,我需要用 (Python: kruskal.test() ) 替换 Kruskal-Wall
一 构建后的图 二 代码 package graph.kruskal; import java.util.ArrayList; import java.util.Collections; impor
一 点睛 构造最小生成树还有一种算法,即 Kruskal 算法:设图 G=(V,E)是无向连通带权图,V={1,2,...n};设最小生成树 T=(V,TE),该树的初始状态只有 n 个节点而无边的非
来这里之前我已经努力尝试并做了我的研究。下面的代码崩溃了,我怀疑滥用了 cout。 (这不应该是最好的实现,但暂时不是 pb) 有经验的人能看出问题出在哪里吗? 提前致谢 #include #inc
据说Kruskal构造MST的算法是贪心的,但是该算法选择的是全局最小值而不是局部最小值,这与Prim的算法不同。谁能解释一下 Kruskal 算法为何被视为贪婪算法? 最佳答案 我们在克鲁斯卡尔做什
假设G是一个有n个顶点的无向图,每对顶点之间有加权边。你能按以下结构构造一棵树吗: v_1-v_2-v_3-...-v_n 使得树中的每个节点对应于 G 中的一个顶点,并且每个节点除叶子外只有一个子节
我正在学习 Kruskal 的算法,我遇到了几个不同的实现,并且想知道它们之间的权衡是什么。两种实现方式如下: 实现一- 将图中的所有边放入优先队列 PQ- 从 PQ 中移除最小边 e - 如果 e
我对什么是 Kruskal 算法有了基本的了解,这就是我的发现: 该算法基本上是通过合并多棵树来构造一棵最小生成树,它首先根据边的权重对边进行排序。该算法从一个空子图开始,扫描边列表,如果不创建循环,
我正在研究来自 this geeksforgeeks article 的 Kruskal 的 MST .给出的步骤是: 按权重的非降序对所有边进行排序。 选择最小的边。检查它是否与目前形成的生成树形成
我有一个任务,我需要从单元格网格创建一个迷宫。 我使用 Randomized Kruskal's algorithm 成功地做到了如 Wiki 页面所述并使用 Disjoint-set data st
我找到了一个创建 makes 和 finds 方法的教程 public void makeSet(long data) { Node node = new Node();
我发现最小生成树 (MST) 的某些边使用联合查找方法重叠,详见 here ,经过修改 - 使用 float 而不是 integer 权重,使用 integer 值而不是 string ID。下图中的
我打算用 C++ 实现 Kriskal 的算法,但是... Unhandled exception at 0x0127160d in DAA.exe: 0xC0000005: Access viola
我正在计算这样的 kruskal 算法的时间复杂度(请参阅附件中的算法) T(n) = O(1) + O(V) + O(E log E) + O(V log V) = O(E log E)
我正在尝试尽可能高效地实现 Kruskal。 对于运行时效率,使用堆或排序算法对边进行排序有区别吗? 还有哪些其他技术可以使 Kruskal 算法更有效地工作? 最佳答案 这取决于您要解决的确切问题。
我如何使用 Kruskal 算法计算 im R(3.0.0 - Linux x32) 最小生成树? 我使用 igraph (0.6.5) 库创建一个加权全图,如下所示: set.seed(123456
当图有多个连通分量时,我不确定如何实现 Kruskal 算法 根据我对 Kruskal 算法的理解,它反复将最小边添加到集合中。然后,当检查完所有边时,它返回最多的边集。 但是,如果我的图表断开连接怎
虽然我在工作an assignment在 Stanford CS106B C++ 类(class)上,但我大量坚持实现 Kruskal 算法以找到最小生成树。 更具体地说,我无法弄清楚确定是否向树添加
由于 Kruskal 算法是贪心算法,这意味着我们有时可能得不到真正的最小路径。 但是谁能举出一个例子来说明这个算法没有得到最小值? 我不是在寻找复杂性,只是需要一个确实没有得到最佳解决方案的案例。
Here is a Graph我需要使用 Prim 的 和 Kruskal 的 算法找到 G 的最小生成树。 我使用 Prim 算法找到了最小生成树。 Here is my attempt . 我在使
我是一名优秀的程序员,十分优秀!