Uchiha_Obito
2017-09-01 13:46
//普利姆算法 void CMap::primTree(int nodeIndex) { vector<int> nodeVec; vector<Edge> edgeVec; int value = 0; int edgeCount = 0; nodeVec.push_back(nodeIndex); cout << m_pNodeArray[nodeIndex].m_cData << endl; m_pNodeArray[nodeIndex].m_bIsVisited = true; while (edgeCount < m_iCapacity - 1) { int temp = nodeVec.back(); for (int i = 0; i < m_iCapacity; ++i) { getValueFromMatrix(temp, i, value); if (value != 0) { if (m_pNodeArray[i].m_bIsVisited) { continue; } else { Edge edge(value, temp, i); edgeVec.push_back(edge); } } else { continue; } } int min = getMinEdge(edgeVec); edgeVec[min].m_bIsSelect = true; m_pEdgeArray[edgeCount] = edgeVec[min]; edgeCount++; cout << edgeVec[min].m_iNodeIndexA << "---" << edgeVec[min].m_iNodeIndexB << " "; cout << edgeVec[min].m_iWeightValue << endl; int bNodeIndex = edgeVec[min].m_iNodeIndexB; nodeVec.push_back(bNodeIndex); m_pNodeArray[bNodeIndex].m_bIsVisited = true; cout << m_pNodeArray[bNodeIndex].m_cData << endl; } } int CMap::getMinEdge(vector<Edge> vec) { int edgeIndex = 0; int minWeight = 0; int i = 0; for (; i < vec.size(); ++i) { if (!vec[i].m_bIsSelect) { edgeIndex = i; minWeight = vec[i].m_iWeightValue; break; } } if (minWeight == 0) { return -1; } for (; i < vec.size(); ++i) { if (vec[i].m_bIsSelect) { continue; } else { if (minWeight > vec[i].m_iWeightValue) { minWeight = vec[i].m_iWeightValue; edgeIndex = i; } } } return edgeIndex; } 这是代码,检查了好多遍,完全照着写打印结果也是错的。 下面的输出: A 0---5 1 F 5---1 2 B 5---3 2 D 1---2 3 C 3---4 4 E 求大佬解答。。
你看了kruskal算法吗,他的打印结果和你这个一样,很迷啊。
第18行应该是Edge edge(temp,i,value);
数据结构探险之图篇
56337 学习 · 81 问题
相似问题