标签: kruskals-algorithm

我正在寻找C++ Kruskal实现来对我自己的基准测试......如果你知道一些好的,请分享!

有人可以向我提供有关如何检查图形的边缘是否形成循环的信息吗？任何信息都会非常有帮助。提前谢谢了。

我正在尝试使用 对结构数组进行排序qsort，但它没有正确对内容进行排序。结构节点由起始顶点、结束顶点以及从顶点“a”到达顶点“b”的成本组成。

我正在编写克鲁斯卡尔算法的代码

#include <stdio.h>
#include <stdlib.h>

int v, e;

typedef struct node {
    int a;
    int b;
    int cost;
} node;

int compare(const void *a, const void *b) {
    const node *x = *(node **)a;
    const node *y = *(node **)b;
    return (x->cost > y->cost) ? 1 : 0;
}

int main() {
    scanf("%d %d", &v, &e);
    int i;
    node *arr[e];
    for (i = 0; i < e; i++) {
        int a, b, cost;
        scanf("%d %d %d", …

我正在阅读wikipeida并发现Kruskal的Pseudocode如下:

KRUSKAL(G):    
    foreach v ? G.V:    
        MAKE_SET(v)    
    G.E = sort(G.E)    
    i = 0    
    while (i != |V|-1):      
        pick the next (u, v) edge from sorted list of edges G.E        
        if (FIND_SET(u) != FIND_SET(v)):          
            UNION(u, v)        
            i = i + 1 

我不确定是什么FIND_SET(),维基百科有以下描述:

如果该边连接两个不同的树,则将其添加到森林中,将两棵树组合成一棵树.

所以我想它会检查是否连接了两棵不同的树,但这究竟意味着什么呢？

可能的重复：
克鲁斯卡尔 vs 普里姆

你什么时候会使用 Kruskal 算法而不是 Prim 算法来找到最小生成树？哪种输入图和节点更适合每种类型？在什么情况下，在空间和时间方面使用其中之一更有效？

他们的特定输入是否使一个比另一个好得多？

我能够运行此代码进行一些输入.但在某些情况下,我得到了错误的生成树.例如:如果我在执行程序时给出如下输入:

输入no.of vertices:5输入no.of edges:8

    Enter the vertices and the weight of edge 1:
    1
    3
    10

 Enter the vertices and the weight of edge 2:
1
4
100
 Enter the vertices and the weight of edge 3:
3
5
64
 Enter the vertices and the weight of edge 4:
1
2
13
 Enter the vertices and the weight of edge 5:
3
2
20
 Enter the vertices and the weight of edge 6:
2
5
5
 Enter the vertices and …

我正在实施Kruskal的算法.

在以下代码中调用graph()后,节点的值会发生变化.我不太清楚为什么 - 如果有人能清楚这一点,我会非常感激.我没有从图中访问节点的值,并且正在访问的数组的节点和边都被分配到堆栈外部!

struct node {
  int parent, rank;
};
typedef struct node node;

struct edge {
  int fromvertex, tovertex;
  float weight;
};
typedef struct edge edge;

node* nodes;
edge* edges;

typedef enum {Unvisited, Visited} vertexstate;

int main (int argc, char const *argv[])
{
  void getcount(int*, int*);
  void graph(int, int);
  void makeset(int);
  int hasspantree(int, int, int);
  void kruskal(int, int);
  int printmcst(int);
  int nodecount, edgecount, i, totalcost=0;
  getcount(&nodecount, &edgecount);
  for (i = 1; i <= nodecount; i++)
    makeset(i);
  printf("%d \t …

在一个用于分析算法的类中,我们为Kruskal算法提供了这个伪代码:

然后他说明了以下不相交的森林:

m个MAKE-SET,UNION和FIND-SET操作的序列,其中n个是MAKE-SET操作,可以在不相交的森林上执行,在最坏情况下的时间O( mα)中通过秩和路径压缩进行并联(n)).

用于计算步骤2和步骤5-8的复杂性

对于连接的G:| E | ≥| V | -1; m = O(V + E),n = O(V);

所以步骤2,5-8:O((V + E)α(V))= O(Eα(V))

α(V)= O(lg V)= O(lg E); 所以我们得到O(E lg E)----- //这里α(V)如何相等？

Kruskal:步骤3,5-8和步骤4:O(E lg E)

观察:| E | <| V | 2 - > lg E = O(lg V)

所以,Kruskal的复杂性:O(E lg V)

我试图理解这个"alpha(n)"/"α(n)"函数背后的逻辑,从我所读到的看来,简单地说,Ackermann函数是指数速度快得令人难以置信的,而且逆是以对数方式非常缓慢地增长.

如果我的解释是正确的,"α(n)"代表什么？这是否意味着MAKE-SET操作最多为O(lg n)？如何/为什么使用逆阿克曼是必要的？我的印象是这个操作执行V次(对于每个顶点).在此之后,α(V)也被简化为O(lg V)= O(lg E),这是否意味着,在最大值时,α(V)可以由O(lg V)表示.

另外,为什么是| E | <| V | ^ 2 - > lg E = O(lg V) …

我在C(www.bubblellicious.es/prim.tar.gz)中实现了Prim的算法,但我只是想知道如何将其转换为Kruskal的算法.

看起来它们非常相似,但我无法想象如何将旧代码修改为新代码.如果你给出一些建议或东西,这将是美味的.我知道这很简单,但我仍然是C编程中的n00b ...

我正在学习最小生成树，我遇到了这个问题并决定尝试一下......

在随机生成的 100 个顶点和 800 个边的有向图网络上实现最小生成树算法

public static int[][] getRandomArray(int n){
    int[][] a = new int[n][n];
    Random r = new Random();

    for(int i = 0; i < a.length; i++){
        for(int j = 0; j < a[i].length; j++){
            a[i][j] = r.nextInt();
        }
    }

    return a;
}


public static void main (String [] args)
{
   int x[];
     //TreeSet is used to sort the edges before passing to the algorithm
    TreeSet<Edge>  edges = new TreeSet<Edge>();

    Random random = new Random();

    edges.add(new Edge("0", "1", …