邻接矩阵在图像数据储存中的应用

#ifndef _GRAPH_H_ #define _GRAPH_H_ #include<iostream> using namespace std; #define VERTEX_DEFAULT_SIZE 10 template<typename Type> class Graph{ public: bool isEmpty()const{ return curVertices == 0; } bool isFull()const{ if(curVertices >= maxVertices || curEdges >= curVertices*(curVertices-1)/2) return true; //图满有2种情况：(1)、当前顶点数超过了最大顶点数，存放顶点的空间已满 return false; //(2)、当前顶点数并没有满，但是当前顶点所能达到的边数已满 } int getCurVertex()const{ return curVertices; } int getCurEdge()const{ return curEdges; } public: virtual bool insertVertex(const Type &v) = 0; //插入顶点 virtual bool insertEdge(const Type &v1, const Type &v2) = 0; //插入边 virtual bool removeVertex(const Type &v) = 0; //删除顶点 virtual bool removeEdge(const Type &v1, const Type &v2) = 0; //删除边 virtual int getFirstNeighbor(const Type &v) = 0; //得到第一个相邻顶点 virtual int getNextNeighbor(const Type &v, const Type &w) = 0; //得到下一个相邻顶点 public: virtual int getVertexIndex(const Type &v)const = 0; //得到顶点下标 virtual void showGraph()const = 0; //显示图 protected: int maxVertices; //最大顶点数 int curVertices; //当前顶点数 int curEdges; //当前边数 }; template<typename Type> class GraphMtx : public Graph<Type>{ //邻接矩阵继承父类矩阵 #define maxVertices Graph<Type>::maxVertices //因为是模板，所以用父类的数据或方法都得加上作用域限定符 #define curVertices Graph<Type>::curVertices #define curEdges Graph<Type>::curEdges public: GraphMtx(int vertexSize = VERTEX_DEFAULT_SIZE){ //初始化邻接矩阵 maxVertices = vertexSize > VERTEX_DEFAULT_SIZE ? vertexSize : VERTEX_DEFAULT_SIZE; vertexList = new Type[maxVertices]; //申请顶点空间 for(int i = 0; i < maxVertices; i++){ //都初始化为0 vertexList[i] = 0; } edge = new int*[maxVertices]; //申请边的行 for(i = 0; i < maxVertices; i++){ //申请列空间 edge[i] = new int[maxVertices]; } for(i = 0; i < maxVertices; i++){ //赋初值为0 for(int j = 0; j < maxVertices; j++){ edge[i][j] = 0; } } curVertices = curEdges = 0; //当前顶点和当前边数 } GraphMtx(Type (*mt)[4], int sz){ //通过已有矩阵的初始化 int e = 0; //统计边数 maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE; vertexList = new Type[maxVertices]; //申请顶点空间 for(int i = 0; i < maxVertices; i++){ //都初始化为0 vertexList[i] = 0; } edge = new int*[maxVertices]; //申请边的行 for(i = 0; i < maxVertices; i++){ //申请列空间 edge[i] = new Type[maxVertices]; } for(i = 0; i < maxVertices; i++){ //赋初值为矩阵当中的值 for(int j = 0; j < maxVertices; j++){ edge[i][j] = mt[i][j]; if(edge[i][j] != 0){ e++; //统计列的边数 } } } curVertices = sz; curEdges = e/2; } ~GraphMtx(){} public: bool insertVertex(const Type &v){ if(curVertices >= maxVertices){ return false; } vertexList[curVertices++] = v; return true; } bool insertEdge(const Type &v1, const Type &v2){ int maxEdges = curVertices*(curVertices-1)/2; if(curEdges >= maxEdges){ return false; } int v = getVertexIndex(v1); int w = getVertexIndex(v2); if(v==-1 || w==-1){ cout<<"edge no exit"<<endl; //要插入的顶点不存在，无法插入 return false; } if(edge[v][w] != 0){ //当前边已经存在，不能进行插入 return false; } edge[v][w] = edge[w][v] = 1; //因为是无向图，对称的，存在边赋为1； return true; } //删除顶点的高效方法 bool removeVertex(const Type &v){ int i = getVertexIndex(v); if(i == -1){ return false; } vertexList[i] = vertexList[curVertices-1]; int edgeCount = 0; for(int k = 0; k < curVertices; k++){ if(edge[i][k] != 0){ //统计删除该行的边数 edgeCount++; } } //删除行 for(int j = 0; j < curVertices; j++){ edge[i][j] = edge[curVertices-1][j]; } //删除列 for(j = 0; j < curVertices; j++){ edge[j][i] = edge[j][curVertices-1]; } curVertices--; curEdges -= edgeCount; return true; } /* //删除顶点用的是数组一个一个移动的方法，效率太低。 bool removeVertex(const Type &v){ int i = getVertexIndex(v); if(i == -1){ return false; } for(int k = i; k < curVertices-1; ++k){ vertexList[k] = vertexList[k+1]; } int edgeCount = 0; for(int j = 0; j < curVertices; ++j){ if(edge[i][j] != 0) edgeCount++; } for(int k = i; k < curVertices-1; ++k) { for(int j = 0; j < curVertices; ++j) { edge[k][j] = edge[k+1][j]; } } for(int k = i; k < curVertices-1; ++k) { for(int j = 0; j < curVertices; ++j) { edge[j][k] = edge[j][k+1]; } } curVertices--; curEdges -= edgeCount; return true; } */ bool removeEdge(const Type &v1, const Type &v2){ int v = getVertexIndex(v1); int w = getVertexIndex(v2); if(v==-1 || w==-1){ //判断要删除的边是否在当前顶点内 return false; //顶点不存在 } if(edge[v][w] == 0){ //这个边根本不存在，没有必要删 return false; } edge[v][w] = edge[w][v] = 0; //删除这个边赋值为0，代表不存在； curEdges--; return true; } int getFirstNeighbor(const Type &v){ int i = getVertexIndex(v); if(i == -1){ return -1; } for(int col = 0; col < curVertices; col++){ if(edge[i][col] != 0){ return col; } } return -1; } int getNextNeighbor(const Type &v, const Type &w){ int i = getVertexIndex(v); int j = getVertexIndex(w); if(i==-1 || j==-1){ return -1; } for(int col = j+1; col < curVertices; col++){ if(edge[i][col] != 0){ return col; } } return -1; } public: void showGraph()const{ if(curVertices == 0){ cout<<"Nul Graph"<<endl; return; } for(int i = 0; i < curVertices; i++){ cout<<vertexList[i]<<" "; } cout<<endl; for(i = 0; i < curVertices; i++){ for(int j = 0; j < curVertices; j++){ cout<<edge[i][j]<<" "; } cout<<vertexList[i]<<endl; } } int getVertexIndex(const Type &v)const{ for(int i = 0; i < curVertices; i++){ if(vertexList[i] == v){ return i; } } return -1; } private: Type *vertexList; //存放顶点的数组 int **edge; //存放顶点关系的矩阵用边表示 }; #endif