求最小生成樹——kruskal算法

kruskal算法

C++代碼實作

1. 輸入邊資訊：兩頂點及權重
2. 按權重從小到大排序
3. 找n-1條不構成回路的最小邊（難點：判斷是否構成回路）

#include<iostream>
using namespace std;

//邊結構體
typedef struct edge {
	int vex1;
	int vex2;
	int weight;
}edge;

int main()
{
	edge ed[10];
	int i = 0;
	cout << "請輸入兩點及權重：" << endl;
	for (i = 0; i < 10; i++)
	{
		cin >> ed[i].vex1 >> ed[i].vex2 >> ed[i].weight;
	}
	//按照權重從小到大排序
	for (i = 0; i < 10; i++)
	{
		int t = 0;
		int min = 0x7fffffff;
		for (int j = i; j < 10; j++)
		{
			if (ed[j].weight < min)
			{
				min = ed[j].weight;
				t = j;
			}
		}	
		edge m;
		m = ed[i];
		ed[i] = ed[t];
		ed[t] = m;
	}
	//儲存頂點之間是否可達标志
	bool visited[10][10] = { false }; 
	for (i = 0; i < 10; i++)
		visited[i][i] = true;
	//找不構成回路的最小邊
	for (i = 0; i < 10; i++)
	{
		if (visited[ed[i].vex1][ed[i].vex2] == false)
		{
			visited[ed[i].vex1][ed[i].vex2] = true;
			visited[ed[i].vex2][ed[i].vex1] = true;
			cout << ed[i].vex1 << "-" << ed[i].vex2 << "：" << ed[i].weight << endl;
			//更新可達狀态
			for (int j = 0; j < 10; j++)
			{
				if (visited[ed[i].vex1][j])
					visited[ed[i].vex2][j] = visited[ed[i].vex1][j];
				if(visited[ed[i].vex2][j])
					visited[ed[i].vex1][j] = visited[ed[i].vex2][j];
			}
			for (int j = 0; j < 10; j++)
			{
				if (visited[ed[i].vex1][j])
				{
					for (int k = 0; k < 10; k++)
					{
						if (visited[ed[i].vex1][k])
							visited[j][k] = visited[ed[i].vex1][k];
					}
				}
				if (visited[ed[i].vex2][j])
				{
					for (int k = 0; k < 10; k++)
					{
						if (visited[ed[i].vex2][k])
							visited[j][k] = visited[ed[i].vex2][k];
					}
				}
			}
		}
	}
}