PRIM(minimum spanning tree)

#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 một ma trận
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";
}

void PRIM(int Graph[][100], int vertexNumber, SEdge *eaCategory)
{
int *_labelArray = new int[100]; // Mảng đánh nhãn cho 1 đỉnh thuộc tập Y hoặc V\Y
int _categoryNumber = 0; // Số phần tử trong tập T

/** === BƯỚC 1 === **/
// Gán tất cả các đỉnh của đồ thị G thuộc tập V\Y
for(int i=0; i < vertexNumber; i++)
{
_labelArray[i] = 0;
}

// Bắt đầu duyệt từ đỉnh 0, đưa đỉnh 0 vào tập Y
_labelArray[0] = 1;

/** === BƯỚC 4 === **/
// Lặp cho đến khi số phần tử của tập T là n-1
while (_categoryNumber < vertexNumber-1)
{
SEdge edgeMin; // Lưu lại cạnh có trọng số nhỏ nhất
int vlMin = -1; // Giá trị trọng số của cạnh edgeMin, khởi tạo là -1

/** === BƯỚC 2 === **/
for(int i= 0 ; i < vertexNumber; i++)
{
// Kiểm tra xem đỉnh w có thuộc tập V/Y hay không
if(_labelArray[i] == 1)
{
for(int j = 0; j < vertexNumber; j++)
{
bool a = _labelArray[j] == 0;   // Đã duyệt chưa
bool b = Graph[j][i] != 0 && Graph[i][j] != 0; // Có cạnh nối hay không
bool c = vlMin == -1 || Graph[j][i] < vlMin;   // Nếu cạnh nối giữa v và w nhỏ hơn cạnh có trọng số nhỏ nhất tìm được

if(a && b && c)
{
vlMin = Graph[j][i];    // Gán lại giá trị cạnh nhỏ nhất nho vlMin
edgeMin.m_iRow = i; // Gán lại giá trị đỉnh cho cạnh edgeMin
edgeMin.m_iCol = j; // Gán lại giá trị đỉnh cho cạnh edgeMin
}
}
}
}

/** === BƯỚC 3 === **/
eaCategory[_categoryNumber] = edgeMin; // Thêm cạnh edgeMin vào tập T
_categoryNumber++;         // Tăng số lượng phần tử tập T
_labelArray[edgeMin.m_iCol] = 1;     // Gán đỉnh w vừa duyệt qua vào tập Y
}
}

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

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

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

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