最小边这个函数是不是有点问题？

？\除了边没有被访问过这个条件外，是不是还要考虑两个顶点是不是都被访问过。例如：A-B的权值为2时，不考虑两个顶点是否都被访问过的话，A、B、F就成了一个环，明显不对。

醉独醒

2016-08-18

源自：数据结构探险之图篇 4-3

关注问题我要回答

1312

操作

收起

5 回答

洗头最爱用飘柔回答被采纳 +3 积分
2016-10-25

是有错的，这个算法。因为第一个for循环找出的是最后一条没有被选择的边，但是该边的大小如何是未知的，本来无所谓的。但是第二个for循环的i起始是上一次的i。假如，最短的边在i前，就无法选出正确的边。解决办法也很简单，就是用冒泡法，比较所有的没被选择的边，选出最小的就行

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

收起回答

醉独醒提问者

非常感谢！

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

qq_慕斯卡2428267

我觉得可能是老师忘记在第一个for里的if里面加一个break

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

daxiao
2017-09-01

我想问那个，他首先调用primTree(int nodeIndex)的nodeindex 一开始并未使m_bisvisited为true，感觉会导致闭环的问题

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
		{
			//判断是否形成回环，形成回环时，此最小权值的边应该舍去
			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) 两条边的权值的修改，下边图片是修改后我运行的结果。