使用 Kruskal 的最小生成树找到，但存在重叠顶点

问：

我试图找到具有给定图形（作为邻接列表）、优先级队列和 union-find 方法（使用 kruskal）的最小生成树。

但是我想要的输出有两个区别：

首先，输出包含未排序的 Edge。

由于 Kruskal 对边进行排序并选取其中之一，因此必须对输出进行排序，但我的输出没有。

这是我的输出：

1 - 2 : 35
3 - 2 : 126
8 - 6 : 120
5 - 1 : 247
2 - 6 : 150
.
.
.
.

第二个问题是生成最小生成树有冗余节点，这是我的输出：

1 : 2[35] 5[247] 5[247] 2[35]
2 : 1[35] 3[126] 6[150] 6[150] 3[126] 1[35]
.
.
.

“节点 1”中有两个“2”和两个“5”，节点 2 也有类似的问题。

事实上，最小生成树的“节点 1”不应该有“5”，但它确实有。

我认为优先级队列有问题，但我找不到它。

这是我关于查找具有邻接列表的最小生成树的完整代码，如下所示：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct DisjointSet
{
    struct DisjointSet* Parent;
    void* data;
} DisjointSet;

typedef struct PQNode
{
    int priority;
    void* data;
}PQNode;

typedef struct PQ
{
    PQNode* Node;
    int capacity;
    int using;
}PQ;

typedef struct Vertex
{
    int data;
    int isVisited;
    int index;

    struct Vertex* Next;
    struct Edge* AdjList;
} Vertex;

typedef struct Edge
{
    int Weight;
    struct Edge* Next;
    Vertex* From;
    Vertex* Target;
} Edge;

typedef struct Graph
{
    Vertex* Vt;
    int cnt;
} Graph;

// ----------------- Priority Q ---------------------

PQ* NewQ(int size)
{
    PQ* q = (PQ*)malloc(sizeof(PQ));
    q->capacity = size;
    q->using = 0;
    q->Node = (PQNode*)malloc(sizeof(PQNode) * q->capacity);

    return q;
}

void Swap(PQ* q, int idx1, int idx2)
{
    int CopySize = sizeof(PQNode);
    PQNode* TempNode = (PQNode*)malloc(CopySize);

    memcpy(TempNode, &q->Node[idx1], CopySize);
    memcpy(&q->Node[idx1], &q->Node[idx2], CopySize);
    memcpy(&q->Node[idx2], TempNode, CopySize);

    free(TempNode);
}

int isEmpty(PQ* q)
{
    return (q->using == 0);
}

int GetParent(int i)
{
    return (int)((i - 1) / 2);
}

int GetChild(int i)
{
    return (2 * i) - 1;
}

void DestroyQ(PQ* q)
{
    free(q->Node);
    free(q);
}

void Enqueue(PQ* q, PQNode Node)
{
    int Current = q->using;
    int Parent = GetParent(Current);

    if (q->using == q->capacity)
    {
        if (q->capacity == 0)
        {
            q->capacity = 1;
        }

        q->capacity = 2;
        q->Node = (PQNode*)realloc(q->Node, sizeof(PQNode) * q->capacity);
    }

    q->Node[Current] = Node;

    while (Current > 0 && q->Node[Current].priority < q->Node[Parent].priority)
    {
        Swap(q, Current, Parent);

        Current = Parent;
        Parent = GetParent(Current);
    }
    q->using++;
}

void Dequeue(PQ* q, PQNode* RootNode)
{
    int Left = 0;
    int Right = 0;
    int Parent = 0;

    memcpy(RootNode, &q->Node[0], sizeof(PQNode));
    memset(&q->Node[0], 0, sizeof(PQNode));

    q->using--;
    Swap(q, 0, q->using);

    Left = GetChild(0);
    Right = Left + 1;

    while (1)
    {
        int Select = 0;

        if (Left >= q->using)
        {
            break;
        }
        if (Right >= q->using)
        {
            Select = Left;
        }
        else
        {
            if (q->Node[Left].priority > q->Node[Right].priority)
            {
                Select = Right;
            }
            else
            {
                Select = Left;
            }
        }

        if (q->Node[Select].priority < q->Node[Parent].priority)
        {
            Swap(q, Parent, Select);
            Parent = Select;
        }
        else
        {
            break;
        }

        Left = GetChild(Parent);
        Right = Left + 1;
    }

}

// ----------------- Priority Q ---------------------

// -------------- Union and find --------------------

DisjointSet* Find(DisjointSet* Set)
{
    while (Set->Parent != NULL)
    {
        Set = Set->Parent;
    }
    return Set;
}

void Union(DisjointSet* S1, DisjointSet* S2)
{
    S2 = Find(S2);
    S2->Parent = NULL;
}

DisjointSet* NewSet(void* data)
{
    DisjointSet* Set = (DisjointSet*)malloc(sizeof(DisjointSet));
    Set->Parent = NULL;
    Set->data = data;

    return Set;
}

void DestroySet(DisjointSet* Set)
{
    free(Set);
}

// -------------- Union and find --------------------

// ------------------- Graph ------------------------

Graph* NewGraph()
{
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->Vt = NULL;
    g->cnt = 0;

    return g;
}

void DestroyEdge(Edge* e)
{
    free(e);
}

void DestroyVertex(Vertex* v)
{
    while (v->AdjList != NULL)
    {
        Edge* e = v->AdjList->Next;
        DestroyEdge(v->AdjList);
        v->AdjList = e;
    }

    free(v);
}

void DestroyGraph(Graph* g)
{
    while (g->Vt != NULL)
    {
        Vertex* v = g->Vt->Next;
        DestroyVertex(g->Vt);
        g->Vt = v;
    }

    free(g);
}

Vertex* NewVertex(int data)
{
    Vertex* v = (Vertex*)malloc(sizeof(Vertex));

    v->data = data;
    v->Next = NULL;
    v->AdjList = NULL;
    v->isVisited = 0;
    v->index = -1;

    return v;
}

Edge* NewEdge(Vertex* From, Vertex* Target, int weight)
{
    Edge* e = (Edge*)malloc(sizeof(Edge));
    e->From = From;
    e->Target = Target;
    e->Next = NULL;
    e->Weight = weight;

    return e;
}

void AddVertex(Graph* g, Vertex* v)
{
    Vertex* vList = g->Vt;

    if (vList == NULL)
    {
        g->Vt = v;
    }
    else
    {
        while (vList->Next != NULL)
        {
            vList = vList->Next;
        }
        vList->Next = v;
    }
    v->index = g->cnt++;
}

void AddEdge(Vertex* v, Edge* e)
{
    if (v->AdjList == NULL)
    {
        v->AdjList = e;
    }
    else
    {
        Edge* AdjList = v->AdjList;
        while (AdjList->Next != NULL)
        {
            AdjList = AdjList->Next;
        }
        AdjList->Next = e;
    }
}

void printG(Graph* g)
{
    Vertex* v = NULL;
    Edge* e = NULL;

    if ((v = g->Vt) == NULL)
    {
        return;
    }
    while (v != NULL)
    {
        printf("%d : ", v->data);
        if ((e = v->AdjList) == NULL)
        {
            v = v->Next;
            printf("\n");
            continue;
        }

        while (e != NULL)
        {
            printf("%d[%d] ", e->Target->data, e->Weight);
            e = e->Next;
        }

        printf("\n");

        v = v->Next;
    }
    printf("\n");
}

void Kruskal(Graph* g, Graph* MSTree)
{
    Vertex* CurrentV = NULL;
    Vertex** MSTreeV = (Vertex**)malloc(sizeof(Vertex*) * (g->cnt));

    DisjointSet** VertexSet = (DisjointSet**)malloc(sizeof(DisjointSet*) * g->cnt);

    PQ* q = NewQ(200);

    int i = 0;
    CurrentV = g->Vt;
    while (CurrentV != NULL)
    {
        Edge* CurrentE;
        VertexSet[i] = NewSet(CurrentV);
        MSTreeV[i] = NewVertex(CurrentV->data);
        AddVertex(MSTree, MSTreeV[i]);

        CurrentE = CurrentV->AdjList;
        while (CurrentE != NULL)
        {
            PQNode Node = { CurrentE->Weight, CurrentE };
            Enqueue(q, Node);
            CurrentE = CurrentE->Next;
        }
        CurrentV = CurrentV->Next;
        i++;
    }


    while (!isEmpty(q))
    {
        Edge* CurrentEdge;
        int from;
        int to;
        PQNode Pop;

        Dequeue(q, &Pop);
        CurrentEdge = (Edge*)Pop.data;

        printf("%d - %d : %d\n", CurrentEdge->From->data, CurrentEdge->Target->data, CurrentEdge->Weight);

        from = CurrentEdge->From->index;
        to = CurrentEdge->Target->index;

        if (Find(VertexSet[from]) != Find(VertexSet[to]))
        {
            AddEdge(MSTreeV[from], NewEdge(MSTreeV[from], MSTreeV[to], CurrentEdge->Weight));
            AddEdge(MSTreeV[to], NewEdge(MSTreeV[to], MSTreeV[from], CurrentEdge->Weight));
            Union(VertexSet[from], VertexSet[to]);
        }
    }

    for (i = 0; i < g->cnt; i++)
    {
        DestroySet(VertexSet[i]);
    }
    free(VertexSet);
    free(MSTreeV);
}

// ------------------- Graph ------------------------

int main()
{
    Graph* g = NewGraph();
    Graph* k = NewGraph();

    Vertex* v1 = NewVertex(1);
    Vertex* v2 = NewVertex(2);
    Vertex* v3 = NewVertex(3);
    Vertex* v4 = NewVertex(4);
    Vertex* v5 = NewVertex(5);
    Vertex* v6 = NewVertex(6);
    Vertex* v7 = NewVertex(7);
    Vertex* v8 = NewVertex(8);
    Vertex* v9 = NewVertex(9);
    

    AddVertex(g, v1); // a
    AddVertex(g, v2); // b
    AddVertex(g, v3); // c
    AddVertex(g, v4); // d
    AddVertex(g, v5); // e
    AddVertex(g, v6); // f
    AddVertex(g, v7); // g
    AddVertex(g, v8); // h
    AddVertex(g, v9); // i
    

    AddEdge(v1, NewEdge(v1, v2, 35));
    AddEdge(v1, NewEdge(v1, v5, 247));

    AddEdge(v2, NewEdge(v2, v1, 35));
    AddEdge(v2, NewEdge(v2, v3, 126));
    AddEdge(v2, NewEdge(v2, v6, 150));

    AddEdge(v3, NewEdge(v3, v2, 126));
    AddEdge(v3, NewEdge(v3, v4, 117));
    AddEdge(v3, NewEdge(v3, v6, 162));
    AddEdge(v3, NewEdge(v3, v7, 220));

    AddEdge(v4, NewEdge(v4, v3, 117));

    AddEdge(v5, NewEdge(v5, v1, 247));
    AddEdge(v5, NewEdge(v5, v6, 82));
    AddEdge(v5, NewEdge(v5, v8, 98));

    AddEdge(v6, NewEdge(v6, v2, 150));
    AddEdge(v6, NewEdge(v6, v3, 162));
    AddEdge(v6, NewEdge(v6, v5, 82));
    AddEdge(v6, NewEdge(v6, v7, 154));
    AddEdge(v6, NewEdge(v6, v8, 120));

    AddEdge(v7, NewEdge(v7, v3, 220));
    AddEdge(v7, NewEdge(v7, v6, 154));
    AddEdge(v7, NewEdge(v7, v9, 106));

    AddEdge(v8, NewEdge(v8, v5, 98));
    AddEdge(v8, NewEdge(v8, v6, 120));

    AddEdge(v9, NewEdge(v9, v7, 106));


    printG(g);
    printf("Kruskal");
    Kruskal(g, k);
    printG(k);

    DestroyGraph(g);

    return 0;
}