Fv5QkbY1G5LDg_28R1J8Oief5nmC

Prim算法

没听课（）教材代码，复制过来了

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
/******************************* 
   对应教材6.4.1节，Prim算法 
********************************/
#include <iostream>
using namespace std;

const int MaxSize = 10;                   //图中最多顶点个数
int visited[MaxSize] = {0};              //全局数组变量visited初始化
template <class DataType>
class MGraph
{
public:
   	MGraph(DataType a[ ], int n, int e);     //构造函数，建立具有n个顶点e条边的图
   	~MGraph( ){ };                        //析构函数
 	void Prim(int v);
private:
    DataType vertex[MaxSize];           //存放图中顶点的数组
    int edge[MaxSize][MaxSize];           //存放图中边的数组
    int vertexNum, edgeNum;              //图的顶点数和边数

 	int MinEdge(int r[ ], int n);
};
  
template <class DataType>
MGraph<DataType> :: MGraph(DataType a[ ], int n, int e) 
{
   	int i, j, k, w;
   	vertexNum = n; edgeNum = e;
   	for (i = 0; i < vertexNum; i++)          //存储顶点
   		vertex[i] = a[i];
   	for (i = 0; i < vertexNum; i++)          //初始化邻接矩阵
 		for (j = 0; j < vertexNum; j++)
   			if (i == j)
			   edge[i][j] = 0;
			else
			   edge[i][j] = 100;               //假设边上权的最大值是100             
   	for (k = 0; k < edgeNum; k++)           //依次输入每一条边
   	{
   		cout << "请输入边依附的两个顶点的编号，以及边上的权值：";
		cin >> i >> j >> w;                       //输入边依附的两个顶点的编号
		edge[i][j] = w; edge[j][i] = w;           //置有边标志
   	}
}

template <class DataType>
void MGraph<DataType> :: Prim(int v)                           //从顶点v出发
{   
	int i, j, k;
	int adjvex[MaxSize], lowcost[MaxSize];
    for (i = 0; i < vertexNum; i++)             //初始化辅助数组
	{
		lowcost[i] = edge[v][i]; adjvex[i] = v;
	}
	lowcost[v] = 0;                         //将顶点v加入集合U
	for (k = 1; k < vertexNum; k++)            //迭代n-1次
	{
		j = MinEdge(lowcost, vertexNum);       //寻找最短边的邻接点j
      	cout << "(" << vertex[j] << "," << vertex[adjvex[j]] << ")" << lowcost[j] << endl; 
		lowcost[j] = 0;                       //顶点j加入集合U
		for (i = 0; i < vertexNum; i++)          //调整辅助数组
	        if (edge[i][j] < lowcost[i]) {
				lowcost[i] = edge[i][j]; 
				adjvex[i] = j;
        	}
    }
}

template <class DataType>
int MGraph<DataType> :: MinEdge(int r[ ], int n)
{
	int index = 0, min = 100;           //此处如果仅记载最小值下标会有bug 
	for (int i = 1; i < n; i++)
		if (r[i] != 0 && r[i] < min)
		{
			min = r[i]; index = i;		
		}
	return index;
}

int main( )
{
	/*测试数据使用教材 图6-16 所示带权无向图， 输入边依次为 
	(0 1 34)(0 2 46)(0 5 19)(1 4 12)(2 3 17)(2 5 25)(3 4 38)(3 5 25)(4 5 26) */ 
	char ch[ ]={'A','B','C','D','E','F'};       
	MGraph<char> MG{ch, 6, 9};             
	MG.Prim(0);
	return 0;
}