Kruskal

#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;

struct SEdge
{
int m_iRow;     // Số dòng của một đỉnh
int m_iCol;     // Số cột của một đỉnh
};

// Đọc ma trận có trọng số
void importFile(char *filename_input_name, int Graph[][100],int &vertexNumber)
{
ifstream txt (filename_input_name);

txt >> vertexNumber;   // Đọc số lượng đỉnh

if (txt.is_open())
{
for(int i = 0; i < vertexNumber; i++)
{
for(int j = 0; j < vertexNumber; j++)
{
txt >> Graph[i][j];
}
}
txt.close();
}
else
cout << "Unable to open file"; 
}

// Xuất output
void outputFile(char* file_output_name,int A[][100], int vertexNumber, SEdge *T)
{
ofstream txt (file_output_name);
if (txt.is_open())
{
// Dòng 1 : In ra trọng số của các cạnh
for (int i = 0; i < vertexNumber - 1; i++)
{
txt << A[T[i].m_iRow][T[i].m_iCol];
if (i != vertexNumber)
txt << " ";
}
// Dòng 2 : In các cạnh trong cây khung tìm được
txt << "\n{";
for (int j = 0; j < vertexNumber - 1; j++)
{
txt << "(" << (T[j].m_iRow + 1) << "," << (T[j].m_iCol + 1) << ")";
if (j < vertexNumber - 2)
txt << " ; ";
}
txt << "}";

txt.close();
}
else
cout << "Unable to open file";
}

Edge T[100]; // Mảng chứa các cạnh trong cây khung
int nT = 0; // Số phần tử trong tập T
Edge ListEdge[100]; // Mảng chứa các cạnh của đồ thị G
int edgeNumber = 0; // Số lượng cạnh của G
int Label[100]; // Mảng đánh nhãn đỉnh dùng để xét việc tạo chu trình khi thêm cạnh hay không

// Sắp xếp danh sách cạnh theo thứ tự trọng số tăng dần
void SortEdge()
{
// Dùng thuật toán sắp xếp để sắp xếp danh sách cạnh theo thứ tự trọng số tăng dần
}

// Khởi tạo danh sách cạnh của đồ thị từ ma trận trọng số
void CreateListEdge()
{
// Duyệt qua ma trận trọng số của đồ thị
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
// Nếu có cạnh thì thêm vào danh sách cạnh
if(Graph[i][j] != 0)
{
SEdge edge;
edge.iRow = i;
canh.iCol = j;
DSCANH[nCanh] = canh;
nCanh++;
}
}
}
}

// Hàm kiểm tra việc thêm cạnh e vào T có tạo thành chu trình hay không
bool CoChuTrinh(int e)
{
// Nếu nhãn của hai đỉnh trong e là giống nhau => tạo thành chu trình, trả về true
if(Nhan[DSCANH[e].v] == Nhan[DSCANH[e].w])
return true;

// Tìm xem nhãn nào lớn hơn và nhỏ hơn
int NhanNho, NhanLon;
NhanNho = min(Nhan[DSCANH[e].v], Nhan[DSCANH[e].w]);
NhanNho = max(Nhan[DSCANH[e].v], Nhan[DSCANH[e].w]);

// Duyệt qua nhãn của các đỉnh
for(int i = 0; i < g.nSoDinh; ++i)
{
// Nếu nhãn của đỉnh nào đang bằng nhãn lớn hơn thì gán thành nhãn nhỏ hơn
if(Nhan[i] == NhanLon)
Nhan[i] = NhanNho;
}
return false;
}


// Tìm cây khung nhỏ nhất sử dụng Kruskal
void Kruskal()
{
/** === BƯỚC 1 ===
== LẤY DANH SÁCH CẠNH CỦA ĐỒ THỊ TỪ MA TRẬN KỀ VÀ SẮP XẾP THEO TRỌNG SỐ == **/
KhoiTaoDanhSachCanh();
SapXepCanh();

/** Gán nhãn cho các đỉnh của G (phục vụ cho mục đích kiểm tra việc tạo thành chu trình) **/
for(int i=0; i < g.nSodinh; i++)
{
Nhan[i] = i;
}

/** === BƯỚC 3 === **/
// Lặp cho đến khi số phần tử của tập T là n-1
while (nT < g.nSodinh-1)
{
/** === BƯỚC 2 === 
Lần lượt lấy từng cạnh e trong DSCANH đã sắp xếp, nếu đưa e vào T không tạo thành chu trình thì thêm e vào T **/
for(int e = 0; (e < nCanh) && (nT == g.nSodinh-1); i++)
{
bool khongthem = CoChuTrinh(e); // Kiểm tra xem việc thêm cạnh e vào có tạo chu trình hay không

// Nếu không tạo thành chu trình thì thêm cạnh e vào
if(!khongthem)
{
T[nT] = DSCANH[e];
nT++;
if (nT == g.nSodinh-1)
break;
}
}
if (nT == g.nSodinh - 1)
{
cout << "Lien thong";
}
else
{
cout << "Khong lien thong";
}
}
}

void main()
{
int Graph[100][100];
int vertexNumber;

importFile("input.txt", Graph, vertexNumber);

SEdge *eaCategory = new SEdge[vertexNumber - 1];

Kruskal(Graph, vertexNumber, eaCategory);
outputFile("output.txt", Graph, vertexNumber, eaCategory);
}