-
CMap.cpp4查看全部
-
main.cpp: #include <iostream> #include "CMap.h" int main() { CMap *pMap = new CMap(6); 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'); pMap->addNode(pNodeA); pMap->addNode(pNodeB); pMap->addNode(pNodeC); pMap->addNode(pNodeD); pMap->addNode(pNodeE); pMap->addNode(pNodeF); //设置邻接矩阵 pMap->setValueToMatrixForUndirectedGraph(0,1,6); pMap->setValueToMatrixForUndirectedGraph(0,4,5); pMap->setValueToMatrixForUndirectedGraph(0,5,1); pMap->setValueToMatrixForUndirectedGraph(1,2,3); pMap->setValueToMatrixForUndirectedGraph(1,5,2); pMap->setValueToMatrixForUndirectedGraph(2,5,8); pMap->setValueToMatrixForUndirectedGraph(2,3,7); pMap->setValueToMatrixForUndirectedGraph(3,5,4); pMap->setValueToMatrixForUndirectedGraph(3,4,2); pMap->setValueToMatrixForUndirectedGraph(4,5,9); pMap->primTree(0); // pMap->printMatrix(); // // cout<<endl; // // pMap->depthFirstTraverse(0); // cout<<endl; // //广度遍历之前，由于之前的点都被表示为已经访问过 // pMap->resetNode(); // pMap->breadthFirstTraverse(0); return 0; }CMap.h: #ifndef INC_0214_CMAP_H #define INC_0214_CMAP_H #include <vector> #include "Node.h" #include "Edge.h" using namespace std; class CMap{ public: CMap(int capacity); ~CMap(); bool addNode(Node *pNode); //向图中加入顶点（结点） void resetNode(); //重置顶点 bool setValueToMatrixForDirectedGraph(int row,int col,int val = 1); //为有向图设置邻接矩阵 bool setValueToMatrixForUndirectedGraph(int row,int col,int val = 1); //为无向图设置邻接矩阵 void printMatrix(); //打印邻接矩阵 void depthFirstTraverse(int nodeIndex); //深度优先遍历 void breadthFirstTraverse(int nodeIndex); //广度优先遍历 void primTree(int nodeIndex);//Prim生成树 private: bool getValueFromMatrix(int row,int col,int &val); //从矩阵中获取权值 void breadthFirstTraverseImp(vector<int> preVec); //广度优先遍历实现函数 int getMinEdge(vector<Edge> edgeVec);//找最小边函数 private: int m_iCapacity; //图中最多可以容纳的顶点数 int m_iNodeCount; //已经添加的顶点（结点）个数 Node *m_pNodeArray; //用来指向一段内存，这段内存用来存放顶点数组 int *m_pMatrix; //用来存放邻接矩阵 Edge *m_pEdge;//用于保存最小边，需要在cpp文件中申请一段内存 }; #endif //INC_0214_CMAP_HCMap.cpp: #include "CMap.h" #include "Node.h" #include <iostream> #include <vector> using namespace std; CMap::CMap(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));//需要初始化将这个矩阵的各元素初始化为0； //也可以用for循环进行初始化：但是注意m_pMatrix是一个一维数组 // for(int i = 0;i < m_pMatrix*m_pMatrix;i++){ // m_pMatrix[i] = 0; // } //存放最小边的空间大小 m_pEdge = new Edge[m_iCapacity - 1]; } CMap::~CMap() {//针对析构函数中申请的内存进行释放 delete []m_pNodeArray; delete []m_pMatrix; } bool CMap::addNode(Node *pNode) { //向图中加入顶点（结点） if(pNode == NULL){ return NULL; } m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;//内存在构造函数时就已经申请好了，只需要付值了 m_iNodeCount++; return true; } void CMap::resetNode() { //重置顶点 for(int i = 0;i < m_iNodeCount;i++){ m_pNodeArray[i].m_bIsVisited = false; } } bool CMap::setValueToMatrixForDirectedGraph(int row,int col,int val) { //为有向图设置邻接矩阵,函数声明时是int val = 1，但是定义时不加=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 CMap::setValueToMatrixForUndirectedGraph(int row,int col,int val) { //为无向图设置邻接矩阵 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; } void CMap::printMatrix(){ for(int i = 0;i < m_iCapacity;i++){ for(int k = 0; k < m_iCapacity;k++){ cout << m_pMatrix[i*m_iCapacity+k] << " "; } cout << endl; } } bool CMap::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 CMap::depthFirstTraverse(int nodeIndex){//需要用深度优先遍历实现 int value = 0; cout << m_pNodeArray[nodeIndex].m_cData << " "; m_pNodeArray[nodeIndex].m_bIsVisited = true; for(int i = 0; i < m_iCapacity;i++){ getValueFromMatrix(nodeIndex,i,value);//注意引用的写法 if(value == 1){ if(m_pNodeArray[i].m_bIsVisited){ continue; } else{ depthFirstTraverse(i); } } else{ continue; } } } void CMap::breadthFirstTraverse(int nodeIndex){ cout << m_pNodeArray[nodeIndex].m_cData << " "; m_pNodeArray[nodeIndex].m_bIsVisited = true; //需要用数组来保存被访问过的结点的索引，这里使用vector,标准模板库需要将头文件加入 vector<int> curVec; curVec.push_back(nodeIndex); breadthFirstTraverseImp(curVec); } void CMap::breadthFirstTraverseImp(vector<int> preVec){ int value = 0;//用于去邻接矩阵取值，看是否为0 vector<int> curVec;//用来保存当前这一层的所有节点 for(int j = 0;j < (int)preVec.size();j++){ for(int i = 0; i < m_iCapacity;i++){ getValueFromMatrix(preVec[j],i,value); if(value != 0){//如果边存在，还要看对应顶点被访问过没 if(m_pNodeArray[i].m_bIsVisited){ continue; } else{//如果存在且没又被访问过 cout << m_pNodeArray[i].m_cData<<" "; m_pNodeArray[i].m_bIsVisited = true; curVec.push_back(i); } } } } //还需要判断这一层是否为空，为空则不必向下进行遍历 if(curVec.size() == 0){ return; } else{ breadthFirstTraverseImp(curVec); } } void CMap::primTree(int nodeIndex) {//Prim生成树 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) {//看点被访问过没，而不是边 continue; } else{ //若这条边还没有被访问过，放进数组 Edge edge(temp,i,value);//用构造函数实例化一个边的对象 edgeVec.push_back(edge); } } } //此时与temp连接的边都放入了备选边中，不会重复放入同一条边 //从可选边集合中找出最小的边，连着这条边的另一个顶点就放入点的集合中 //从可选边集合中找出最小的边函数： int edgeIndex = getMinEdge(edgeVec); edgeVec[edgeIndex].m_bSelected = true;//把选中的边置为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);//放入点时需要将访问置为true m_pNodeArray[nextNodeIndex].m_bIsVisited = true; //打印下一个点 cout<<m_pNodeArray[nextNodeIndex].m_cData << endl; } } int CMap::getMinEdge(vector<Edge> edgeVec){ int minWeight = 0; int edgeIndex = 0; int i = 0; for(; i < edgeVec.size();i++){ if(!edgeVec[i].m_bSelected){//先看selected是不是为假 minWeight = edgeVec[i].m_iWeightValue; //还需要记录最小边的索引 edgeIndex = i; break;//找到第一个点之后就要跳出循环 } } if(minWeight == 0){//找最小边失败，返回-1 return -1; } for(;i < edgeVec.size();i++){ if(edgeVec[i].m_bSelected){//若为true continue; } else{ if(minWeight > edgeVec[i].m_iWeightValue){ minWeight = edgeVec[i].m_iWeightValue; edgeIndex = i; } } } return edgeIndex; }Node.h: #ifndef INC_0214_NODE_H #define INC_0214_NODE_H class Node{ public: Node(char data =0); char m_cData; bool m_bIsVisited;//访问过了是true }; #endif //INC_0214_NODE_HNode.cpp: #include "Node.h" Node::Node(char data) { m_cData = data; m_bIsVisited = false; }Edge.h: #ifndef INC_0214_EDGE_H #define INC_0214_EDGE_H class Edge{ public: Edge(int nodeIndexA = 0,int nodeIndexB = 0,int weightValue = 0); int m_iNodeIndexA; int m_iNodeIndexB; int m_iWeightValue; bool m_bSelected; }; #endif //INC_0214_EDGE_HEdge.cpp: #include "Edge.h" Edge::Edge(int nodeIndexA,int nodeIndexB,int weightValue){ m_iNodeIndexA = nodeIndexA; m_iNodeIndexB = nodeIndexB; m_iWeightValue = weightValue; m_bSelected = false;//false为未访问过 }查看全部 -
//CMap.h #include <vector> using namespace std; #include "Node.h" class CMap{ public: CMap(int capacity);//向图中加入顶点 ~CMap(); bool addNode(Node* pNode);//重置顶点 void resetNode(); bool setValueToMatrixForDirecteGraph(int row,int col,int val = 1); //为有向图设置邻接矩阵 bool setValueToMatrixForUndirecteGraph(int row,int col,int val = 1);//为无向图设置邻接矩阵 void printMatrix();//打印邻接矩阵 void depthFirstTraverse(int nodeIndex);//深度优先遍历 void breadthFirstTraverse(int nodeIndex);// 广度优先遍历 private: bool getValueFromMatrix(int row,int ol,int &val);//从矩阵中获取权值 void breadthFirtTraverseImp(vector<int> preVec);//广度优先遍历实现函数 private: int m_iCapacity; //图中最多可以容纳的顶点数 int m_iNodeCount; //已经添加的顶点个数 Node *m_pNodeArray; //存放顶点数组 int *m_pMatrix; //存放邻接矩阵 }; #endif查看全部 -
CMap.cpp3查看全部
-
CMap.cpp2查看全部
-
CMap.cpp1查看全部
-
CMap.h查看全部
-
Node.cpp查看全部
-
Node.h查看全部
-
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; } } }查看全部
-
/**************************************************************/ 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; } }查看全部
-
#ifndef DMAP_H #define DMAP_H #include <vector> #include "Node.h" using namespace std; class DMap { public: DMap(int capacity); ~DMap(void); bool AddNode(Node* pNode);//向图中增加结点（顶点） void ResetNode(); //重置顶点 bool SetValuetoMatricForDGraph(int row,int col,int val=1);//有向图设置 bool SetValuetoMatricForUGraph(int row,int col,int val=1);//无向图设置 void printMatrix();//打印邻接矩阵 void depthFirstTravers(int nodeindex);//深度优先遍历 void breadFirstTravers(int nodeindex);//广度优先遍历 private: bool getValueFromMatrix(int row,int col, int &val);//从矩阵获取权值 void breadFirstrTraversImpl(vector <int> prevect);//广度优先遍历实现 private: int m_iCapacity; //图中顶点数容量 int m_iNodeCount; //已添加顶点个数 Node* m_pNodeArray; //存放顶点数组 int* m_pMatrix; //存放邻接矩阵 }; #endif查看全部
-
图的存储结构：邻接矩阵，邻接表，十字链表，邻接多重表查看全部
-
prim算法是：假设从顶点A开始， 先选距离A最近的顶点（比如F），然后把把F点放入已涉及顶点集合当中，A-F边放入已选边的集合中。之后将A和F看作一个整体，再去找理这个整体最近的点和边。
kruskal算法是：先把所有的边找到，每一次都去找所有边中最短的那一条。不断的把顶点连接起来，直到所有的顶点都放入顶点集合中 并且通过边形成同一个集合为止。
2种算法都要在选边的过程中不断判断选择的边是否会和已有边形成闭环，如果形成闭环就要舍弃
查看全部 -
//CMap.cpp #include "CMap.h" #include <iostream> #include <vector> using namespace std; CMap::CMap(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));/初始化邻接矩阵 } bool CMap::addNode(Node* pNode) { m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData; m_iNodeCount++； return true; } void CMap::resetNode() { for(int i = 0;i < m_iNodeCount,i++) { m_pNodeArray[i].m_blsVisited = false; } } //为边设置权值 bool CMap::setValueToMatrixForDirectedGraph(int row,int col,int val) { m_pMatrix[row*m_iCapacity+col] = val; return true; } bool CMap::setValueToMatrixForUndirectedGraph(int row,int col,int val) {//无向图的邻接矩阵是对称的 m_pMatrix[row*m_iCapacity+col] = val; m_pMatrix[col*m_iCapacity+row] = val; return true; } //根据权值判断两个顶点是否相连 bool CMap::getValueFromMatrix(int row,int col,int& val) { val = m_pMatrix[row*m_iCapacity+col]; return true; } void CMap::printMatrix() { for(int i = 0;i < m_iCapacity;i++) { for(int j = 0;j < m_iCapacity;j++) { cout << p_Matrix[i*mCapacity+k] << " "; } cout << endl; } } //深度优先搜索 void CMap::depthFirstTraverse(int nodeIndex) { int value = 0; cout << m_pNodeArray[nodeIndex].m_cData << " "; m_pNodeArray[nodeIndex].m_blsVisited = true; //通过邻接矩阵判断是否与其他的顶点是否有连接 for(int i = 0;i < m_iCapacity;i++) { getValFromMatrix(nodeIndex,i,value); if(value != 0) { if(pNodeArray[i].m_blsVisited) { continue; } else{ depthFirstTraverse(i); } } } } CMap::~CMap() { delete []m_pNodeArray; delete []m_pMatrix; }查看全部
举报
0/150
提交
取消