-
- 精慕门4947531 2016-11-11
- //5.根据点在集合的不同作不同处理 if(nodeAInSetLabel==-1 && nodeAInSetLabel==-1) { vector<int> vec; vec.push_back(nodeAIndex); vec.push_back(nodeBIndex); nodeSets.push_back(vec); } else if(nodeAInSetLabel==-1 && nodeBInSetLabel!=-1) { nodeSets[nodeBInSetLabel].push_back(nodeAIndex); } else if(nodeAInSetLabel!=-1 && nodeBInSetLabel==-1) { nodeSets[nodeAInSetLabel].push_back(nodeBIndex); } else 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]; } } //同一集合中，形成环路 else if(nodeAInSetLabel!=-1 && nodeBInSetLabel!=-1 && nodeAInSetLabel==nodeBInSetLabel) { continue; } m_pEdge[edgeCount]=edgeVect[minEdgeIndex]; edgeCount++; cout<<edgeVect[minEdgeIndex].m_iNodeIndexA<<"---" } }
- 1赞 · 1采集
-
- 精慕门4947531 2016-11-11
- void DMap::kruskalTree() { int value=0; int edgeCount=0; //定义存放结点集合的数组 vector<vector<int>> nodeSets; //第一步取出所有边 vector<Edge>edgeVect; for(int i=0;i<m_iCapacity;i++) { for(int k=0;k<m_iCapacity;k++) { getValueFromMatrix(i,k,value); if(value!=0) { Edge edge(i,k,value); edgeVect.push_back(edge); } } } //第二步从所有边取出组成最小生成树的边 //1.找出算法的终结条件 while(edgeCount<m_iCapacity-1) { //2.从边集合找到最小边 int minEdgeIndex=getMinEdge(edgeVect); edgeVect[minEdgeIndex].m_bSelected=true; //3.找到最小边连接的点 int nodeAIndex=edgeVect[minEdgeIndex].m_iNodeIndexA; int nodeBIndex=edgeVect[minEdgeIndex].m_iNodeIndexB; bool nodeAIsInSets=false; bool nodeBIsInSets=false; int nodeAInSetLabel=-1; int nodeBInSetLabel=-1; //4.找到点所在的点集合 for(int i=0;i<(int)nodeSets.size();i++) { nodeAIsInSets=IsInSets(nodeSets[i],nodeAIndex); if(nodeAIsInSets) { nodeAInSetLabel=i; } } for(int i=0;i<(int)nodeSets.size();i++)
- 0赞 · 0采集
-
- Swordsemperor 2016-10-13
- bool Cmap::isInSet(int node, vector<int> nodeVec) { for (int i = 0; i < nodeVec.size(); i++) { if (node == nodeVec[i])return true; } return false; } void Cmap::combineNodeSet(vector<int> set1, vector<int> set2) { for (int i = 0; i < set2.size(); i++) { set1.push_back(set2[i]); } }
- 0赞 · 0采集
-
- Swordsemperor 2016-10-13
- if (labelA == -1 && labelB == -1) { vector<int> tempNodeVec; tempNodeVec.push_back(edgeVec[miniIndex].nodeA); tempNodeVec.push_back(edgeVec[miniIndex].nodeB); nodeSets.push_back(tempNodeVec); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA == -1 && labelB != -1) { nodeSets[labelB].push_back(indexNodeA); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA != -1 && labelB == -1) { nodeSets[labelA].push_back(indexNodeB); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA != -1 && labelB != -1 && labelA != labelB) { combineNodeSet(nodeSets[labelA], nodeSets[labelB]); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA != -1 && labelB != -1 && labelA == labelB) { continue; } cout << indexNodeA << "----" << indexNodeB; cout << " " << edgeVec[miniIndex].value << endl; } }
- 0赞 · 0采集
-
- Swordsemperor 2016-10-13
- while (edgeCount < campacity - 1) { int miniIndex = getMiniEdge(edgeVec); edgeVec[miniIndex].visited = true; int indexNodeA = edgeVec[miniIndex].nodeA; int indexNodeB = edgeVec[miniIndex].nodeB; int labelA = -1; int labelB = -1; for (int i = 0; i < nodeSets.size(); i++) { if (isInSet(indexNodeA, nodeSets[i])){ labelA = i; } if (isInSet(indexNodeB, nodeSets[i])){ labelB = i; } }
- 0赞 · 0采集
-
- Swordsemperor 2016-10-13
- void Cmap::kruskalTree(int index) { vector<edge> edgeVec; vector<vector<int>> nodeSets; int edgeCount = 0; vector<edge> edgeMini; for (int i = 0; i < campacity; i++) { for (int j = 0; j < campacity; j++) { int tempVal; getValue(i, j, tempVal); if (tempVal != 0) { edge tempEdge(i, j, tempVal); edgeVec.push_back(tempEdge); } } }
- 0赞 · 0采集
数据加载中...