一.序 圖的存儲表示有多種，在此我們只研究三種最為常用的存儲表示方式：鄰接矩陣(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--;}新聞熱點
疑難解答
