#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>

#define Max 150
#define Found 1
#define notFound 0

using namespace std;

struct Graph {
	int sodinh;
	int a[Max][Max];
	int visited[Max];
	int LuuVet[Max];
};

struct Queue {
	int size;
	int a[Max];
};

struct Canh
{
	int u;//Dinh thu nhat
	int v;//Dinh thu hai
	int trongso;
};

Canh T[Max];

void readGraph(string fn, Graph &g);
void printGraph(Graph g);

void DFS(int s, Graph &g);
void duyetDFS(int s, int f, Graph &g);

void khoiTao(Queue &q);
bool Them(int k, Queue &q);
bool kiemTraRong(Queue q);
bool Lay(int &v, Queue &q);

void BFS(int s, Graph &g);
void duyetBFS(int s, int f, Graph &g);

bool dfsHamilton(int path[], Graph g, int &count);
int visit(int u, int visited[], int &count, int &flag, int path[], Graph g);
void printHamilton(Graph g, int path[]);

void Prim(Graph g);

void Kruskal(Graph g, int &nT, Canh T[]);
void khoiTaoMangCanh(Graph g, int &nCanh, Canh DSCanh[]);
void sapXepCanh(int nCanh, Canh DSCanh[], Graph g);
bool coChuTrinh(Graph g, Graph h, int iMin, Canh DSCanh[]);

int main()
{
	int a,countHamilton;
	Graph g;
	Canh T[100];
	int path[100];
	readGraph("test9.txt", g);
	printGraph(g);
	//dfsHamilton(path, g, countHamilton);
	//Prim(g);
	Kruskal(g, a, T);
	system("pause");
}

void readGraph(string fn, Graph &g) {
	fstream f;
	f.open(fn);
	f >> g.sodinh;
	for (int i = 0; i < g.sodinh; i++)
		for (int j = 0; j < g.sodinh; j++)
			f >> g.a[i][j];
	f.close();
}

void printGraph(Graph g) {
	cout << "So dinh la: " << g.sodinh << endl;
	for (int i = 0; i < g.sodinh; i++) {
		for (int j = 0; j < g.sodinh; j++)
			cout << g.a[i][j];
		cout << endl;
	}
	cout << endl;
}

//hàm xét từ đỉnh s bất kỳ
void DFS(int s, Graph &g)
{
	//Đánh dấu đỉnh s đã suyệt
	g.visited[s] = 1;

	//Tìm xem từ đỉnh s có đỉnh i nào chưa duyệt và nối trực tiếp với s
	for (int i = 0; i < g.sodinh; i++)
		if (g.visited[i] == 0 && g.a[s][i] != 0)
		{
			g.LuuVet[i] = s; //Lưu trước đỉnh i là đỉnh s
			DFS(i, g);//gọi đệ quy tiến hành xét tiếp
		}
}

//Hàm tìm đường đi từ đỉnh s đến đỉnh f trong đồ thị g
void duyetDFS(int s, int f, Graph &g)
{
	//Khởi tạo giá trị ban đầu, tất cả các địh chư đuợc duyệt và chưa lưu vết
	for (int i = 0; i < g.sodinh; i++)
	{
		g.visited[i] = 0;
		g.LuuVet[i] = -1;
	}

	//Gọi hàm DFS
	DFS(s, g);

	if (g.visited[f] == 1)
	{
		//In ket qua
		int j = f;
		while (j != s)
		{
			cout << j+1 << "<---";
			j = g.LuuVet[j];
		}
		cout << s+1;
		cout << endl;
	}
	else
		cout << "Khong co duong di tu dinh " << s+1<< " den dinh " << f+1;
	cout << endl;
}

void khoiTao(Queue &q) {
	q.size = 0;
}
bool Them(int k, Queue &q)
{
	if (q.size + 1 > Max) return false;
	q.a[q.size] = k;
	q.size++;
	return true;
}
bool kiemTraRong(Queue q)
{
	return (q.size == 0);
}
bool Lay(int &v, Queue &q)
{
	if (kiemTraRong(q)) return false;
	v = q.a[0];
	for (int i = 0; i < q.size - 1; i++)
		q.a[i] = q.a[i + 1];
	q.size--;
	return true;
}

void BFS(int s, Graph &g)
{
	Queue q;
	khoiTao(q);
	Them(s, q);//Thêm đỉnh s vào q

	while (!kiemTraRong(q))
	{
		Lay(s, q);
		//Đánh dấu đỉnh s đã suyệt
		g.visited[s] = 1;
		for (int i = 0; i < g.sodinh; i++)
			if (g.visited[i] == 0 && g.a[s][i] != 0)
			{
				Them(i, q);
				g.LuuVet[i] = s;
			}
	}
}

void duyetBFS(int s, int f, Graph &g)
{
	//Khởi tạo giá trị ban đầu, tất cả các địh chư đuợc duyệt và chưa lưu vết
	for (int i = 0; i < g.sodinh; i++)
	{
		g.visited[i] = 0;
		g.LuuVet[i] = -1;
	}

	//Gọi hàm BFS
	BFS(s, g);

	if (g.visited[f] == 1)
	{
		//In ket qua
		int j = f;
		while (j != s)
		{
			cout << j+1 << "<---";
			j = g.LuuVet[j];
		}
		cout << s+1;
		cout << endl;
	}
	else
		cout << "Khong co duong di tu dinh " << s << " den dinh " << f;
	cout << endl;
}

bool dfsHamilton(int path[], Graph g, int &count)
{
	int count;
	int start = 0;
	int flag = notFound; //2: cho biết ý nghĩa của biến flag
	int visited[Max]; //3: cho biết ý nghĩa của mảng visited
	for (int i = 0; i < g.sodinh; i++) {
		visited[i] = 0;
	}
	count = 0; //đếm số lượng đỉnh trong chu trình Hamilton đang tìm
	path[count] = start;
	count++;
	visited[start] = 1;
	flag = visit(start, visited, count, flag, path, g);
	if (flag) return Found; else return notFound;
}

int visit(int u, int visited[], int &count, int &flag, int path[], Graph g) {
	if (flag == Found) return flag;
	for (int v = 0; v < g.sodinh; v++)
		if (visited[v] == 0 && g.a[u][v] != 0) {//nếu u kề v, v chưa thăm
			visited[v] = 1;
			path[count] = v;
			count++;
			if (count == g.sodinh && g.a[v][path[0]] != 0) //4: cho biết ý nghĩa
				flag = Found;
			visit(v, visited, count, flag, path, g);
		}
	if (flag == notFound) {//5: cho biết ý nghĩa của đoạn chtr này
		visited[u] = 0; count--;
	}
	return flag;
}

void printHamilton(Graph g, int path[], int &count) {
	if (dfsHamilton(path, g, count) == 1) {
		cout << "Chu trinh la: ";
		for (int i = 0; i < count; i++) cout << path[i] << " ";
		cout << endl;
	}
	else cout << "Do thi khong co chu trinh";
}

void Prim(Graph g)
{
	//B1: Gán số cạnh của cây khung ban đầu là 0
	int nT = 0;
	//B2: Khởi tạo nhãn các đỉnh là chưa duyệt (0)
	for (int i = 0; i < g.sodinh; i++)
		g.visited[i] = 0;

	//B3: Đánh dấu đỉnh 0 là đã duyệt
	g.visited[0] = 1;

	while (nT < g.sodinh - 1)//nếu đủ n -1 cạnh thì dừng (Tại sao, dựa vào đâu??)
	{
		Canh canhnhonhat;//dùng để lưu trữ cạnh nhỏ nhất từ một đỉnh đã xét tới đỉnh chưa xét
		int min = -1;	//Tại sao lấy -1????
		for (int i = 0; i < g.sodinh; i++)
			if (g.visited[i] == 0) //nếu là đỉnh chưa duyệt. Điều kiện đúng khi j thuộc tập Y hay V\Y
			{
				for (int j = 0; j < g.sodinh; j++)
					if (g.visited[j] == 1 && (g.a[i][j] != 0))
					{
						if (min == -1 || g.a[i][j] < min)
						{
							min = g.a[i][j];
							canhnhonhat.u = i;
							canhnhonhat.v = j;
							canhnhonhat.trongso = g.a[i][j];
						}
					}
			}

		//Thêm cạnh nhỏ nhất vào tập T
		T[nT] = canhnhonhat;
		nT++;//tăng số cạnh lên 1

		g.visited[canhnhonhat.u] = 1;//Tại sao????

	}

	//Tổng trọng số của cây khung
	int sum = 0;
	cout << "Cay khung nho nhat cua do thi la: " << endl;
	for (int i = 0; i < nT; i++)
	{
		cout << "(" << T[i].u+1 << ", " << T[i].v+1 << ") ";
		sum += T[i].trongso;
	}
	cout << endl;
	cout << "Tong gia tri cua cay la: " << sum << endl;
}

void Kruskal(Graph g, int &nT, Canh T[])
{
	int nCanh;
	Canh DSCanh[100];
	Graph h;
	for (int i = 0; i < g.sodinh; i++)
		for (int j = 0; j < g.sodinh; j++)
			h.a[i][j] = 0;
	//Khởi tạo danh sách cạnh của đồ thị
	khoiTaoMangCanh(g, nCanh, DSCanh);
	//Sắp xếp danh sách cạnh tăng dần theo trọng số
	sapXepCanh(nCanh, DSCanh, g);

	//Gán số cạnh của cây khung là 0
	nT = 0;

	int iMin = 0; //chỉ số phần tử cạnh đang xét

				  //Lần lượt đưa các cạnh vào cây khung để không tạo ra chu trình
	while (nT < g.sodinh - 1)
	{
 		if (iMin < nCanh)
		{
			if (coChuTrinh(g, h, iMin, DSCanh) == false)
			{
				T[nT] = DSCanh[iMin];
				cout << endl << T[nT].u << "-" << T[nT].v << "-" << T[nT].trongso;
				nT++;
			}
			iMin++;
		}
		else
		{
			break;
		}
	}
	cout << endl;
	int sum = 0;
	//for (int i = 0; i < nT; i++) {
		//cout << "(" << T[i].u + 1 << "," << T[i].v + 1 << ")" << setw(4);
		//sum = sum + T[i].trongso;
	//}
	//cout << endl << "Tong gia tri cua cay khung la " << sum << endl;
}

void khoiTaoMangCanh(Graph g,  int &nCanh, Canh DSCanh[]) {
	nCanh = 0;
	int j = 0;
	for (int i = 0; i < g.sodinh; i++) {
		for (int j=i+1;j<g.sodinh;j++)
			if (g.a[i][j] != 0) {
				DSCanh[nCanh].trongso = g.a[i][j];
				DSCanh[nCanh].u = i;
				DSCanh[nCanh].v = j;
				nCanh++;
			}
	}
	//for (int i = 0; i < nCanh; i++) cout << DSCanh[i].u + 1 << "-" << DSCanh[i].v + 1 << "-" << DSCanh[i].trongso << setw(4);
}

void sapXepCanh(int nCanh, Canh DSCanh[], Graph g) {
	bool nhohon = 1;
	while (nhohon == 1) {
		nhohon = 0;
		for (int i = 0; i < nCanh-1; i++)
			if (DSCanh[i].trongso > DSCanh[i+1].trongso) {
				Canh Temp;
				Temp = DSCanh[i];
				DSCanh[i] = DSCanh[i + 1];
				DSCanh[i + 1] = Temp;
				nhohon = 1;
			}
		}
	for (int i = 0; i < nCanh; i++) cout << DSCanh[i].u+1 << "-" << DSCanh[i].v+1 << "-" <<  DSCanh[i].trongso << setw(4);
}

bool coChuTrinh(Graph g, Graph h, int iMin, Canh DSCanh[]) {
	int pathx[100],c;
	h.a[DSCanh[iMin].u][DSCanh[iMin].v] = 1;
	if (dfsHamilton(pathx, h, c)) return true;
	return false;
}
//2 = 1 5 = 1