C++实现图的存储、Prim和Kruskal算法

#include "CMap.h" #include "Node.h" #include "Edge.h" #include <cstring> #include <iostream> using namespace std; CMap::CMap(int campacity){ m_iCampacity = campacity; m_iNodeCount = 0; m_pNodeArray = new Node[campacity]; m_pMatrix = new int[m_iCampacity * m_iCampacity]; memset(m_pMatrix,0,m_iCampacity * m_iCampacity * sizeof(int)); m_pEdgeArray = new Edge[m_iCampacity - 1]; } CMap::~CMap(){ delete[] m_pNodeArray; delete[] m_pMatrix; delete[] m_pEdgeArray; } bool CMap::addNode(Node *pNode){ if(pNode == NULL) return false; m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData; m_iNodeCount++; return true; } void CMap::resetNode(){ for(int i = 0;i < m_iCampacity;i++){ m_pNodeArray[i].m_bIsVisited = false; } } /** 带有默认参数的构造函数只需在声明时指定默认参数值，定义则不必指明默认参数的值 **/ bool CMap::setValueToMatrixForDirectedGraph(int row,int col,int val){ if(row < 0 || row >= m_iCampacity || col < 0 || col >= m_iCampacity) return false; m_pMatrix[row * m_iCampacity + col] = val; return true; } bool CMap::setValueToMatrixForUndirectedGraph(int row,int col,int val){ if(row < 0 || row >= m_iCampacity || col < 0 || col >= m_iCampacity) return false; m_pMatrix[row * m_iCampacity + col] = val; m_pMatrix[col * m_iCampacity + row] = val; return true; } void CMap::printMatrix(){ for(int i = 0; i < m_iCampacity;i++){ for(int j = 0; j < m_iCampacity;j++){ cout<<m_pMatrix[i * m_iCampacity + j]<<"\t"; } cout<<endl; } } bool CMap::getValueFromMatrix(int row,int col,int &val){ if(row < 0 || row >= m_iCampacity || col < 0 || col >= m_iCampacity) return false; val = m_pMatrix[row * m_iCampacity + col]; return true; } void CMap::depthFirstTraverse(int nodeindex){ cout<<m_pNodeArray[nodeindex].m_cData<<" "; m_pNodeArray[nodeindex].m_bIsVisited = true; int value = 0; for(int i = 0;i < m_iCampacity;i++){ //value = m_pNodeArray[nodeindex + 1].c_Data; getValueFromMatrix(nodeindex,i,value); if(value == 1){ if(m_pNodeArray[i].m_bIsVisited){ continue; }else{ depthFirstTraverse(i); } }else{ continue; } } } void CMap::breadFirstTraverse(int nodeindex){ if(nodeindex < 0 || nodeindex >= m_iCampacity) return; cout<<m_pNodeArray[nodeindex].m_cData<<" "; m_pNodeArray[nodeindex].m_bIsVisited = true; vector<int> curVec; curVec.push_back(nodeindex); breadFirstTraverseImp(curVec); //传递容器参数直接传递即可 } void CMap::breadFirstTraverseImp(vector<int> preVec){ int value; vector<int> curVec; for(int i = 0;i < (int)preVec.size();i++){ for(int j = 0;j < m_iCampacity;j++){ getValueFromMatrix(preVec[i],j,value); if(value !=0){ if(m_pNodeArray[j].m_bIsVisited){ continue; }else{ cout<<m_pNodeArray[j].m_cData<<" "; m_pNodeArray[j].m_bIsVisited = true; curVec.push_back(j); } }else{ continue; } } } if(curVec.size() > 0){ breadFirstTraverseImp(curVec); } } /**最小生成树 Prim算法相关函数**/ void CMap::primTree(int nodeindex){ int value; vector<int> nodeVec; //选中点的集合 vector<Edge> edgeVec; //备选边的集合 int edgeCount = 0; nodeVec.push_back(nodeindex); m_pNodeArray[nodeindex].m_bIsVisited = true; cout<<m_pNodeArray[nodeindex].m_cData<<endl; while(edgeCount < m_iCampacity - 1){ int temp = nodeVec.back(); for(int i = 0;i < m_iCampacity;i++){ getValueFromMatrix(temp,i,value); if(value != 0){ if(m_pNodeArray[i].m_bIsVisited){ continue; }else{ Edge edge(temp,i,value); //什么时候用new，什么时候不用new，这里为什么不用 edgeVec.push_back(edge); } }else{ continue; } } //int len = edgeVec.size(); //从可选边集合中选出最小边 int edgeIndex = getMinEdge(edgeVec); edgeVec[edgeIndex].m_bSelected = true; cout<<edgeVec[edgeIndex].m_iNodeA<<"----"<<edgeVec[edgeIndex].m_iNodeB; cout<<" weight:"<<edgeVec[edgeIndex].m_iWeightValue<<endl; //cout<<edgeVec[edgeIndex].m_iWeightValue<<endl; m_pEdgeArray[edgeCount] = edgeVec[edgeIndex]; edgeCount++; int nextNodeIndex = edgeVec[edgeIndex].m_iNodeB; nodeVec.push_back(nextNodeIndex); m_pNodeArray[nextNodeIndex].m_bIsVisited = true; cout<<m_pNodeArray[nextNodeIndex].m_cData<<endl; } } int CMap::getMinEdge(vector<Edge> edgeVec){ int edgeIndex = 0; int minWeight = 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; for(;i < (int)edgeVec.size();i++){ if(edgeVec[i].m_bSelected){ continue; }else{ if(edgeVec[i].m_iWeightValue < minWeight){ minWeight = edgeVec[i].m_iWeightValue; edgeIndex = i; } } } return edgeIndex; } //最小生成树 kluskal算法 void CMap::kluskalTree(){ int value = 0; int edgeCount = 0; //定义存放节点集合的数组 vector< vector<int> > nodeSets;//点集合的集合 vector<Edge> edgeVec; //第一步：取出所有边 for(int i = 0;i < m_iCampacity;i++){ //轮训矩阵上三角 for(int j = i+1;j < m_iCampacity;j++){ getValueFromMatrix(i,j,value); if(value != 0){ Edge edge(i,j,value); edgeVec.push_back(edge); } } } //第二步：从所有边中取出组成最小生成树的边 //1、找到算法的结束条件 while(edgeCount < m_iCampacity - 1){ //2、从边集合中找到最小边 int minEdgeIndex = getMinEdge(edgeVec); edgeVec[minEdgeIndex].m_bSelected = true; //3、找出最小边连接的点 int nodeAIndex = edgeVec[minEdgeIndex].m_iNodeA; int nodeBIndex = edgeVec[minEdgeIndex].m_iNodeB; //4、找出点所在的集合 bool isAInSet = false; bool isBInSet = false; int nodeAInSetLabel = -1; int nodeBInSetLabel = -1; for(int i = 0;i < (int)nodeSets.size();i++){ isAInSet = isInSet(nodeSets[i],nodeAIndex); if(isAInSet){ nodeAInSetLabel = i; } } for(int i = 0;i < (int)nodeSets.size();i++){ isBInSet = isInSet(nodeSets[i],nodeBIndex); if(isBInSet){ nodeBInSetLabel = i; } } //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){ 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 i = nodeBInSetLabel;i < (int)nodeSets.size()-1;i++){ nodeSets[i] = nodeSe