尝试使用书中的最小生成树示例，但它不适用于大数据

Question

注意：这不是我的代码

我正在尝试将数据结构与C++教科书的最小生成树算法一起使用，但如您所见，我制作了一个边缘 [] 边缘数组并注释掉了旧的 edges[] 数组，但看起来它不适用于更大的边缘或其他东西。（顺便说一下，我只是使用字符作为整数）

有谁知道为什么？我没有改变太多，我只是改变了边缘数组。它编译得很好，但如果你运行它，你会看到它不适用于我的数据，但它将适用于原始数据。

数组就在主数组的正上方（最后一件事）

另外，如果您不想打开IDE，这是我在在线IDE上的代码：http://goo.gl/35KMcK

这是代码：

#include <iostream>
using namespace std;
class MSTEdge
{
    char src;
    char dest;
    int weight;
public:
    MSTEdge(char s = 0, char d = 0, int w = 0) : src(s), dest(d), weight(w) { }
    char& getSrc() { return src; }
    char& getDest() { return dest; }
    int& getWeight() { return weight; }
    int& get() { return getWeight(); }
};
// undirected and weighted graph
class Graph
{
    int V, E;
    MSTEdge* edge;
    int icount;
public:
    Graph(int v, int e) : V(v), E(e), icount(0)
    {
        edge = new MSTEdge[e];
    }
    int& getVertexAmount() { return V; }
    int& getEdgeAmount() { return E; }
    MSTEdge*& getEdges() { return edge; }
    MSTEdge& operator [](int x) { return edge[x]; }
    void insert(MSTEdge& e)
    {
        edge[icount++] = e;
    }
};
// subset for union-find
class subset
{
    int parent;
    int rank;
public:
    subset(int p = 0, int r = 0) : parent(p), rank(r) {}
    int& getTheParent() { return parent; }
    int& getTheRank() { return rank; }
};
// find set of an element i
int find(subset* subsets, int i)
{
    // find root and make root as parent of i (path compression)
    if (subsets[i].getTheParent() != i)
        subsets[i].getTheParent() = find(subsets, subsets[i].getTheParent());
    return subsets[i].getTheParent();
}
// union of two sets of x and y
void Union(subset* subsets, int x, int y)
{
    int x_root = find(subsets, x);
    int yroot = find(subsets, y);
    // Attach smaller rank tree under root of high rank tree
    // (Union by Rank)
    if (subsets[x_root].getTheRank() < subsets[yroot].getTheRank())
        subsets[x_root].getTheParent() = yroot;
    else if (subsets[x_root].getTheRank() > subsets[yroot].getTheRank())
        subsets[yroot].getTheParent() = x_root;
    // If ranks are same, then make one as root and increment its rank by one
    else
    {
        subsets[yroot].getTheParent() = x_root;
        subsets[x_root].getTheRank()++;
    }
}
template <typename T>
void partition_array(T* arr, int& i, int& j, T pivot)
{
    while (i <= j)
    {
        while (arr[i].get() < pivot.get())
            i++;
        while (arr[j].get() > pivot.get())
            j--;
        if (i <= j)
        {
            T tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };
}
template <typename T>
void quickSort_array(T* arr, int left, int right)
{
    int i = left, j = right;
    T pivot = arr[(left + right) / 2];
    // partition 
    partition_array(arr, i, j, pivot);
    // recursion 
    if (left < j)
        quickSort_array(arr, left, j);
    if (i < right)
        quickSort_array(arr, i, right);
}
// The main function to construct MST
void MST(Graph& graph)
{
    int V = graph.getVertexAmount();
    MSTEdge* result = new MSTEdge[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
    quickSort_array(graph.getEdges(), 0, graph.getEdgeAmount());
    // Allocate memory for creating V ssubsets
    subset* subsets = new subset[V];
    // Create V subsets with single elements
    for (int v = 0; v < V; ++v)
    {
        subsets[v].getTheParent() = v;
        subsets[v].getTheRank() = 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
        MSTEdge next_edge = graph[i++];
        int x = find(subsets, next_edge.getSrc());
        int y = find(subsets, next_edge.getDest());
        // 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
    cout << "Following are the edges in the constructed MSTn";
    for (i = 0; i < e; ++i)
        cout
        << result[i].getSrc()
        << " -- "
        << result[i].getDest()
        << " == "
        << result[i].getWeight()
        << endl;
    return;
}
/* weighted graph
10
0-------- 1
|       |
6|   5  |15
|       |
2 --------3
4
*/

//MSTEdge edges[] =  //THIS WORKS
//{
//  MSTEdge(0,1,10),
//  MSTEdge(0,2,6),
//  MSTEdge(0,3,5),
//  MSTEdge(1,3,15),
//  MSTEdge(2,3,4)
//};
MSTEdge edges[] =    // CAUSES PROBLEMS
{
    MSTEdge('A','B',5),
    MSTEdge('A','C',1),
    MSTEdge('B','C',10),
    MSTEdge('B','E',13),
    MSTEdge('C','D',5),
    MSTEdge('D','E',15),
    MSTEdge('D','F',10),
    MSTEdge('E','F',17)
};

// Driver program to test above functions
int main()
{
    int count = sizeof(edges) / sizeof(MSTEdge);
    int V = count - 1;  // Number of vertices in graph
    Graph graph(V, count);
    for (int e = 0; e < count; e++)
        graph.insert(edges[e]);
    MST(graph);
    return 1;
}
// Following are the edges in the constructed MST
// 2 -- 3 == 4
// 0 -- 3 == 5
// 0 -- 1 == 10

Answer 1

subsets数组使用以下代码初始化：

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

这为您提供了具有从 0 到 V-1 parent值的子集

然后，代码尝试使用此行查找这些子集

int x = find(subsets, next_edge.getSrc());

但是您的边将源和目标设置为"A"、"B"、"C"等。所以它永远无法在subsets中找到任何东西.它可能正在访问数组边界之外的subsets项目并导致未定义的行为。

要修复它，请将edges数组更改为使用 0、1、2 作为节点 ID（可能是最简单的），或者更改初始化代码subsets将父级设置为"A"、"B"、"C"等。 注意：可能还有更多地方假定节点 ID 从 0 开始。