当前位置:  首页  >  PHP资讯  >  业界资讯

C++实现图的邻接矩阵表示

这篇文章主要为大家详细介绍了C++实现图的邻接矩阵表示,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

本文实例为大家分享了C++实现图的邻接矩阵表示代码,供大家参考,具体内容如下

1.遇到的问题:教材中写着子类Graphmtx(我用GrapMatrix)继承基类Graph

但是我在子类GraphMatrix中使用父类Graph的保护成员属性:maxVertices 显示没有声明(如下图)。

原来,c++中声明一个模板类及子类,在子类中如果需要访问父类的protected变量,需要使用父类的类作用域限定符,否则会报“identifier not found”错误。如果不是模板类,可以直接访问。

例如:要如下这样使用父类的保护成员属性,太麻烦了。

所以,我就不用继承基类的方法了。直接把Graph父类的保护成员属性放到GrapMatrix类中。

2.实现程序:

(1)GraphMatrix.h  

 #ifndef GraphMatrix_h #define GraphMatrix_h #include  using namespace std; const int DefaultVertices = 30; // 默认最大顶点数 template  class GraphMatrix { public: const E maxWeight = 100000; // 代表无穷大的值(=∞) GraphMatrix(int sz=DefaultVertices); // 构造函数 ~GraphMatrix(); // 析构函数 void inputGraph(); // 创建基于邻接矩阵的图 void outputGraph(); // 输出图的所有顶点和边信息 T getValue(int i); // 取顶点i的值,i不合理返回0 E getWeight(int v1, int v2); // 取边(v1, v2)上的权值 int getFirstNeighbor(int v); // 取顶点v的第一个邻接顶点 int getNextNeighbor(int v, int w); // 取v的邻接顶点w的下一个邻接顶点 bool insertVertex(const T& vertex); // 插入顶点vertice bool insertEdge(int v1, int v2, E cost); // 插入边(v1, v2)权值为cost bool removeVertex(int v); // 删去顶点v和所有与它相关联的边 bool removeEdge(int v1, int v2); // 在图中删去边(v1, v2) int getVertexPos(T vertex); // 给出顶点vertice在图中的位置 private: int maxVertices; // 图中最大的顶点数 int numEdges; // 当前边数 int numVertices; // 当前顶点数 T *VerticesList; // 顶点表 E **Edge; // 邻接矩阵 }; // 构造函数 template  GraphMatrix::GraphMatrix(int sz) { int i, j; maxVertices = sz; numVertices = 0; numEdges = 0; VerticesList = new T[maxVertices]; // 创建顶点表数组 Edge = new E*[maxVertices]; // 创建邻接矩阵数组 for(i = 0; i  GraphMatrix::~GraphMatrix() { delete []VerticesList; // 释放动态分配的空间 delete []Edge; } // 创建基于邻接矩阵的图 template  void GraphMatrix::inputGraph() { int i, j, k; int n, m; // 要输入的顶点数和边数 T e1, e2; // 边的两端顶点 E weight; // 边对应的权值 cout <<"请输入顶点数和边数:" <> n >> m; cout <<"请输入顶点:" <> e1; insertVertex(e1); // 插入 } cout <<"请输入边的两端顶点和权值:" <> e1 >> e2 >> weight; // 输入端点信息 j = getVertexPos(e1); // 查顶点号 k = getVertexPos(e2); if(j == -1 || k == -1) cout <<"边两端点信息有误,重新输入!" < void GraphMatrix::outputGraph() { int i, j, n, m; T e1, e2; E w; n = numVertices; m = numEdges; cout <<"顶点数为:" < 0 && w  int GraphMatrix::getVertexPos(T vertex) { for(int i = 0; i  T GraphMatrix::getValue(int i) { if(i >= 0 && i  E GraphMatrix::getWeight(int v1, int v2) { if(v1 != -1 && v2 != -1) // 存在这两个顶点 return Edge[v1][v2]; return 0; } // 取顶点v的第一个邻接顶点 template  int GraphMatrix::getFirstNeighbor(int v) { if(v != -1) { for(int col = 0; col  0 && Edge[v][col]  int GraphMatrix::getNextNeighbor(int v, int w) { if(v != -1 && w != -1) { for(int col = w+1; col  0 && Edge[v][col]  bool GraphMatrix::insertVertex(const T& vertex) { if(numVertices == maxVertices) // 顶点表满 return false; VerticesList[numVertices++] = vertex; return true; } // 插入边(v1, v2)权值为cost template  bool GraphMatrix::GraphMatrix::insertEdge(int v1, int v2, E cost) { if(v1 > -1 && v1  -1 && v2  bool GraphMatrix::removeVertex(int v) { if(v <0 && v > numVertices) // v不在图中,不删除 return false; if(numVertices == 1) // 只剩一个顶点,不删除 return false; int i, j; VerticesList[v] = VerticesList[numVertices-1]; // 用最后一个顶点替代当前要删的顶点 // 删除与v相关联边数 for(i = 0; i  0 && Edge[i][v]  bool GraphMatrix::removeEdge(int v1, int v2) { if(v1 > -1 && v1  -1 && v2  

(2)main.cpp

 // 测试数据: /* 5 7 A B C D E A B 24 A C 46 B C 15 B E 67 C B 37 C D 53 E D 31 */ #include "GraphMatrix.h" int main(int argc, const char * argv[]) { GraphMatrix st; // 声明对象 bool finished = false; int choice; char e1, e2, next; int weight; while(!finished) { cout <<"[1]创建基于邻接矩阵的图" <> choice; switch(choice) { case 1: st.inputGraph(); break; case 2: st.outputGraph(); break; case 3: cout <<"请输入顶点:"; cin >> e1; e2 = st.getValue(st.getFirstNeighbor(st.getVertexPos(e1))); if(e2) cout <<"顶点" <> e1 >> e2; next = st.getValue(st.getNextNeighbor(st.getVertexPos(e1), st.getVertexPos(e2))); if(next) cout <<"顶点" <> e1; if(st.insertVertex(e1)) cout <<"插入成功!" <> e1 >> e2 >> weight; st.insertEdge(st.getVertexPos(e1), st.getVertexPos(e2), weight); break; case 7: cout <<"请输入要删除的顶点:"; cin >> e1; if(st.removeVertex(st.getVertexPos(e1))) cout <<"顶点" <> e1 >> e2; st.removeEdge(st.getVertexPos(e1), st.getVertexPos(e2)); break; case 9: finished = true; break; default: cout <<"选择输入错误,请重新输入!" < 

测试结果:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

内容推荐:免费高清PNG素材下载
吐了个 "CAO" !
扫码关注 PHP1 官方微信号
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved PHP1.CN 第一PHP社区 版权所有 京ICP备19059560号-4