c++ - C/C++ 对结构体中的结构体数组进行 qsort

Question

我正在研究 Kruskal 算法。使用 qsort 函数的排序部分会产生奇怪的节点行为:它按权重正确排序，但会更改每个节点的父节点。当程序执行 FIND-SET(X) 函数时，这种行为导致堆栈溢出。这是我的代码:

#include <iostream>

/*
*DISJOINT
*SETS
*/
typedef struct NODE {
    int rank;
    int data;
    struct NODE *parent;
} NODE;

//MAKE-SET(x)
void makeSet(NODE *node) {
    node->parent = node;
    node->rank = 0;
}

//FIND-SET(x)
NODE *findSet(NODE *node) {
    if (node != node->parent) {
        node->parent = findSet(node->parent);
    }
    return node->parent;
}

//LINK(x, y)
void link(NODE *nodeX, NODE *nodeY) {
    if (nodeX->rank > nodeY->rank) {
        nodeY->parent = nodeX;
    } else {
        nodeX->parent = nodeY;
        if (nodeX->rank == nodeY->rank) {
            nodeY->rank += 1;
        }
    }
}

//UNION(x, y)
void unionSet(NODE *nodeX, NODE *nodeY) {
    link(findSet(nodeX), findSet(nodeY));
}



/*
*GRAPH
*/
typedef struct EDGE {
    NODE source;
    NODE destination;
    int weight;
} EDGE;

typedef struct GRAPH {
    int V;  //Number of vertices/nodes 
    int E;  //Number of edges 
    EDGE *edge; //Array of edges
} GRAPH;

GRAPH *newGraph(int allocatedNumberOfVertices, int allocatedNumberOfEdges) {
    GRAPH *graph = (GRAPH *)malloc(sizeof(GRAPH));
    graph->E = 0;   // intial state: no edges
    graph->V = allocatedNumberOfVertices;
    graph->edge = (EDGE *)malloc((allocatedNumberOfEdges) * sizeof(EDGE));
    return graph;
}

void addEdge(GRAPH *graph, NODE srcNode, NODE dstNode, int weight) {
    graph->edge[graph->E].source = srcNode;
    graph->edge[graph->E].destination = dstNode;
    graph->edge[graph->E].weight = weight;
    graph->E += 1;
}

int compareEdges(const void *first, const void *second) {
    const EDGE *firstEdge = (const EDGE *)first;
    const EDGE *secondEdge = (const EDGE *)second;

    if (firstEdge->weight == secondEdge->weight) {
        return 0;
    } else if (firstEdge->weight > secondEdge->weight) {
        return 1;
    } else {
        return -1;
    }
}

/*Kruskal's algorithm - returns an array of least weighted edges*/
EDGE *getMinimumSpanningTree(GRAPH *graph) {
    int V = graph->V;
    int E = graph->E;
    int resultE = 0;
    EDGE *result = (EDGE *)malloc(E * (sizeof(EDGE)));

    //create a disjoint-set for every node
    for (int e = 0; e < E; e++) {
        makeSet(&(graph->edge[e].source));
        makeSet(&(graph->edge[e].destination));
    }


    //sort edges of graph into nondecreasing order by weight
    qsort(graph->edge, graph->E, sizeof(struct EDGE), compareEdges);

    //finds a safe edge to add to the growing forest
    for (int e = 0; e < E; e++) {
        if (findSet(&(graph->edge[e].source))->data != findSet(&(graph->edge[e].destination))->data) {
            result[resultE++] = *graph->edge;
            unionSet(&(graph->edge[e].source), &(graph->edge[e].destination));
        }
    }

    return result;
}

void KruskalDemo() {
    GRAPH *graph = newGraph(6, 9);
    NODE node[6];
    for (int i = 0; i < 6; i++) {
        node[i].data = i;
    }

    addEdge(graph, node[0], node[1], 3);
    addEdge(graph, node[1], node[2], 1);
    addEdge(graph, node[2], node[3], 1);
    addEdge(graph, node[3], node[0], 1);
    addEdge(graph, node[3], node[1], 3);
    addEdge(graph, node[3], node[4], 6);
    addEdge(graph, node[4], node[2], 5);
    addEdge(graph, node[4], node[5], 2);
    addEdge(graph, node[5], node[2], 4);


    EDGE *MST = getMinimumSpanningTree(graph);

    //we expect to have 5 vertices
    for (int i = 0; i < 5; i++) {
        printf("weight(%d, %d) = %d\n", MST->source.data, MST->destination.data, MST->weight);
    }
}

int main() {
    KruskalDemo();
    return 0;
}

Answer 1

我解决了:问题是算法，并且结构体edge的字段不是指针:

更改:

 typedef struct EDGE {
    NODE source;
    NODE destination;
    int weight;
} EDGE;

对此:

typedef struct EDGE {
    NODE *source;
    NODE *destination;
    int weight;
} EDGE;

算法为:

for (int e = 0; e < E; e++) {
    if (findSet(graph->edge[e].source)->data != findSet(graph->edge[e].destination)->data) {
        result[resultE++] = graph->edge[e];
        unionSet(graph->edge[e].source,graph->edge[e].destination);
    }
}