高级数据结构：最小生成树及普里姆算法

一、最小生成树定义：

对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（树中所有边上的权值和）也不同，设R为G的所有生成树的集合，若T为R中权值和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree，MST）
注：

1. 最小生成树可能有多个，但边的权值之和总是唯一且最小的
2. 最小生成树的边数=定点数-1，砍掉一条则不连通，增加一条则会出现回路
3. 若一个连通图本身就是一颗树，则其最小生成树就是它本身
4. 只有连通图才有生成树，非连通图只有生成森林

二、普里姆算法（Prim）

从某一个顶点（所以存在多个最小生成树）开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止

实现代码：

#define SIZE 10
#define MAX_WEIGHT 65535
class Graph
{
public:
	Graph();
	~Graph();
	void InsertVertex(char v);
	void InsertEdge(char v1,char v2,int weight);
	void PrintGraph();
	int GetVertexIndex(char v); //获得顶点v在顶点数组的下标
	void MST_Prim(char vertex); //
private:
	int MaxVertex; //顶点的最大个数
	int NumVertex; //顶点的实际个数
	char *Vertex; //存储顶点的一维数组
	//int **Edge;
	int Edge[SIZE][SIZE]; //存储顶点边的信息
	int NumEdge;  //边的实际条数
};
//给图中的属性进行初始化

Graph::Graph()
{
	MaxVertex = SIZE;
	NumVertex = NumEdge = 0;
	Vertex = new char[MaxVertex];
	for(int i = 0;i<MaxVertex;i++)
	{
		for(int j = 0;j<MaxVertex;j++)
		{
			if(i == j)
				Edge[i][j] = 0;
			else
				Edge[i][j] = MAX_WEIGHT;
		}
	}
}
Graph::~Graph()
{
	if(Vertex != NULL)
	{
		delete []Vertex;
		Vertex = NULL;
	}
}
void Graph::InsertVertex(char v)
{
	if(NumVertex >= MaxVertex)
		return;
	Vertex[NumVertex++] = v;
}
int Graph::GetVertexIndex(char v)
{
	int i;
	for(i = 0;i<NumVertex;i++)
	{
		if(v == Vertex[i])
			return i;
	}
	return -1;
}

void Graph::InsertEdge(char v1,char v2,int weight)
{
	int p1 = GetVertexIndex(v1);
	int p2 = GetVertexIndex(v2);
	if(p1 == -1 || p2 == -1)
		return ;
	//将p1和p2所对应的二维数组的值改为1，说明两个顶点有边
	Edge[p1][p2] = Edge[p2][p1] = weight;
	NumEdge++;
}
void Graph::PrintGraph()
{
	int i,j;
	cout<<"  ";
	for(i = 0;i<NumVertex;i++)
		cout<<Vertex[i]<<" ";
	cout<<endl;
	for(i = 0;i<NumVertex;++i)
	{
		cout<<Vertex[i]<<" ";
		for(j = 0;j<NumVertex;j++)
		{
			if(Edge[i][j] == MAX_WEIGHT)
				cout<<"*"<<" ";
			else
				cout<<Edge[i][j]<<" ";
		}
		cout<<endl;
	}
}
void Graph::MST_Prim(char vertex)
{
	/*定义两个数组mst和lowcost,假设从顶点0开始则
	lowcost[i] = 5表示从起始点0到顶点i的权值为5
	mst[i]的值表示的是起始点，例如mst[5]=0,说明从起始点0到顶点5
	*/
	int *mst = new int[NumVertex];
	int *lowcost =  new int[NumVertex];
	//对两个数组进行初始化，从vertex顶点开始
	int k = GetVertexIndex(vertex);

	int i,j;
	for(i = 0;i<NumVertex;++i)
	{
		if(i == k)
			lowcost[i] = 0;//说明从当前顶点开始，已被选中
		else
		{
			mst[i] = k;
			lowcost[i] = Edge[k][i];
		}
	}
	//构建最小生成树，即是循环查找n-1条最小的边，并将每次找到的输出
	int min,min_index;
	int start,end;
	for(i = 0;i<NumVertex-1;++i)
	{
		min = MAX_WEIGHT;
		min_index = -1;
		for(j = 0;j<NumVertex;j++)
		{
			if(lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];
				min_index = j; //记住最小值下标，即是终点，由此下标找到mst的值，即是起始点
			}
		}
		start = mst[min_index];
		end = min_index;
		cout<<Vertex[start]<<"->"<<Vertex[end]<<":"<<min<<endl; //打印找到的当前最小边
		lowcost[min_index] = 0; //置为0，说明已经被选
		//更新，从当前选中的顶点min_index继续开始
		for(j = 0;j<NumVertex;j++)
		{
			int cost = Edge[min_index][j];//从新的顶点到其余顶点的权值
			if(cost < lowcost[j])//将新的权值和以前的进行比较，如果小就更新
			{
				lowcost[j] = cost;
				mst[j] = min_index;
			}
		}
	}
	delete[]mst;
	delete[]lowcost;
	mst=NULL;
	lowcost=NULL;
}
void main()
{
	Graph g;
	g.InsertVertex('a');
	g.InsertVertex('b');
	g.InsertVertex('c');
	g.InsertVertex('d');
	g.InsertVertex('e');
	g.InsertVertex('f');
	g.InsertEdge('a','b',6);
	g.InsertEdge('a','c',1);
	g.InsertEdge('a','d',5);
	g.InsertEdge('b','c',5);
	g.InsertEdge('b','e',3);
	g.InsertEdge('c','d',5);
	g.InsertEdge('c','e',6);
	g.InsertEdge('c','f',4);
	g.InsertEdge('d','f',2);
	g.InsertEdge('e','f',6);
	g.PrintGraph();
	g.MST_Prim('a');
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173