问答详情
源自:4-2 图的编码实战-最小生成树之普利姆算法(二)

打印结果老是不对。

//普利姆算法
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
求大佬解答。。


提问者:Uchiha_Obito 2017-09-01 13:46

个回答

  • xk今天要改名了
    2017-09-02 15:34:33

    你看了kruskal算法吗,他的打印结果和你这个一样,很迷啊。

  • xk今天要改名了
    2017-09-01 19:08:19

    第18行应该是Edge edge(temp,i,value);