-
十字链表查看全部
-
邻接表查看全部
-
邻接矩阵查看全部
-
图的存储结构： 邻接矩阵 －数组 邻接表 十字链表 －链表形式，主要有向图 邻接多重表 － 链表形式，无向图查看全部
-
//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<<"---" } }查看全部
-
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++)查看全部
-
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++) {查看全部
-
那个地方出错了，慢慢查 i 6 int nextNodeIndex 2 int edgeIndex 6 int temp 2 int + this 0x00395d40 {m_iCapacity=6 m_iNodeCount=6 m_pNodeArray=0x00395d90 ...} DMap * const nodeIndex 0 int + nodeVect [5](0,5,0,1,2) std::vector<int,std::allocator<int> > edgeCount 4 int + edgeVect [12]({m_iNodeIndexA=0 m_iNodeIndexB=1 m_iWeightValue=6 ...},{m_iNodeIndexA=0 m_iNodeIndexB=4 m_iWeightValue=5 ...},{m_iNodeIndexA=0 m_iNodeIndexB=5 m_iWeightValue=1 ...},{m_iNodeIndexA=5 m_iNodeIndexB=0 m_iWeightValue=1 ...},{m_iNodeIndexA=5 m_iNodeIndexB=1 m_iWeightValue=2 ...},{m_iNodeIndexA=5 m_iNodeIndexB=2 m_iWeightValue=8 ...},{m_iNodeIndexA=5 m_iNodeIndexB=3 m_iWeightValue=4 ...},{m_iNodeIndexA=5 m_iNodeIndexB=4 m_iWeightValue=9 ...},{m_iNodeIndexA=0 m_iNodeIndexB=1 m_iWeightValue=6 ...},{m_iNodeIndexA=0 m_iNodeIndexB=4 m_iWeightValue=5 ...},{m_iNodeIndexA=1 m_iNodeIndexB=2 m_iWeightValue=3 ...},{m_iNodeIndexA=2 m_iNodeIndexB=3 m_iWeightValue=7 ...}) std::vector<Edge,std::allocator<Edge> > value 8 int查看全部
-
void DMap::primTree(int nodeIndex) { int value=0; int edgeCount=0; vector<int>nodeVect; vector<Edge> edgeVect; edgeVect.push_back(nodeIndex); cout<<m_pNodeArray[nodeIndex].m_cData<<endl; while(edgeCount < m_iCapacity-1) { int temp=nodeVect.back(); for(int i=0;i<m_iCapacity;i++) { getValueFromMatrix(temp,i,value); if(value!=0) { if(m_pNodeArray[temp].m_bVisited) { continue; } else { Edge edge(temp,i,value); edgeVect.push_back(edge); } } } int edgeIndex=getMinEdge(edgeVect); edgeVect[edgeIndex].m_bSelected=true; cout<<edgeVect[edgeIndex].m_iNodeIndexA<<"-------"<<edgeVect[edgeIndex].m_iNodeIndexA<<" "; cout<<edgeVect[edgeIndex].m_iWeightValue<<endl; m_pEdge[edgeCount]=edgeVect[edgeIndex]; edgeCount++; int nextNodeindex=edgeVect[edgeIndex].m_iNodeIndexB; nodeVect.push_back (nextNodeindex); m_pNodeArray[nextNodeindex].m_bVisited=true; cout<<m_pNodeArray[nextNodeindex].m_cData<<endl; } }查看全部
-
#include "stdafx.h" #include <stdlib.h> #include <iostream> #include <vector> #include "DMap.h" using namespace std; int _tmain(int argc, _TCHAR* argv[]) { DMap* pMap=new DMap(8); Node* pNodeA=new Node('A'); Node* pNodeB=new Node('B'); Node* pNodeC=new Node('C'); Node* pNodeD=new Node('D'); Node* pNodeE=new Node('E'); Node* pNodeF=new Node('F'); Node* pNodeG=new Node('G'); Node* pNodeH=new Node('H'); pMap->AddNode(pNodeA); pMap->AddNode(pNodeB); pMap->AddNode(pNodeC); pMap->AddNode(pNodeD); pMap->AddNode(pNodeE); pMap->AddNode(pNodeF); pMap->AddNode(pNodeG); pMap->AddNode(pNodeH); pMap->SetValuetoMatricForUGraph(0,1); pMap->SetValuetoMatricForUGraph(0,3); pMap->SetValuetoMatricForUGraph(1,2); pMap->SetValuetoMatricForUGraph(1,5); pMap->SetValuetoMatricForUGraph(3,6); pMap->SetValuetoMatricForUGraph(3,7); pMap->SetValuetoMatricForUGraph(6,7); pMap->SetValuetoMatricForUGraph(2,4); pMap->SetValuetoMatricForUGraph(4,5); pMap->printMatrix();查看全部
-
/************************************************************************** //广度优先遍历 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::depthFirstTravers(int nodeindex) { cout<<m_pNodeArray[nodeindex].m_cData<<" "; m_pNodeArray[nodeindex].m_bVisited=true; for(int i=0;i<m_iCapacity;i++) { getValueFromMatrix(nodeindex,i,value); if(value==1) { if(m_pNodeArray[i].m_bVisited) { continue; } else { depthFirstTravers(i); } } else { continue; } } }查看全部
-
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; } }查看全部
-
/**************************************************************/ DMap::DMap(int capacity) { m_iCapacity=capacity; m_iNodeCount=0; m_pNodeArray=new Node[m_iCapacity]; m_pMatrix=new int [m_iCapacity*m_iCapacity]; //memset(m_pMatrix,0,m_iCapacity*m_iCapacity*sizeof(int)); for(int i=0;i<m_iCapacity*m_iCapacity*sizeof(int);i++) { m_pMatrix[i]=0; } } DMap::~DMap(void) { delete []m_pNodeArray; delete []m_pMatrix; } bool DMap::AddNode(Node* pNode) { if(pNode==NULL) { return false; } m_pNodeArray[m_iNodeCount]->m_cData=pNode->m_cData; m_iNodeCount++; return true; } void DMap::ResetNode() { for(int i=0;i<m_iNodeCount;i++) { m_pNodeArray[i].m_bVisited=false; } }查看全部
举报
0/150
提交
取消