个回答

• 洗头最爱用飘柔

  2016-10-25 13:22:20

  已采纳

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

  3

• daxiao

  2017-09-01 15:44:42

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

  1

• 慕工程3931867

  2017-03-06 23:46:20

  /*
  		      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) 两条边的权值的修改，下边图片是修改后我运行的结果。

  

  2

• 慕工程3931867

  2017-03-06 21:38:12

  我也有同样的疑惑

  
  

  0

• 妙柴

  2016-08-19 18:11:23

  我照着打代码也是调整到最小边这里出错

  0