I tried to find minimum spanning tree with given graph (as adjacency list), priority queue and union-find method (with kruskal).
But there are two differences with my desired output :
First, The output contains Edges which didn't sort.
Since Kruskal sort Edges and pick one of them, the output must be sorted, but my output didn't.
Here is my output :
1 - 2 : 35
3 - 2 : 126
8 - 6 : 120
5 - 1 : 247
2 - 6 : 150
.
.
.
.
Second problem is generated Minimum Spanning Tree have redundancy nodes, Here is my output :
1 : 2[35] 5[247] 5[247] 2[35]
2 : 1[35] 3[126] 6[150] 6[150] 3[126] 1[35]
.
.
.
There are two '2' and two '5' in 'Node 1' and similar problem for 'Node 2'.
In fact, the 'Node 1' of Minimum spanning tree should not have '5' but it does.
I think there are problems in priority queue but I can't find it.
Here is my full-code about finding minimum spanning tree with adjacency list as below :
#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;
}