Kruskal algorithm, cycles and unvisited vertices

Question

Algorithm does not pass through vertex 1(Z) and 4(B). Cycles are for vertices 12-13-14(S-T-K) and 13-15-16(T-L-R), how to fix it?

Below is the command, my code, graph, my output and the input file.

The input file contains the data of one connected graph. Its first line contains an integer Nv that specifies the number of edges of the graph. Then there are Nv lines containing descriptions of the consecutive vertices. The description of each node contains a positive integer corresponding to its identifier and a text string corresponding to its name. It can be assumed that both the number of vertices and the identifiers will not exceed 32,767, the length of the name will not be more than 8 characters, and it will only contain letters or numbers. The next line is the number Ne that specifies the number of edges in the graph. Then there are Ne lines containing the description of the subsequent edges. The description of each edge contains three positive integers, the first two correspond to the identifiers of the vertices connected by the given edge, the third is the weight of this edge.

The output should be exactly as many lines as the edges contain the Minimal Spanning Tree, each line should contain information about one edge. The information for each edge should contain the names of the vertices and the edge weight separated by spaces.

#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

There are at least two issues with your code:

1. When you call your quicksort implementation you should start it with edgenumber - 1 as right border index, otherwise you access uninitialised data.
2. Your loop detection is not correct because you don't care for the case where there are already three or more edges in MST with the same vertex. Here the path can split but you just follow one of them. Thus you add also cyclic edges to MST and the limit of MST.size() >= vertexnumber - 1 is reached before you could link all vertices to the tree.

I hope this helps. There are plenty of implementations in the net (e.g. see external links in the wikipedia article) where you can study how others have solved the task of loop detection. But if my assumption is right that you are doing this as homework, of course, it is better to try yourself.