-
生成树:n-1 n是顶点数查看全部
-
图的广度优先搜素就是一层一层的搜索查看全部
-
图的深度优先搜索相当与树的前序遍历,先访问根,在访问左孩子,在访问右孩子查看全部
-
最小边函数 int CMap::getMinEdge(vector<Edge>edgeVec) { int minWeight=0; int edgeIndex=0; int i=0; for(int i=0;i<edgeVec.size();i++) { if(!edgeVec[i].m_bSelected) { minWeight=edgeVec[i].m_iWeightValue; edgeIndex=i; break; } } if(minWeight==0) return -1; for(;i<edgeVec.size();i++) { if(!edgeVec[i].m_bSelected&&!m_pNodeArray[edgeVec[i].m_iNodeIndexB].m_bIsVisited)//注意不要有环路,B点不能访问过 { if(minWeight>edgeVec[i].m_iWeightValue) { minWeight=edgeVec[i].m_iWeightValue; edgeIndex=i; } } } return edgeIndex; }查看全部
-
Prime算法 void CMap::primTree(int nodeIndex) { int value=0; int edgeCount=0; vector<int>nodeVec; vector<Edge>edgeVec; cout<<m_pNodeArray[nodeIndex].m_cData<<endl; nodeVec.push_back(nodeIndex); m_pNodeArray[nodeIndex].m_bIsVisited=true;//“不要忘了” while(edgeCount<m_iCapacity-1) { int temp=nodeVec.back(); for(int i=0;i<m_iCapacity;i++) { getValueFromMatrix(temp,i,value); if(value!=0) { if(!m_pNodeArray[i].m_bIsVisited) { Edge edge(temp,i,value); edgeVec.push_back(edge); } } } int edgeIndex=getMinEdge(edgeVec); edgeVec[edgeIndex].m_bSelected=true; cout<<edgeVec[edgeIndex].m_iNodeIndexA<<"----"<<edgeVec[edgeIndex].m_iNodeIndexB<<" "; cout<<edgeVec[edgeIndex].m_iWeightValue<<endl; m_pEdge[edgeCount]=edgeVec[edgeIndex]; edgeCount++; int nextNodeIndex=edgeVec[edgeIndex].m_iNodeIndexB; nodeVec.push_back(nextNodeIndex); m_pNodeArray[nextNodeIndex].m_bIsVisited=true; cout<<m_pNodeArray[nextNodeIndex].m_cData<<endl; } }查看全部
-
,查看全部
-
克鲁斯卡尔(Kruskal)算法:把所有边都列举出来,选择权值最小的边,如果所选边与原来选择的边构成了闭环则舍弃该边,再在剩余的边中重复上面方法(只有所有点都涉及,并且点之间已经被边连接了,合并成同一个集合,此算法才算是结束)查看全部
-
普里姆(Prim)算法:找出一个点,列出这个点的所有边,加入待选边集合,在待选边集合中找最小的权值边,然后再根据所选边的另一个顶点重复上述步骤查看全部
-
//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<<"---" } }查看全部
-
bool DMap::IsInSets(vector<int> nodeSet,int target) { for(int i=0;i<nodeSet.size();i++) { if(nodeSet[i]=target) { return true; } } return false; } void DMap::mergeNodeSet(vector<int> &nodeSetA,vector<int> nodeSetB) { for(int i=0;i<nodeSetB.size();i++) { nodeSetA.push_back(nodeSetB[i]); } }查看全部
-
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=i+1;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++) {查看全部
-
/************************************************************************** //广度优先遍历 void DMap::breadFirstTravers(int nodeindex) { cout<<m_pNodeArray[nodeindex].m_cData<<" "; m_pNodeArray[nodeindex].m_bVisited=true; vector<int> curVect; curVect.push_back(nodeindex); breadFirstTraversImpl(curVect); } void DMap::breadFirstTraversImpl(vector <int> preVect) { int value=0; vector<int> curVect; for(int j=0;j<(int)preVect.size();j++) { for(int i=0;i<m_iCapacity;i++) { getValueFromMatrix(preVect[j],i,value) { if(value!=0) { if(m_pNodeArray[i].m_bVisited) { continue; } else { cout<<m_pNodeArray[i].m_cData<<" "; m_pNodeArray[i].m_bVisited=true; curVect.push_back(i); } } } } } if(curVect.size()==0) { return; } else { breadFirstTraversImpl(curVect); } } 1>------ 已启动生成: 项目: DATAGRSPH, 配置: Debug Win32 ------ 1 warning C4018: “<”: 有符号/无符号不匹配 ========== 生成: 成功 1 个,失败 0 个,最新 0 个,跳过 0 个 ==========查看全部
-
void DMap::ResetNode() { for(int i=0;i<m_iNodeCount;i++) { m_pNodeArray[i].m_bVisited=false; } } bool DMap::SetValuetoMatricForDGraph(int row,int col,int val=1) { if(row<0 || row>m_iCapacity) { return false; } if(col<0 || col>m_iCapacity) { return false; } m_pMatrix[row*m_iCapacity+col]=val; return true; } bool DMap::SetValuetoMatricForUGraph(int row,int col,int val=1) { if(row<0 || row>m_iCapacity) { return false; } if(col<0 || col>m_iCapacity) { return false; } m_pMatrix[row*m_iCapacity+col]=val; m_pMatrix[col*m_iCapacity+row]=val; return true; } bool DMap::getValueFromMatrix(int row,int col, int &val) { if(row<0 || row>m_iCapacity) { return false; } if(col<0 || col>m_iCapacity) { return false; } val=m_pMatrix[row*m_iCapacity+col]; return true; } void DMap::printMatrix() { for(int i=0;i<m_iCapacity;i++) { for(int j=0;j<m_iCapacity;j++) { cout<<m_pMatrix[i*m_iCapacity+j]<<" "; } cout<<endl; } }查看全部
-
顶点结构体:包括顶点索引和顶点数据就行 图的结构体:包括顶点数组(记录顶点)和邻接矩阵(记录边,并且顶点和边的关系)就行 邻接表与逆邻接表:相对于弧的出入顶点说的,如果存储的是弧出顶点的就是邻接表,如果存储的是弧进顶点就是逆邻接表查看全部
-
数据结构图
图遍历
最小生成树
地图,路径规划 ...
权重,加权
查看全部
举报
0/150
提交
取消