圖的存儲表示--鄰接表實現

2019-11-08 18:52:17

字體：大中小

來源：轉載

供稿：網友

一.序鄰接表是鄰接矩陣的改進。當圖中的邊數少于頂點個數時，鄰接矩陣中會出現大量的零元素，如果這些零元素，將消耗大量的內存。為此，可以把鄰接矩陣的n行改為n個鏈表，把同一個頂點出發的邊鏈接到同一個稱之為邊鏈表的單鏈表中，單鏈表的每個結點代表一條邊，叫做邊結點，結點中保存有與該邊相關聯的另一頂點的頂點下標dest和指向同一鏈表中下一邊結點的指針link.如果帶權圖時，結點中還要保存改邊上的權值cost.頂點i的出邊表的表頭指針adj在頂點表的下標為i的頂點記錄中，該記錄還保存了該頂點的其他信息。二.模型這里寫圖片描述三.實現源碼請戳https://github.com/zhangzhuo233/Data_Structure/tree/master/Graph

/*GraphLink.h**2016.2.16*/#PRagma once#include<iostream>using namespace std;#define DEFAULT_VERTEX_SIZE 10template<class Type> class GraphLink;template<class Type>class Edge{ friend class GraphLink<Type>;public: Edge(int num=0):dest(num),link(NULL) {} ~Edge() {}private: int dest; Edge *link;};template<class Type>class Vertex{ friend class GraphLink<Type>;public: Vertex():data(),adj(NULL) {} ~Vertex() {}private: Type data; Edge<Type> *adj;};template<class Type>class GraphLink{public: GraphLink(int sz = DEFAULT_VERTEX_SIZE) { maxVertices = sz > DEFAULT_VERTEX_SIZE ? sz : DEFAULT_VERTEX_SIZE; numEdges = numVertices = 0; NodeTable = new Vertex<Type>[maxVertices]; } ~GraphLink() { int n = numVertices; for(int i = 0; i < n; ++i) RemoveVertex(NodeTable[i].data); delete []NodeTable; }public: bool InsertVertex(const Type &v); //插入頂點v bool InsertEdge(const Type &vertex1, const Type &vertex2);//插入vertex1-->vertex2邊 int NumberOfVertice()const; //獲取頂點總數 int NumberOfEdge()const; //獲取邊總數 int GetFirstNeighbor(const Type &vertex)const; //獲取vertex的第一個鄰接頂點 int GetNextNeighbor(const Type &vertex1, const Type &vertex2)const;//獲取vertex1的鄰接頂點vertex2的下一個鄰接頂點 bool RemoveVertex(const Type &vertex); //刪除頂點vertex bool RemoveEdge(const Type &vertex1, const Type &vertex2);//刪除vertex1和vertex2構成的邊public: void ShowGraph()const { for (int i = 0; i < numVertices; ++i) { cout<<NodeTable[i].data<<"-->"; Edge<Type> *e = NodeTable[i].adj; while(e != NULL) { cout<<e->dest<<"-->"; e = e->link; } cout<<"Nul"<<endl; } }private: int GetPosVertex(const Type v)const { for (int i = 0; i < numVertices; ++i) { if(NodeTable[i].data == v) return i; } return -1; } Vertex<Type> *NodeTable;//頂點表 int maxVertices; int numVertices; int numEdges;};template<class Type>bool GraphLink<Type>::InsertVertex(const Type &v){ if(numVertices > maxVertices) return false; NodeTable[numVertices++].data = v; return true;}template<class Type>bool GraphLink<Type>::InsertEdge(const Type &vertex1, const Type &vertex2){ int v1 = GetPosVertex(vertex1); int v2 = GetPosVertex(vertex2); if(v1 == -1 || v2 == -1) return false; //采用單鏈表的頭插方式 //v1-->v2 Edge<Type> *e = new Edge<Type>(v2); e->link = NodeTable[v1].adj; NodeTable[v1].adj = e; //v2-->v1 e = new Edge<Type>(v1); e->link = NodeTable[v2].adj; NodeTable[v2].adj = e; numEdges++;}template<class Type>int GraphLink<Type>::NumberOfVertice()const{return numVertices;}template<class Type>int GraphLink<Type>::NumberOfEdge()const{return numEdges;}template<class Type>int GraphLink<Type>::GetFirstNeighbor(const Type &vertex)const{ int v = GetPosVertex(vertex); if(v == -1) return -1; if(NodeTable[v].adj != NULL) return NodeTable[v].adj->dest; return -1;}template<class Type>int GraphLink<Type>::GetNextNeighbor(const Type &vertex1, const Type &vertex2)const{ int v1 = GetPosVertex(vertex1); int v2 = GetPosVertex(vertex2); if(v1 == -1 || v2 == -1) return -1; Edge<Type> *p = NodeTable[v1].adj; while(p != NULL && p->dest != v2) p = p->link; if(NULL == p) return -1; if(p->link != NULL) return p->link->dest; return -1;}template<class Type>bool GraphLink<Type>::RemoveEdge(const Type &vertex1, const Type &vertex2){ int v1 = GetPosVertex(vertex1); int v2 = GetPosVertex(vertex2); if(v1 == -1 || v2 == -1) return false; //刪除v1-->v2 Edge<Type> *p = NodeTable[v1].adj; Edge<Type> *q = NULL; while(p != NULL && p->dest != v2) { q = p; p = p->link; } if(NULL == p) return false; if(q == NULL)//說明刪除的是頭結點 NodeTable[v1].adj = p->link; else q->link = p->link; free(p); p == NULL; //刪除v2-->v1 p = NodeTable[v2].adj; q = NULL; while(p != NULL && p->dest != v1) { q = p; p = p->link; } if(NULL == p) return false; if(q == NULL)//說明刪除的是頭結點 NodeTable[v2].adj = p->link; else q->link = p->link; free(p); p == NULL; numEdges--;}template<class Type>bool GraphLink<Type>::RemoveVertex(const Type &vertex){/*思路：** 1.剔除頂點vertex邊鏈表中所包含頂點中的關于vertex的結點(可以借用RemoveEdage())** 2.最后一行覆蓋所刪除行（1）頂點覆蓋頂點 1）p保存最后一行的單鏈表，刪除行的頂點指向最后一行的邊鏈表，tmp保存numVertices-1 2）覆蓋頂點 3）與最后一行所關聯的結點，將他們所包含的最后一個結點的下標更改成所刪除的下標 (2)邊鏈表覆蓋邊鏈表（指向tmp）** 3.減少頂點數*/ int v = GetPosVertex(vertex); if(v == -1) return false; //1. Edge<Type> *p = NodeTable[v].adj; while(p != NULL) { RemoveEdge(vertex, NodeTable[p->dest].data); p = NodeTable[v].adj; } //2. //1) p = NodeTable[numVertices-1].adj; NodeTable[v].adj = NodeTable[numVertices-1].adj; int tmp = numVertices-1; //2) NodeTable[v].data = NodeTable[numVertices-1].data; //3) Edge<Type> *q = NULL; while(p != NULL) { q = NodeTable[p->dest].adj; while(q != NULL && q->dest != tmp) q = q->link; q->dest = v; p = p->link; } //3. numVertices--; return true;}

測試代碼

/*Test.cpp**2016.2.16*/#include"GraphLink.h"#include<vld.h>int main(){ GraphLink<char> gl; gl.ShowGraph(); gl.InsertVertex('A'); gl.InsertVertex('B'); gl.InsertVertex('C'); gl.InsertVertex('D'); gl.ShowGraph(); gl.InsertEdge('A', 'B'); gl.InsertEdge('A', 'C'); gl.InsertEdge('B', 'D'); gl.ShowGraph(); cout<<gl.GetFirstNeighbor('A')<<endl; cout<<gl.GetNextNeighbor('A', 'B')<<endl; gl.RemoveVertex('A'); gl.RemoveVertex('B'); gl.RemoveVertex('C'); gl.RemoveVertex('D'); gl.ShowGraph();}

上一篇：C# TCP退出Accept阻塞的兩種方法

下一篇：Eclipse Ctrl+左鍵查看源代碼Source not found