C++

Question

내가 here

그들은 정수의 무게를 사용하고 크루스 칼의 알고리즘을 사용하여 최소 스패닝 트리에 대한 템플릿을 발견 (대신 정수)를 두 번 무게 크루스 칼의 이론을 구현하는 방법, 그것은 가능하다 대신 이중 무게 사용?

내가 여기 저기에서 변경을했고, 저에게 오류를주고 있습니다.

struct Edge 
{ 
    int src, dest; 
    double weight; 
}; 

및

double myComp(const void* a, const void* b) 
    { 
     struct Edge* a1 = (struct Edge*)a; 
     struct Edge* b1 = (struct Edge*)b; 
     return a1->weight > b1->weight; 
    } 

나는 이유는 모르겠지만, 이러한 변화는 void KruskalMST(struct Graph* graph)의 퀵 선

의 다음 몇 작동하지 않을 만든 : 여기

내가 변경거야

다음은 원래 코드입니다.

// Kruskal's algortihm to find Minimum Spanning Tree of a given connected, 
// undirected and weighted graph 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

// a structure to represent a weighted edge in graph 
struct Edge 
{ 
    int src, dest, weight; 
}; 

// a structure to represent a connected, undirected and weighted graph 
struct Graph 
{ 
    // V-> Number of vertices, E-> Number of edges 
    int V, E; 

    // graph is represented as an array of edges. Since the graph is 
    // undirected, the edge from src to dest is also edge from dest 
    // to src. Both are counted as 1 edge here. 
    struct Edge* edge; 
}; 

// Creates a graph with V vertices and E edges 
struct Graph* createGraph(int V, int E) 
{ 
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); 
    graph->V = V; 
    graph->E = E; 

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge)); 

    return graph; 
} 

// A structure to represent a subset for union-find 
struct subset 
{ 
    int parent; 
    int rank; 
}; 

// A utility function to find set of an element i 
// (uses path compression technique) 
int find(struct subset subsets[], int i) 
{ 
    // find root and make root as parent of i (path compression) 
    if (subsets[i].parent != i) 
     subsets[i].parent = find(subsets, subsets[i].parent); 

    return subsets[i].parent; 
} 

// A function that does union of two sets of x and y 
// (uses union by rank) 
void Union(struct subset subsets[], int x, int y) 
{ 
    int xroot = find(subsets, x); 
    int yroot = find(subsets, y); 

    // Attach smaller rank tree under root of high rank tree 
    // (Union by Rank) 
    if (subsets[xroot].rank < subsets[yroot].rank) 
     subsets[xroot].parent = yroot; 
    else if (subsets[xroot].rank > subsets[yroot].rank) 
     subsets[yroot].parent = xroot; 

    // If ranks are same, then make one as root and increment 
    // its rank by one 
    else 
    { 
     subsets[yroot].parent = xroot; 
     subsets[xroot].rank++; 
    } 
} 

// Compare two edges according to their weights. 
// Used in qsort() for sorting an array of edges 
int myComp(const void* a, const void* b) 
{ 
    struct Edge* a1 = (struct Edge*)a; 
    struct Edge* b1 = (struct Edge*)b; 
    return a1->weight > b1->weight; 
} 

// The main function to construct MST using Kruskal's algorithm 
void KruskalMST(struct Graph* graph) 
{ 
    int V = graph->V; 
    struct Edge result[V]; // Tnis will store the resultant MST 
    int e = 0; // An index variable, used for result[] 
    int i = 0; // An index variable, used for sorted edges 

    // Step 1: Sort all the edges in non-decreasing order of their weight 
    // If we are not allowed to change the given graph, we can create a copy of 
    // array of edges 
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp); 

    // Allocate memory for creating V ssubsets 
    struct subset *subsets = 
     (struct subset*) malloc(V * sizeof(struct subset)); 

    // Create V subsets with single elements 
    for (int v = 0; v < V; ++v) 
    { 
     subsets[v].parent = v; 
     subsets[v].rank = 0; 
    } 

    // Number of edges to be taken is equal to V-1 
    while (e < V - 1) 
    { 
     // Step 2: Pick the smallest edge. And increment the index 
     // for next iteration 
     struct Edge next_edge = graph->edge[i++]; 

     int x = find(subsets, next_edge.src); 
     int y = find(subsets, next_edge.dest); 

     // If including this edge does't cause cycle, include it 
     // in result and increment the index of result for next edge 
     if (x != y) 
     { 
      result[e++] = next_edge; 
      Union(subsets, x, y); 
     } 
     // Else discard the next_edge 
    } 

    // print the contents of result[] to display the built MST 
    printf("Following are the edges in the constructed MST\n"); 
    for (i = 0; i < e; ++i) 
     printf("%d -- %d == %d\n", result[i].src, result[i].dest, 
                result[i].weight); 
    return; 
} 

// Driver program to test above functions 
int main() 
{ 
    /* Let us create following weighted graph 
      10 
     0--------1 
     | \  | 
     6| 5\ |15 
     |  \ | 
     2--------3 
      4  */ 
    int V = 4; // Number of vertices in graph 
    int E = 5; // Number of edges in graph 
    struct Graph* graph = createGraph(V, E); 


    // add edge 0-1 
    graph->edge[0].src = 0; 
    graph->edge[0].dest = 1; 
    graph->edge[0].weight = 10; 

    // add edge 0-2 
    graph->edge[1].src = 0; 
    graph->edge[1].dest = 2; 
    graph->edge[1].weight = 6; 

    // add edge 0-3 
    graph->edge[2].src = 0; 
    graph->edge[2].dest = 3; 
    graph->edge[2].weight = 5; 

    // add edge 1-3 
    graph->edge[3].src = 1; 
    graph->edge[3].dest = 3; 
    graph->edge[3].weight = 15; 

    // add edge 2-3 
    graph->edge[4].src = 2; 
    graph->edge[4].dest = 3; 
    graph->edge[4].weight = 4; 

    KruskalMST(graph); 

    return 0; 
} 

Answer 1

문제는 double 대 int과 전혀 관련이 없으며 행운의 영향으로 int과 함께 작동했을 수도 있지만 똑같이 잘못되었습니다.

int myComp(const void* a, const void* b) 
{ 
    struct Edge* a1 = (struct Edge*)a; 
    struct Edge* b1 = (struct Edge*)b; 
    return a1->weight > b1->weight; <----THIS 
} 

이보다 큰 b1.weight 및 0 그렇지 않으면이다 1a1.weight 경우 반환합니다.

당신이 반환해야하는 것입니다 :

• 0 : 두 값이 모두

• <0 동일한 경우 : a1.weight 미만 b1.weight

• >0 경우 : a1.weight 이상 b1.weight 경우

분명히 qsort 예상대로 함수가 작동하지 않습니다. 이 값과 일치하도록 코드를 변경하십시오. 당신은 저를 제공 한 링크를 확인하고 그 예를 볼 수 있습니다.