首页 > 代码库 > C++ 图的实现
C++ 图的实现
今天正式在博客园开通博客，特此将今天学习的内容记录一下，看一看博客园的博客效果。
图可以说是算法与数据结构中十分重要的一个部分，然而对于图的实现，还是有一点点繁琐，今天参考清华大学出版社《数据结构》一书进行了一些回顾，记录于此。
本文并不对基本概念进行过多探讨，而着眼于实现。基于对途中边集的存储有邻接矩阵以及邻接表两种主要形式。本文将着重实现三个类：Graph基类，包含大量的virtual函数以待在派生类中实现；Graph的派生类Graphmtx(邻接矩阵实现图的存储)、Graphlnk(邻接表实现图的存储)。并通过简单的test对以上实现加以测试。废话不多说，直接贴代码，代码中加了比较详细的注释说明。
- 基类Graph定义：
//FileName : Graph.h #pragma once #include<iostream> using namespace std; #define INF 100000 //表示正无穷 const int DefaultVertices = 30; template<class T,class E> class Graph { public: static const E maxWeight = INF; Graph(int size = DefaultVertices){}; ~Graph(){}; bool GraphEmpty()const //检查为空 { if (numEdges ==0 )return true; else return false; } bool GraphFull()const //检查为满 { if(numVertices==maxVertices ||numEdges==maxVertices*(maxVertices-1)/2) return true; else return false; } int NumberOfVertices(){return numVertices;} //返回当前顶点数 int NumberOfEdges(){return numEdges;} //返回当前边数 virtual T getValue(int i)=0; //取顶点i的值，i不合理返回0 virtual E getWeight(int v1,int v2)=0; //取边（v1，v2）的权值 virtual int getFirstNeighbor(int v)=0; //取顶点v的第一个邻接顶点 virtual int getNextNeighbor(int v,int w)=0; //取邻接顶点w的下一个邻接顶点 virtual bool insertVertex(const T& vertex)=0; //插入一个顶点vertex virtual bool insertEdge(int v1, int v2,E cost)=0;//插入边（v1,v2）,权值cost virtual bool removeVertex(int v)=0; //删除顶点v和所有与之关联的边 virtual bool removeEdge(int v1,int v2)=0; //删除边（v1,v2） protected: int maxVertices; int numEdges; int numVertices; virtual int getVertexPos(T vertex)=0; };
- 基于邻接表实现边集存储的派生子类Graphlnk定义及实现：
//Filename : Grapglnk.h #include "Graph.h" template<class T ,class E> struct Edge //边界点的定义 { int dest; //边的另一顶点位置 E cost; //权值 Edge<T ,E> *link;//下一条边链指针 Edge(){} //构造函数 Edge(int num , E weight):dest(num),cost(weight),link(NULL){} //构造函数 bool operator != (Edge<T,E> &R)const{ //判边不等否 return (dest!=R.dest)? true:false; } }; template<class T ,class E > struct Vertex{ //顶点的定义 T data; //顶点名字 Edge<T ,E> *adj; //边链表的头指针 }; template <class T ,class E> class Graphlnk: public Graph<T,E> { public: Graphlnk(int sz=DefaultVertices); ~Graphlnk(); T getValue(int i) { return (i>=0 && i<numVertices)? NodeTable[i].data : 0; } E getWeight(int v1,int v2); int getFirstNeighbor(int v); int getNextNeighbor(int v,int w); bool insertVertex(const T& vertex); bool insertEdge(int v1, int v2,E cost); bool removeVertex(int v); bool removeEdge(int v1,int v2); void inputGraph(); void outputGraph(); private: Vertex<T,E> * NodeTable; //顶点表 int getVertexPos(const T vertex){ for (int i = 0;i<numVertices;i++) if(NodeTable[i].data =http://www.mamicode.com/= Vertex) return i; return -1; //找不到就返回-1 } }; template <class T ,class E> Graphlnk<T,E>::Graphlnk(int sz) //构造函数 { maxVertices = sz; numVertices = 0; numEdges = 0; NodeTable = new Vertex<T,E>[maxVertices]; if(NodeTable ==NULL){ cerr<<"存储分配错！"<<endl;exit(1);} for (int i = 0;i<maxVertices;i++) { NodeTable[i].adj = NULL; } } template<class T ,class E> Graphlnk<T,E>::~Graphlnk() //析构函数 { for(int i = 0; i<maxVertices;i++) { Edge<T,E> *p = NodeTable[i].adj; while( p!= NULL) { NodeTable[i].adj = p->link; delete p ; p = NodeTable[i].adj; } } delete []NodeTable; } template <class T ,class E> E Graphlnk<T,E>::getWeight(int v1,int v2) //返回边（v1，v2）的权重，边不存在则返回0 { if(v1 != -1 && v2 !=-1) { Edge<T,E> *p = NodeTable[v1].adj; while(p!=NULL && p->dest!=v2) p = p->link; if(p!=NULL) return p->cost; } return 0; } template<class T,class E> int Graphlnk<T,E>::getFirstNeighbor(int v) //获得v的第一个邻接顶点，找不到则返回-1 { if(v>=0 && v<numVertices) { Edge<T,E> *p = NodeTable[v].adj; if(p!=NULL) return p->dest; } return -1; } template<class T ,class E> int Graphlnk<T,E>::getNextNeighbor(int v,int w) //获得v的邻接顶点w的下一个邻接顶点 { if(v1>=0 && v1<numVertices && v2>=0 && v2<numVertices) { Edge<T,E> *p = NodeTable[v1].adj; if(p!=NULL && p->dest != w) //寻找邻接顶点w p = p->link; if(p!=NULL && p->link!=NULL) //找到w且存在下一个邻接顶带你 return p->link->dest; } return -1： } template<class T ,class E> bool Graphlnk<T,E>::insertVertex(const T& vertex) //插入点 { if(numVertices == maxVertices) return false; //图已满，插入失败 NodeTable[numVertices++].data = http://www.mamicode.com/vertex; // return true; } template<class T ,class E> bool Graphlnk<T,E>::removeVertex(int v) //删除点 { if(numVertices ==1 || v<0 ||v>=numVertices) return false; Edge<T,E> *p ,*s ,*t; int i, k; while(NodeTable[v].adj != NULL) //删除该顶点，以及与之邻接的顶点中的记录 { p = NodeTable[v].adj; k = p->dest; s = NodeTable[k].adj; //以找对称存放的边节点 t = NULL; while (s!=NULL && s->dest!= v) //在对称点的邻接表里面找v，删除掉 { t = s; s = s->link; } if(s!=NULL) { if(t==null) //第一个邻接顶点就是v NodeTable[k].adj = s->link; else t->link = s->link; delete s; } NodeTable[v].adj = p->link; delete p; numEdges --; } numVertices--; NodeTable[v].data = NodeTable[numVertices].data; p = NodeTable[v].adj = NodeTable[numVertices].adj; while(p!=NULL) { s = NodeTable[p->dest].adj; while(s!=NULL) { if(s->dest == numVertices) { s->dest = v; break; } else s = s->link; } p = p->link } return true; } template<class T ,class E> bool Graphlnk<T,E>::insertEdge(int v1, int v2,E cost) //插入一条边,若边已存在，或参数不合理，返回false { if(v1>=0 && v1< numVertices && v2>=0 && v2< numVertices) { Edge<T,E> *q ,*p = NodeTable[v1].adj; //先检查该边是否已经存在 while(p!=NULL && p->dest!= v2) p = p->link; if(p!=NULL)//找到该边 { cout<<"该边已经存在，插入失败！"<<endl; return false; } p = new Edge<T,E>; q = new Edge<T,E>; p->dest = v2; p->cost = cost; p->link = NodeTable[v1].adj; NodeTable[v1].adj = p; //插入到邻接表表头 q->dest = v1; q->cost = cost; q->link = NodeTable[v2].adj; NodeTable[v2].adj = p; numEdges ++; return true; } return false; } template<class T, class E> bool Graphlnk<T,E>::removeEdge(int v1,int v2) { if(v1 >=0 && v1< numVertices && v2>=0 && v2< numVertices) { Edge<T,E> *p = NodeTable[v1].adj, *q = NULL ;*s = p; while(p!=NULL && p->dest!= v2) //先找该边 { q = p; p = p->link; } if(p!=NULL) //找到该边 { if(p==s)//第一个节点就找到 NodeTable[v1].adj = p->link; else q->link = p->link; delete p; } else return false; //找不到边 p = NodeTable[v2].adj; q= NULL; s = p; while(p!=NULL && p->dest!=v1) { q = p; p = p->link; } if(p==s) NodeTable[v2].adj = p->link; else q->link = p->link; delete p; return true; } return false; } template<class T ,class E> void Graphlnk<T,E>::inputGraph() { //通过从输入流对象in输入n的顶点和e条五项边的信息建立邻接矩阵表示的图G。邻接矩阵初始化工作在构造函数完成 int i,j,k,m,n; T e1,e2; E weight; cout<<"请输入顶点数和边数(空格隔开):"<<endl; cin >> n >> m; //输入点数n的边数m cout<<"请依次输入顶点:"<<endl; for(i=0;i<n;i++)//输入顶点，建立顶点表 { cin>>e1; this->insertVertex(e1); //G.insertVertex(e1); } cout<<"请依次输入边，形如 v1 v2 weight ："<<endl; i=0; while(i<m) { cin >> e1>>e2>>weight; j = this->getVertexPos(e1);//查顶点号 k = this->getVertexPos(e2); if(j==-1 || k==-1) { cout<<"边两端点信息有误，重新输入！"<<endl; } else { this->insertEdge(j,k,weight); i++; } } } template<class T ,class E> void Graphlnk<T,E>::outputGraph() { //输出图的所有顶点和边信息 int i,j,n,m; T e1,e2; E weight; n = this->NumberOfVertices(); //点数 m = this->NumberOfEdges(); //边数 cout<<"顶点数的边数为："; cout<<n<<","<<m<<endl; //输出点数和边数 cout<<"各边依次为："<<endl; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { weight = this->getWeight(i,j); if(weight>0 && weight< maxWeight) { e1 = this->getValue(i); e2 = this->getValue(j); cout<<"("<<e1<<","<<e2<<","<<weight<<")"<<endl; } } } }
- 基于邻接矩阵实现边集存储的派生子类Graphmtx定义及实现：
//Filename : Graphmtc.h #include "Graph.h" #include<iostream> using namespace std; template<class T,class E> class Graphmtx: public Graph<T,E> { //friend istream &operator>>(istream &in,Graphmtx<T,E> &G); //输入 //friend ostream &operator<<(ostream &out,Graphmtx<T,E> &G); //输出 public: Graphmtx(int sz=DefaultVertices); //构造 ~Graphmtx() //析构 { delete []VerticesList; delete []Edge; } T getValue(int i) //取顶点i的值，若i不合理返回NULL { if(i>=0 && i<numVertices) return VerticesList[i]; else return NULL; } E getWeight(int v1,int v2) //取边（v1,v2）的权值，不合理返回0 { if(v1!=-1 && v2!=-1) return Edge[v1][v2]; else return 0; } int getFirstNeighbor(int v); int getNextNeighbor(int v,int w); bool insertVertex(const T& vertex); bool insertEdge(int v1, int v2,E cost); bool removeVertex(int v); bool removeEdge(int v1,int v2); void inputGraph(); void outputGraph(); private: T *VerticesList; //顶点表 E * *Edge; //邻接矩阵 int getVertexPos(T vertex) //给出顶点在图中的位置 { for(int i=0;i<numVertices;i++) if(VerticesList[i]==vertex)return i; return -1; //找不到返回-1 } }; template<class T ,class E> Graphmtx<T,E>::Graphmtx(int sz) //构造函数 { maxVertices = sz; numVertices = 0; numEdges = 0; int i,j; VerticesList = new T[maxVertices]; Edge = new E *[maxVertices]; for (i=0;i<maxVertices;i++) Edge[i]= new E[maxVertices]; for(i=0;i<maxVertices;i++) for(j=0;j<maxVertices;j++) Edge[i][j] = (i==j) ? 0 :maxWeight; } template<class T,class E> int Graphmtx<T,E>::getFirstNeighbor(int v)//返回v的第一个邻接顶点的位置 { if(v!=-1) { for(int col =0;col<maxVertices;col++) if(Edge[v][col]>0 && Edge[v][col]<maxWeight) return col; } return -1; } template<class T,class E> int Graphmtx<T,E>::getNextNeighbor(int v,int w)//返回v的邻接顶点w的下一个邻接顶点 { if (v!=-1 && w!=-1) { for (int col =w+1;col<maxVertices;col++) { if(Edge[v][col]>0 &&Edge[v][col]<maxWeight) return col; } } return -1; } template<class T ,class E> bool Graphmtx<T,E>::insertVertex(const T& vertex) //插入一个顶点 { if(numVertices == maxVertices)return false; //顶点表已满，返回false VerticesList[numVertices++]=vertex; return true; } template<class T ,class E> bool Graphmtx<T,E>::insertEdge(int v1, int v2,E cost)//插入一条边 { if(v1>-1 && v1<numVertices && v2>-1 && v2<numVertices) //检查条件 { if( Edge[v1][v2]==maxWeight) { Edge[v1][v2]=Edge[v2][v1] = cost; numEdges++; return true; } else { cout<<"该边已存在，添加失败"<<endl; return false; } } else return false; } template<class T,class E> bool Graphmtx<T,E>::removeVertex(int v) //删除一个顶点 { if(v<0 ||v>numVertices) return false; //v不在图中 if(numVertices==1) return false; //只剩一个顶点，不删除 int i,j; VerticesList[v]=VerticesList[numVertices-1]; //顶点表中删除 for( i=0;i<numVertices;i++) //边数调整 if(Edge[i][v]>0 && Edge[i][v]<maxWeight) numEdges--; for(i=0;i<numVertices;i++) Edge[i][v]=Edge[i][numVertices-1]; numVertices--; //顶点数调整 for(j=0;j<numVertices;j--) Edge[v][j]=Edge[numVertices][j]; return true; } template<class T,class E> bool Graphmtx<T,E>::removeEdge(int v1,int v2) //删除边 { if(v1>-1 && v1<numVertices && v2>-1 &&v2<numVertices && Edge[v1][v2]>0 && Edge[v1][v2]<maxWeight) { Edge[v1][v2] = Edge[v1][v2] = maxWeight; numEdges--; return true; } else return false; }; template<class T ,class E> void Graphmtx<T,E>::inputGraph() { //通过从输入流对象in输入n的顶点和e条五项边的信息建立邻接矩阵表示的图G。邻接矩阵初始化工作在构造函数完成 int i,j,k,m,n; T e1,e2; E weight; cout<<"请输入顶点数和边数(空格隔开):"<<endl; cin >> n >> m; //输入点数n的边数m cout<<"请依次输入顶点:"<<endl; for(i=0;i<n;i++)//输入顶点，建立顶点表 { cin>>e1; this->insertVertex(e1); //G.insertVertex(e1); } cout<<"请依次输入边，形如 v1 v2 weight ："<<endl; i=0; while(i<m) { cin >> e1>>e2>>weight; j = this->getVertexPos(e1);//查顶点号 k = this->getVertexPos(e2); if(j==-1 || k==-1) { cout<<"边两端点信息有误，重新输入！"<<endl; } else { this->insertEdge(j,k,weight); i++; } } } template<class T ,class E> void Graphmtx<T,E>::outputGraph() { //输出图的所有顶点和边信息 int i,j,n,m; T e1,e2; E weight; n = this->NumberOfVertices(); //点数 m = this->NumberOfEdges(); //边数 cout<<"顶点数的边数为："; cout<<n<<","<<m<<endl; //输出点数和边数 cout<<"各边依次为："<<endl; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { weight = this->getWeight(i,j); if(weight>0 && weight< maxWeight) { e1 = this->getValue(i); e2 = this->getValue(j); cout<<"("<<e1<<","<<e2<<","<<weight<<")"<<endl; } } } }
- 编写测试程序加以简单测试：
//Filename： test.cpp #include "Graphmtx.h" void test_Graphmtx() { Graphmtx<char,int> g(30); g.inputGraph(); g.outputGraph(); system("pause"); } void test_Graphlnk() { Graphmtx<char,int> g(30); g.inputGraph(); g.outputGraph(); system("pause"); }
//Filename : main.cpp #include "Graphmtx.h" extern void test_Graphmtx(); extern void test_Graphlnk(); void main() { //test_Graphmtx(); test_Graphlnk(); }
经测试，以上代码可以正确运行。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。