普里姆（Prim）算法

/*********************普里姆(Prim)算法******************/ //网类 template<class Type> class NetGraph { private: Type vexs[MAX];//顶点表 int arc[MAX][MAX];//邻接矩阵 int numVertexes, numEdges;//当前网中节点、边数量 int getPosition(Type el);//获取数据el在顶点表中的位置 Type readType();//外界读取一个数据 public: NetGraph();//创建网图 ~NetGraph(){}//析构函数 void print();//打印邻接矩阵 void MiniSpanTree_Prim();//Prim算法生成最小生成树 }; //获取数据el在顶点表中的位置 template<class Type> int NetGraph<Type>::getPosition(Type el) { int i; for (i = 0; i < this->numVertexes; i++) { if (this->vexs[i] == el) return i; } return -1; } //外界读取一个数据 template<class Type> Type NetGraph<Type>::readType() { Type ch; cout << "Input a edge data: "; cin >> ch; return ch; } //创建网图(手动输入) template<class Type> NetGraph<Type>::NetGraph() { int i,j; Type c1, c2; int p1, p2; int weight;//用于存储权值 cout << "Input Vertexes number: "; cin >> this->numVertexes; cout << "Input Edge number: "; cin >> this->numEdges; //检测顶点、边输入合法性 if (this->numVertexes < 1 || this->numEdges<1 || this->numEdges> this->numVertexes*(this->numVertexes - 1)) { cout << "Error input!" << endl; return; } //顶点初始化 for (i = 0; i < this->numVertexes; i++) { cout << "Input a Type data" << i + 1 << ": "; cin >> this->vexs[i]; } //邻接矩阵初始化 for (i = 0; i < this->numVertexes; i++) { for (j = 0; j < this->numVertexes; j++) { if (i == j) this->arc[i][j] = 0; else this->arc[i][j] = 65535; } } //边初始化 for (i = 0; i < this->numEdges; i++) { c1 = readType(); c2 = readType(); p1 = getPosition(c1); p2 = getPosition(c2); if (p1 == -1 || p2 == -1 || p1 == p2) { cout << "Earror Input!" << endl; return; } cout << "Input a weight value: "; cin >> weight; this->arc[p1][p2] = weight; this->arc[p2][p1] = weight; } } //打印邻接矩阵 template<class Type> void NetGraph<Type>::print() { cout << "******************************" << endl; cout << "打印邻接矩阵" << endl; int i, j; for (i = 0; i < this->numVertexes; i++) { for (j = 0; j < this->numVertexes; j++) cout << this->arc[i][j] << '\t'; cout << endl; } } //Prim算法生成最小生成树 template<class Type> void NetGraph<Type>::MiniSpanTree_Prim() { int min, i, j, k; int adjvex[MAX];//保存相关顶点下标 int lowcost[MAX];//保存相关顶点间边的权值 lowcost[0] = 0;//初始化第一个权值为0，即第一个元素加入生成树 adjvex[0] = 0;//初始化第一个顶点下表为0 for (i = 1; i < this->numVertexes; i++) { lowcost[i] = this->arc[0][i];//将第一个元素与之有关的权值存入数组 adjvex[i] = 0;//初始化都为第一个元素的下标 } for (i = 0; i < this->numVertexes; i++) { min = 65535;//初始化最小权值为65535 j = 1; k = 0; while (j < this->numVertexes) { if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; } j++; } cout << "(" << adjvex[k] << ", " << k << ") "; lowcost[k] = 0;//当前顶点的权值设置为0，表示此顶点已经完成任务 for (j = 1; j < this->numVertexes; j++) { if (lowcost[j] != 0 && this->arc[k][j] < lowcost[j]) { lowcost[j] = this->arc[k][j]; adjvex[j] = k; } } } } //测试程序 int main() { NetGraph<char> graph; graph.print(); graph.MiniSpanTree_Prim(); return 0; }