为了账号安全,请及时绑定邮箱和手机立即绑定

打印结果老是不对。

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


正在回答

2 回答

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

0 回复 有任何疑惑可以回复我~
#1

xk今天要改名了

我看错了 ,并不一样,老师的并没有问题。
2017-09-02 回复 有任何疑惑可以回复我~

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


0 回复 有任何疑惑可以回复我~
#1

Uchiha_Obito 提问者

我的Edge类构造函数是要先传value..这个没问题
2017-09-02 回复 有任何疑惑可以回复我~
#2

xk今天要改名了 回复 Uchiha_Obito 提问者

那你的算法应该没有问题,我试过了,可以出结果,应该是其他地方有问题。
2017-09-02 回复 有任何疑惑可以回复我~

举报

0/150
提交
取消

打印结果老是不对。

我要回答 关注问题
意见反馈 帮助中心 APP下载
官方微信