1回答

• 

  幕布斯9075980

  2018-04-30 10:56:16

  已采纳

  void CMap::kruskalTree()

  {

  int value = 0;

  int edgeCount = 0;

  
  

  vector<vector<int>> nodeSets;

  //之前一直显示vector subscript out of range，这是因为后面出现对vector直接取vec[]的语句，这是不对的

  //因为vector没有分配空间，我在这里分配空间后就可以了。

  nodeSets.resize(m_iCapacity*m_iCapacity);

  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;

  //4找出点所在的点的集合

  bool nodeAIsInSet = false;

  bool nodeBIsInSet = false;

  int nodeAInSetLabel = -1;

  int nodeBInSetLabel = -1;

  for (int i = 0; i < (int)nodeSets.size(); i++)

  {

  nodeAIsInSet = IsInset(nodeSets[i], nodeAIndex);

  if (nodeAIsInSet)//点在指定的集合中

  {

  nodeAInSetLabel = i;//A点所在的点集合的索引

  }

  }

  for (int i = 0; i < (int)nodeSets.size(); i++)

  {

  nodeBIsInSet = IsInset(nodeSets[i], nodeBIndex);

  if (nodeBIsInSet)//点在指定的集合中

  {

  nodeBInSetLabel = i;//A点所在的点集合的索引

  }

  }

  //5根据点所在的集合的不同做出不同的处理

  if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1)

  {

  vector<int>vec;

  vec.push_back(nodeAIndex);

  vec.push_back(nodeBIndex);

  nodeSets.push_back(vec);

  }

  else

  if (nodeAInSetLabel == -1 && nodeBInSetLabel != -1)//A不在任何集合中

  {

  nodeSets[nodeBIndex].push_back(nodeAIndex);

  }

  else

  if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1)

  {

  nodeSets[nodeAIndex].push_back(nodeBIndex);

  }

  else

  if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel)

  {

  mergeNodeSet(nodeSets[nodeAIndex], nodeSets[nodeBIndex]);//把B合并到A当中，B销毁

  for (int k = nodeBInSetLabel; k < (int)nodeSets.size()-1; k++)

  {

  nodeSets[k] = nodeSets[k + 1];

  }

  }

  else

  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;

  }

  }

  
  

  0 0