Kruskal算法，周期和未访问的顶点

Question

算法不会通过顶点1（z）和4（b）。循环用于顶点12-13-14（STK）和13-15-16（TLR），如何修复它？

以下是命令，我的代码，图形，我的输出和输入文件。

输入文件包含一个连接图的数据。它的第一行包含一个整数NV，指定图形的边缘数。然后是包含连续顶点的描述的NV线。每个节点的描述包含一个正整数，与其名称相对应的文本字符串对应。可以假设，顶点和标识符的数量不会超过32,767，名称的长度不会超过8个字符，并且仅包含字母或数字。下一行是指定图中边缘数的数字NE。然后是包含后续边缘的描述的NE线。每个边缘的描述包含三个正整数，前两个对应于给定边缘连接的顶点的标识符，第三个是该边缘的重量。

输出应与边缘包含最小生成树的线一样多，每行应包含有关一个边缘的信息。每个边缘的信息应包含顶点的名称，而边缘重量则由空格分开。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Vertex
{
    int id;
    char name[8];
};

struct Edges
{
    int source;
    int destination;
    int weight;
};

void quickSort(Edges* tab, int left, int right)
{
    if (right <= left)
    {
        return;
    }

    int i = left - 1, j = right + 1, pivot = tab[(left + right) / 2].weight;

    while (1)
    {
        while (pivot > tab[++i].weight);
        while (pivot < tab[--j].weight);


        if (i <= j)
        {
            swap(tab[i].source, tab[j].source);
            swap(tab[i].destination, tab[j].destination);
            swap(tab[i].weight, tab[j].weight);
        }
        else
        {
            break;
        }
    }

    if (j > left)
    {
        quickSort(tab, left, j);
    }
    if (i < right)
    {
        quickSort(tab, i, right);
    }
}

int main()
{
    int vertexnumber;
    int edgenumber;

    Edges* edgeList{};
    vector<Edges> MST;
    vector<Vertex> vertexList;

    cin >> vertexnumber;

    for (int i = 0; i < vertexnumber; i++)
    {
        vertexList.push_back(Vertex());
        cin >> vertexList[i].id;
        cin >> vertexList[i].name;
    }

    cin >> edgenumber;
    edgeList = new Edges[edgenumber];

    for (int i = 0; i < edgenumber; i++)
    {
        cin >> edgeList[i].source;
        cin >> edgeList[i].destination;
        cin >> edgeList[i].weight;
    }

    quickSort(edgeList, 0, edgenumber);

    int iterator = 0;

    for (int i = 0; i < edgenumber; i++)
    {
        bool isLoop = false;
        int helper = edgeList[i].source;

        for (int j = 0; j < MST.size(); j++)
        {
            for (int k = 0; k < MST.size(); k++)
            {
                if (MST[k].source == helper)
                {
                    helper = MST[k].destination;
                    break;
                }
                if (MST[k].destination == helper)
                {
                    helper = MST[k].source;
                    break;
                }
            }
            if (edgeList[i].destination == helper)
            {
                isLoop = true;
                break;
            }
        }
        if (!isLoop)
        {
            MST.push_back(Edges());
            MST[iterator].destination = edgeList[i].destination;
            MST[iterator].source = edgeList[i].source;
            MST[iterator].weight = edgeList[i].weight;

            iterator++;

            if (MST.size() >= vertexnumber - 1)
            {
                break;
            }
        }
    }

    for (int i = 0; i < MST.size(); i++)
    {
        for (int j = 0; j < vertexList.size(); j++)
        {
            if (vertexList[j].id == MST[i].source)
            {
                cout << vertexList[j].name << " ";
                break;
            }
        }
        for (int j = 0; j < vertexList.size(); j++)
        {
            if (vertexList[j].id == MST[i].destination)
            {
                cout << vertexList[j].name << " ";
                break;
            }
        }

        cout << MST[i].weight << endl;
    }

}

S K 60
D O 82
O S 96
F P 108
T K 109
P C 110
W E 115
S T 124
E T 130
G N 135
T R 136
L R 138
F D 139
T L 142
G C 145

16      
1   Z   
2   G   
3   N   
4   B   
5   F   
6   P   
7   C   
8   W   
9   E   
10  D   
11  O   
12  S   
13  T   
14  K   
15  L   
16  R   
34      
1   2   288
1   5   175
1   6   192
2   3   135
2   6   246
2   7   145
3   4   188
3   7   177
3   8   174
4   8   179
4   15  213
5   6   108
5   10  139
6   7   110
6   9   187
6   10  147
6   11  203
7   8   218
7   9   172
8   9   115
8   13  146
8   15  153
9   11  168
9   12  174
9   13  130
10  11  82
11  12  96
12  13  124
12  14  60
13  14  109
13  15  142
13  16  136
14  16  148
15  16  138

Answer 1

您的代码至少有两个问题：

1. 当您调用您的QuickSort实现时，您应该以Edgenumber -1作为正确的边框索引开始，否则您可以访问非初始化的数据。
2. 您的循环检测是不正确的，因为您不在乎mst具有相同顶点的三个或更多边的情况。在这里，路径可以分开，但您只需跟随其中一个即可。因此，您还将循环边缘添加到mst以及mst.size（）＆gt; = dertexnumber -1的限制，然后才能将所有顶点链接到树。

我希望这会有所帮助。网络中有很多实现（例如，请参见