                        課程
                    
                        /后端開發(fā)
                        
                            /C++
                        
                        /數(shù)據(jù)結構探險之圖篇

最小邊這個函數(shù)是不是有點問題？

？\除了邊沒有被訪問過這個條件外，是不是還要考慮兩個頂點是不是都被訪問過。例如：A-B的權值為2時，不考慮兩個頂點是否都被訪問過的話，A、B、F就成了一個環(huán)，明顯不對。

醉獨醒

2016-08-18

源自：數(shù)據(jù)結構探險之圖篇 4-3

關注問題我要回答

1282

操作

收起

5 回答

洗頭最愛用飄柔回答被采納 +3 積分
2016-10-25

是有錯的，這個算法。因為第一個for循環(huán)找出的是最后一條沒有被選擇的邊，但是該邊的大小如何是未知的，本來無所謂的。但是第二個for循環(huán)的i起始是上一次的i。假如，最短的邊在i前，就無法選出正確的邊。解決辦法也很簡單，就是用冒泡法，比較所有的沒被選擇的邊，選出最小的就行

3 回復有任何疑惑可以回復我~

收起回答

#1

醉獨醒提問者

非常感謝！

2017-03-13 回復有任何疑惑可以回復我~

#2

qq_慕斯卡2428267

我覺得可能是老師忘記在第一個for里的if里面加一個break

2019-07-27 回復有任何疑惑可以回復我~

daxiao
2017-09-01

我想問那個，他首先調(diào)用primTree(int nodeIndex)的nodeindex 一開始并未使m_bisvisited為true，感覺會導致閉環(huán)的問題

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

收起回答

慕工程3931867
2017-03-06

/*
		??????A
		??/???|???\
		?/????|????\
		B——-F——-E
		\????/??\??/
		?\?/?????\/
		??C———-D


		??A?B?C?D?E?F?G
		??0?1?2?3?4?5?6

		??A-B?6???A-E?5???A-F?1
		??B-C?3???B-F?2???
		??C-F?4(8)???C-D?7
		??D-F?8(4)???D-E?2
		??E-F?9
		??
*/

int?Map::getMinEdge(vector<Edge>?edgeVec)
{
	int?minWeight?=?0;
	int?edgeIndex?=?0;
	int?i?=?0;

	for?(?;?i?<?(int)edgeVec.size();?i++)
	{
		if?(!edgeVec[i].m_bSelected)
		{
			minWeight?=?edgeVec[i].m_iWeightValue;
			edgeIndex?=?i;
			break;
		}
	}

	//獲取最小邊失敗的情況
	if?(minWeight?==?0)
	{
		return?-1;
	}

	//這里i的值可以不從零開始
	for?(?;?i?<?(int)edgeVec.size();?i++)
	{
		if?(edgeVec[i].m_bSelected)
		{
			continue;
		}
		else
		{
			//判斷是否形成回環(huán)，形成回環(huán)時，此最小權值的邊應該舍去
			if?(m_pNodeArray[edgeVec[i].m_iNodeIndexB].m_bIsVisited)
			{
				continue;
			}
			if?(minWeight?>?edgeVec[i].m_iWeightValue)
			{
				minWeight?=?edgeVec[i].m_iWeightValue;
				edgeIndex?=?i;
			}
		}
	}
	

	return?edgeIndex;
}

上面是修改的代碼和C-F 4(8) ??D-F 8(4) 兩條邊的權值的修改，下邊圖片是修改后我運行的結果。