亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定

為什么克魯斯卡爾算法輸出會這樣呢

http://img1.sycdn.imooc.com//593689030001d89b12230639.jpg

http://img1.sycdn.imooc.com//593689030001b59519201039.jpg


下面是我看著老師的視頻寫的代碼,我看了好幾遍,沒發現有什么不同,但是就是出錯,不知道什么原因。

同樣的代碼,普力馬算法就正常


void?CMap::kruskalTree()
{
	int?value?=?0;
	int?edgeCount?=?0;

	//定義存放結點集合的數組
	vector<vector<int>>?nodeSets;

	//第一步:取出所有邊
	vector<Edge>?edgeVec;
	for?(int?i?=?0;?i?<?m_iCapacity;?i++)
	{
		for?(int?k?=?i?+?1;?k?<?m_iCapacity;?k++)
		{
			getValueFromMatrix(i,?k,?value);
			if?(value?!=?0)
			{
				Edge?edge(i,?k,?value);
				edgeVec.push_back(edge);
			}
		}
	}

	//第二步:從所有邊中取出組成最小生成樹的邊
	//1.找到算法結束條件
	while?(edgeCount?<?m_iCapacity?-?1)
	{
		//2.從邊集合中找到最小邊
		int?minEdgeIndex?=?getMinEdge(edgeVec);
		edgeVec[minEdgeIndex].m_bSelected?=?true;

		//3.找出最小邊連接的點
		int?nodeAIndex?=?edgeVec[minEdgeIndex].m_iNodeIndexA;
		int?nodeBIndex?=?edgeVec[minEdgeIndex].m_iNodeIndexB;

		bool?nodeAIsInSet?=?false;
		bool?nodeBIsInSet?=?false;

		int?nodeAInSetLabel?=?-1;
		int?nodeBInSetLabel?=?-1;

		//4.找出點所在的點集合
		for?(int?i?=?0;?i?<?(int)nodeSets.size();?i++)
		{
			nodeAIsInSet?=?isInSet(nodeSets[i],?nodeAIndex);
			if?(nodeAIsInSet)
			{
				nodeAInSetLabel?=?i;
			}
		}

		for?(int?i?=?0;?i?<?(int)nodeSets.size();?i++)
		{
			nodeBIsInSet?=?isInSet(nodeSets[i],?nodeBIndex);
			if?(nodeBIsInSet)
			{
				nodeBInSetLabel?=?i;
			}
		}

		//5.根據點所在集合的不同做出不同的處理
		if?(nodeAInSetLabel?==?-1?&&?nodeBInSetLabel?==?-1)
		{
			vector<int>?vec;
			vec.push_back(nodeAIndex);
			vec.push_back(nodeBIndex);
			nodeSets.push_back(vec);
		}
		if?(nodeAInSetLabel?==?-1?&&?nodeBInSetLabel?!=?-1)
		{
			nodeSets[nodeBInSetLabel].push_back(nodeAIndex);
		}
		if?(nodeAInSetLabel?!=?-1?&&?nodeBInSetLabel?==?-1)
		{
			nodeSets[nodeBInSetLabel].push_back(nodeBIndex);
		}
		if(nodeAInSetLabel?!=?-1?&&?nodeBInSetLabel?!=?-1?&&?nodeAInSetLabel?!=?nodeBInSetLabel)
		{
			mergeNodeSet(nodeSets[nodeAInSetLabel],?nodeSets[nodeBInSetLabel]);
			for?(int?k?=?nodeBInSetLabel;?k?<?(int)nodeSets.size()?-?1;?k++)
			{
				nodeSets[k]?=?nodeSets[k?+?1];
			}
		}
		if?(nodeAInSetLabel?!=?-1?&&?nodeBInSetLabel?!=?-1?&&?nodeAInSetLabel?==?nodeBInSetLabel)
		{
			continue;
		}

		m_pEdge[edgeCount]?=?edgeVec[minEdgeIndex];
		edgeCount++;

		cout?<<?edgeVec[minEdgeIndex].m_iNodeIndexA?<<?"--"?<<?edgeVec[minEdgeIndex].m_iNodeIndexB?<<?"??";
		cout?<<?edgeVec[minEdgeIndex].m_iWeightValue?<<?endl;
	}
}

bool?CMap::isInSet(vector<int>?nodeSet,?int?target)
{
	for?(int?i?=?0;?i?<?(int)nodeSet.size();?i++)
	{
		if?(nodeSet[i]?==?target)
		{
			return?true;
		}
	}

	return?false;
}

void?CMap::mergeNodeSet(vector<int>?&nodeSetA,?vector<int>?nodeSetB)
{
	for?(int?i?=?0;?i?<?(int)nodeSetB.size();?i++)
	{
		nodeSetA.push_back(?nodeSetB[i]?);
	}
}


正在回答

1 回答

從報錯信息上看是容器下標越界的意思就是說你容器的區間傳入了錯誤的值或大或小。

隨后檢查了代碼在75行處nodeSets[nodeBInSetLabel].push_back(nodeBIndex);下標處應該是nodeAInSetLabel 修改看看可否解決問題。

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

騎著毛驢追太陽 提問者

非常感謝!
2017-08-08 回復 有任何疑惑可以回復我~

舉報

0/150
提交
取消

為什么克魯斯卡爾算法輸出會這樣呢

我要回答 關注問題
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號