虽说是生成树,但我只将生成的边输出了。至于怎么用这些边来创建树。。。我不知道_(:з」∠)_
1 //Prime方法生成最小生成树 2 void GraphAdjacencyListWeight::GenerateMSCPPrime(int FirstVertex) { 3 int *visited = new int[VertexNumber]; 4 memset(visited, 0, VertexNumber * sizeof(int)); 5 //-1代表没用到 6 //0代表此点已放进容器 7 CLOSEEDGE *CloseEdge = new CLOSEEDGE[VertexNumber]; 8 for (int lop = 0; lop < VertexNumber; lop++) { 9 CloseEdge[lop].Weight = -1; 10 CloseEdge[lop].StartVer = -1; 11 } 12 13 CloseEdge[FirstVertex].StartVer = 0; 14 CloseEdge[FirstVertex].Weight = 0; 15 //起点放进容器 16 visited[FirstVertex] = 1; 17 18 //将起点的邻接信息放入CloseEdge 19 for (auto tmpPtr = (VectorVertexList[FirstVertex])->firstArc; tmpPtr != nullptr; tmpPtr = tmpPtr->nextArc) { 20 CloseEdge[tmpPtr->AdjacencyNode].StartVer = FirstVertex; 21 CloseEdge[tmpPtr->AdjacencyNode].Weight = tmpPtr->weight; 22 } 23 24 int k = -1; 25 while (!IsAllVisited(visited)) { 26 k = SearchMinWeight(CloseEdge); 27 //输出生成的边 28 cout << "(" << CloseEdge[k].StartVer << " , " << VectorVertexList[k]->VertexIndex << ")" << endl; 29 visited[k] = 1; 30 31 UpdateCloseEdge(CloseEdge, k); 32 } 33 34 //销毁 35 delete[]visited; 36 delete[]CloseEdge; 37 }
1 int GraphAdjacencyListWeight::SearchMinWeight(CLOSEEDGE closeedge[]) { 2 int miniWeight = -1; 3 int index = -1; 4 for (int lop = 0; lop < VertexNumber; lop++) { 5 if ((miniWeight > closeedge[lop].Weight || miniWeight == -1) && closeedge[lop].Weight > 0) { 6 miniWeight = closeedge[lop].Weight; 7 index = lop; 8 } 9 } 10 if (index == -1) { 11 //返回 -1 说明所有点都取了 12 return -1; 13 } 14 return index; 15 } 16 17 void GraphAdjacencyListWeight::UpdateCloseEdge(CLOSEEDGE CE[], int k) { 18 //k点已被收录 19 CE[k].Weight = 0; 20 CE[k].StartVer = 0; 21 22 for (auto tmpPtr = VectorVertexList[k]->firstArc; tmpPtr != nullptr; tmpPtr = tmpPtr->nextArc) { 23 //已是最小生成树的成员,不进行比较 24 if (CE[tmpPtr->AdjacencyNode].Weight == 0) { 25 continue; 26 } 27 if (CE[tmpPtr->AdjacencyNode].Weight >= tmpPtr->weight || CE[tmpPtr->AdjacencyNode].Weight == -1) { 28 CE[tmpPtr->AdjacencyNode].StartVer = k; 29 CE[tmpPtr->AdjacencyNode].Weight = tmpPtr->weight; 30 } 31 } 32 }
运行结果:
参照书本的174页的那个图