图的存储表示--邻接矩阵法实现

2019-11-08 19:46:01

字体：大中小

来源：转载

供稿：网友

一.序图的存储表示有多种，在此我们只研究三种最为常用的存储表示方式：邻接矩阵(adjacency matrices)，邻接表(adjacency lists)，邻接多重表(adjacency multilists)。今天实现邻接矩阵的存储表示。二.模型这里写图片描述三.邻接矩阵表示法的缺点 1.时间开销很高对于邻接矩阵表示的图来说，要确定“图中有多少条边？”，“图是连通的吗？”等问题，就需要扫描图的所有边，至少需要o(n^2)时间，因为必须检查矩阵中的n^2-n（邻接矩阵对角线上的n个元素都是0，可以不用检查；对于无向图而言，邻接矩阵是对称的，实际上只需检查邻接矩阵中的一半的元素）。 2.存储利用率很低在稀疏图（边很少的图e < n^2,图的邻接矩阵变成稀疏矩阵，大部分元素为0），存储利用率很低。此时不希望检查这些0元素。

实际上，希望用更少的时间（o(e+n),e为图的边的条数)，且e < n^2/2,必须采用邻接表（顺序表或链表）存储表示

三.实现源码请戳https://github.com/zhangzhuo233/Data_Structure/tree/master/Graph

//GraphMtx.h//邻接矩阵方式//2017-2-15 12:00#PRagma once#include<iostream>using namespace std;#define DEFAULT_VERLIST_SIZE 10template<class T, class E>class GraphMtx{public: GraphMtx(T x,int sz=DEFAULT_VERLIST_SIZE) { maxVertices = sz > DEFAULT_VERLIST_SIZE ? sz : DEFAULT_VERLIST_SIZE; VerticesList = new T[maxVertices]; for(int i=0; i<maxVertices; ++i) //顶点置为# { VerticesList[i] = x; } Edge =new E*[maxVertices]; for(int i=0; i<maxVertices; ++i) { Edge[i] = new E[maxVertices]; for(int j=0; j<maxVertices; ++j)//边的条数置为0 { Edge[i][j] = 0; } } numVertices = numEdges = 0; } ~GraphMtx() { delete VerticesList; VerticesList = NULL; for(int i=0; i<maxVertices; ++i) { delete Edge[i]; Edge[i] = NULL; } delete Edge; Edge = NULL; numVertices = numEdges = 0; }public: bool InsertVertex(const T vertex); //插入顶点vertex bool InsertEdge(const T vertex1, const T vertex2);//插入一条边(vertex1,vertex2) int NumberOfVertex()const; //获取顶点总数 int NumberOfEdge()const; //获取边数 int GetFirstNeighbor(const T vertex)const;//获取顶点vertex的第一个邻接顶点的位置 int GetNextNeighbor(const T vertex1, const T vertex2)const;//获取顶点vertex1的某邻接顶点vertex2的下一个邻接顶点的位置 bool RemoveVertex(const T vertex); //删除顶点vertex bool RemoveEdge(const T vertex1, const T vertex2);//删除边(vertex1, vertex2)public: int GetPosVertex(T vertex)const { for(int i=0; i<numVertices; ++i) { if(VerticesList[i] == vertex) return i; } return -1; } void GraphShow() { cout<<" "; for(int i=0; i<numVertices; ++i) { cout<<VerticesList[i]<<' '; } cout<<endl; for(int i=0; i<numVertices; ++i) { cout<<VerticesList[i]<<' '; for(int j=0; j<numVertices; ++j) cout<<Edge[i][j]<<' '; cout<<endl; } }private: T *VerticesList;//顶点表向量 E **Edge; //边的存储空间 int maxVertices;//顶点容量 int numVertices;//当前顶点个数 int numEdges; //当前边数};template<class T, class E>bool GraphMtx<T,E>::InsertVertex(const T vertex){ if(numVertices >= maxVertices) return false; VerticesList[numVertices++] = vertex; return true;}template<class T, class E>bool GraphMtx<T,E>::InsertEdge(const T vertex1, const T vertex2){ int v1 = GetPosVertex(vertex1); int v2 = GetPosVertex(vertex2); if(v1 == -1 || v2 == -1) return false; Edge[v1][v2] = Edge[v2][v1] = 1; numEdges++;}template<class T, class E>int GraphMtx<T,E>::NumberOfVertex()const{return numVertices;}template<class T, class E>int GraphMtx<T,E>::NumberOfEdge()const{return numEdges;}template<class T, class E>int GraphMtx<T,E>::GetFirstNeighbor(const T vertex)const{ int v = GetPosVertex(vertex); if(v == -1) return -1; for (int i = 0; i < numVertices; ++i) { if(Edge[v][i] == 1) return i; } return -1;}template<class T, class E>int GraphMtx<T,E>::GetNextNeighbor(const T vertex1, const T vertex2)const{ int v1 = GetPosVertex(vertex1); int v2 = GetPosVertex(vertex2); if(v1 == -1 || v2 == -1) return -1; for (int i = v2+1; i < numVertices; ++i) { if(Edge[v1][i] == 1) return i; } return -1;}template<class T, class E>bool GraphMtx<T,E>::RemoveVertex(const T vertex){ //消耗空间的做法：用后一行/列覆盖要删除的行/列，后面的往前移动; //时间复杂度低的做法：用最后一行/列覆盖要删除的顶点行/列,会改变顶点的顺序 //选用后者做法 int xnumedge = 0; int v = GetPosVertex(vertex); if(v == -1) return false; for (int i = v; i < numVertices; i++) { if(Edge[v][i] == 1) xnumedge++; } //顶点覆盖 VerticesList[v] = VerticesList[numVertices-1]; //行覆盖 for (int i = v; i < numVertices; i++) Edge[v][i] = Edge[numVertices-1][i]; //列覆盖 for (int i = v; i < numVertices; i++) Edge[i][v] = Edge[i][numVertices-1]; //顶点减少，边减少 numVertices--; numEdges -= xnumedge;}template<class T, class E>bool GraphMtx<T,E>::RemoveEdge(const T vertex1, const T vertex2){ int v1 = GetPosVertex(vertex1); int v2 = GetPosVertex(vertex2); if(v1 == -1 || v2 == -1) return false; if(Edge[v1][v2] == 0) return false; Edge[v1][v2] = Edge[v2][v1] = 0; numEdges--;}

上一篇：leecode 解题总结：122. Best Time to Buy and Sell Stock II

下一篇：IO流_复制多级文件夹案例