圖的結構定義

? ? 圖是由一個頂點集?V?和一個弧集?E構成的數據結構。

? ? ?Graph?=?(V?,?E?)

? ?其中，E?＝?{<v,w>|?v,w∈V?且?P(v,w)}?<v,w>表示從?v?到?w?的一條弧，并稱?v?為弧尾，w?為弧頭。謂詞?P(v,w)?定義了弧?<v,w>的意義或信息。

? ?由頂點集和邊集構成的圖稱作無向圖。

? ?如果”弧”是有方向的，則稱由頂點集和弧集構成的圖為有向圖。

?

鄰接矩陣

?

? 定義:矩陣的元素為

?有向圖的鄰接矩陣為非對稱矩陣,?而無向圖的鄰接矩陣為對稱矩陣;

//無向圖的鄰接矩陣 const int MAX_VERTS = 20; //頂點 template <typename Type> class Vertex { public:Vertex(const Type &_node = Type()): node(_node) {}private:Type node; }; //圖 template <typename Type> class Graph { public:Graph();~Graph();void addVertex(const Type &vertex);void addEdge(int start, int end);void printMatrix();private:Vertex<Type>* vertexList[MAX_VERTS];int nVerts;int adjMatrix[MAX_VERTS][MAX_VERTS]; };
template <typename Type> Graph<Type>::Graph():nVerts(0) {for (int i = 0; i < MAX_VERTS; ++i)for (int j = 0; j < MAX_VERTS; ++j)adjMatrix[i][j] = 0; } template <typename Type> Graph<Type>::~Graph() {for (int i = 0; i < nVerts; ++i)delete vertexList[i]; } template <typename Type> void Graph<Type>::addVertex(const Type &vertex) {vertexList[nVerts ++] = new Vertex<Type>(vertex); } template <typename Type> void Graph<Type>::addEdge(int start, int end) {//無向圖adjMatrix[start][end] = 1;adjMatrix[end][start] = 1; } template <typename Type> void Graph<Type>::printMatrix() {for (int i = 0; i < nVerts; ++i){for (int j = 0; j < nVerts; ++j)cout << adjMatrix[i][j] << ' ';cout << endl;} }

//測試代碼 int main() {Graph<char> g;g.addVertex('A'); //0g.addVertex('B'); //1g.addVertex('C'); //2g.addVertex('D'); //3g.addVertex('E'); //4g.addEdge(0, 1); //A-Bg.addEdge(0, 3); //A-Dg.addEdge(1, 0); //B-Ag.addEdge(1, 4); //B-Eg.addEdge(2, 4); //C-Eg.addEdge(3, 0); //D-Ag.addEdge(3, 4); //D-Eg.addEdge(4, 1); //E-Bg.addEdge(4, 2); //E-Cg.addEdge(4, 3); //E-Dg.printMatrix();return 0; }

鄰接表

注意:在有向圖的鄰接表中不易找到指向該頂點的弧。

//無向圖的鄰接表 template <typename Type> class Graph { public:Graph(int _size = 10);~Graph();void addVertex(const Type &vertex);void addEdge(int start, int end);void printVertex();void printAdjList();private:Type *vertexList;list<int> *headNode;int size;int nVertex; };
template <typename Type> Graph<Type>::Graph(int _size):size(_size), nVertex(0) {vertexList = new Type[size];headNode = new list<int>[size]; } template <typename Type> Graph<Type>::~Graph() {delete []vertexList;delete []headNode; } template <typename Type> void Graph<Type>::addVertex(const Type &vertex) {vertexList[nVertex ++] = vertex; } template <typename Type> void Graph<Type>::addEdge(int start, int end) {headNode[start].push_back(end); } template <typename Type> void Graph<Type>::printVertex() {cout << vertexList[0];for (int i = 1; i < nVertex; ++i)cout << ' ' << vertexList[i];cout << endl; } template <typename Type> void Graph<Type>::printAdjList() {for (int i = 0; i < nVertex; ++i){cout << i;for (list<int>::iterator iter = headNode[i].begin();iter != headNode[i].end();++iter)cout << " -> " << *iter;cout << endl;} }
//測試代碼 int main() {Graph<char> g;g.addVertex('A'); //0g.addVertex('B'); //1g.addVertex('C'); //2g.addVertex('D'); //3g.addVertex('E'); //4g.printVertex();g.addEdge(0, 1); //A-Bg.addEdge(0, 3); //A-Dg.addEdge(1, 0); //B-Ag.addEdge(1, 4); //B-Eg.addEdge(2, 4); //C-Eg.addEdge(3, 0); //D-Ag.addEdge(3, 4); //D-Eg.addEdge(4, 1); //E-Bg.addEdge(4, 2); //E-Cg.addEdge(4, 3); //E-Dg.printAdjList();return 0; }

總結

以上是生活随笔為你收集整理的数据结构基础(20) --图的存储结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。