概述

记录一些图的基本概念，以及图的两种表示方式（邻接表和邻接矩阵）的代码实现，最后总结了两种方式的优缺点，还简单介绍了十字链表和逆邻接表。

图的部分基本概念（我记不住的）

1、完全图

一个无向图，任意两个顶点之间有且仅有一条边，则称为无向完全图。若一个无向完全图有 n 个顶点，那么它就有 n∗(n−1)/2 条边。 一个有向图，任意两个顶点之间有且仅有方向相反的两条边，则称为有向完全图。若一个有向完全图有 n 个顶点，那么它就有 n∗(n−1) 条边。

2、邻接顶点

在无向图中，顶点 u 与 v 之间有一条边（u，v），则称 u 和 v 互为邻接顶点。 在有向图中，顶点 u 和 v 之间有一条边<u, v>，则顶点 u 邻接到顶点 v，顶点 v 邻接自顶点 u，并称边<u，v>与顶点 u、v 相关联。

3、顶点的度

顶点的度就是与它相关联的边的条数，入度表示边的终点指向顶点的个数，出度表示边的起点指向顶点的个数。

在有向图中，顶点的度等于入度与出度的和。

在无向图中，顶点的度 =入度 = 出度。

4、连通图：

在无向图中，两个顶点之间有路径，则称这两个顶点是连通的。如果如中任意一对顶点都是连通的，则称此图为连通图。

在有向图中，若任意一对顶点 vi 和 vj，都有从 vi 到 vj 的路径，则称此图为强连通图。

5、生成树：

一个连通图（无向图）的最小子图称为该图的生成树。有 n 个顶点的连通图的生成树有 n - 1 条边。最小生成树就是权值和最小的生成树。

邻接矩阵表示法

在一个一维数组中存储所有的点，在一个二维数组中存储顶点之间的边的权值，以及一个布尔值标记是否是有向图，默认是无向图：

bool isDirected; // 标识是否是有向图，默认为false vector<V> vertex; // 存储顶点 vector<vector<W> > edge; // 存储边

graph.h

#ifndef GRAPH_H #define GRAPH_H #include <vector> #include <cassert> #include <iostream> using namespace std; // V -- 图顶点的数据类型 // W -- 图边权值的类型 template <typename V, typename W> class GraphMatrix { public: GraphMatrix(const V* _vertex, size_t _size, bool _isDirected = false); // 打印图中的所有边 void printEdge(); // 向图中添加一条边 void addEdge(const V& v1, const V& v2, const W& weight); private: // 获取边所在的下标 int getIndexOfVertex(const V& _vertex); private: bool isDirected; // 标识是否是有向图，默认为false vector<V> vertex; // 存储顶点 vector<vector<W> > edge; // 存储边 }; #endif //GRAPH_H

graph.cpp

#include "graph.h" /* * public 函数 */ template<typename V, typename W> GraphMatrix<V,W>::GraphMatrix(const V* _vertex, size_t _size, bool _isDirected = false) { // 开辟空间并初始化数据 this->vertex.resize(_size); this->edge.resize(_size); this->isDirected = _isDirected; for (int idx = 0; idx < _size; ++idx) { this->vertex[idx] = _vertex[idx]; this->edge[idx].resize(_size); } } template<typename V, typename W> void GraphMatrix<V, W>::addEdge(const V& v1, const V& v2, const W& weight) { int start = getIndexOfVertex(v1); int end = getIndexOfVertex(v2); edge[start][end] = weight; // 如果是无向图还需要添加对称的一遍 if (!isDirected) edge[end][start] = weight; } template<typename V, typename W> void GraphMatrix<V, W>::printEdge() { for (int idx = 0; idx < vertex.size(); ++idx) cout << "" << vertex[idx]; cout << endl; for (int idx_row = 0; idx_row < edge.size(); ++idx_row) { cout << vertex[idx_row] << " "; for (int idx_col = 0; idx_col < edge.size(); ++idx_col) { cout << " " << edge[idx_row][idx_col] ; } cout << endl; } cout << endl; } /* * private 函数 */ template<typename V, typename W> int GraphMatrix<V, W>::getIndexOfVertex(const V& v) { for (int idx = 0; idx < vertex.size(); idx++) { if (vertex[idx] == v) return idx; } // 如果没有找到就说明发生了错误 assert(false); return -1; }

test.cpp

#include "graph.cpp" #include <string> #include <vector> #include <iostream> using namespace std; void TestGraphMatrix() { // 无向图 const char* str = "ABCDE"; GraphMatrix<char, int> graph(str, strlen(str)); graph.addEdge('A', 'D', 8); graph.addEdge('A', 'E', 9); graph.addEdge('B', 'E', 2); graph.addEdge('A', 'B', 6); graph.printEdge(); cout << "--------------------------------" << endl; // 有向图 GraphMatrix<char, int> graph1(str, strlen(str), true); graph1.addEdge('A', 'D', 8); graph1.addEdge('A', 'E', 9); graph1.addEdge('B', 'E', 2); graph1.addEdge('E', 'C', 6); graph1.printEdge(); } int main() { TestGraphMatrix(); return 0; }

输出结果：

A B C D E A 0 6 0 8 9 B 6 0 0 0 2 C 0 0 0 0 0 D 8 0 0 0 0 E 9 2 0 0 0 ----------- A B C D E A 0 0 0 8 9 B 0 0 0 0 2 C 0 0 0 0 0 D 0 0 0 0 0 E 0 0 6 0 0

邻接表表示法

邻接表是把顶点之间的边当做链表上的结点，其中边结点数据成员有：

起点的索引终点的索引边所在权值指向下一个结点的指针 // W -- 边对应权值的类型 template <typename W> struct EdgeNode { W weight; // 边所对应权值 unsigned int startIndex; // 边起点的索引 unsigned int endIndex; // 边终点的索引 EdgeNode<W>* nextNode; // 指向下个结点 };

用一个一维数组来存储所有的顶点。一个一维数组来存储顶点所对应的链表的头指针（结点表示以当前顶点为起点的边）。

bool isDirected; vector<V> vertex; // 存储所有顶点 vector<EdgeNode<W>*> linkTable; // 存储顶点的边

graph.h

#ifndef GRAPH_H #define GRAPH_H #include <vector> #include <cassert> #include <iostream> using namespace std; // W -- 边对应权值的类型 template <typename W> struct EdgeNode { W weight; // 边所对应权值 size_t startIndex; // 边起点的索引 size_t endIndex; // 边终点的索引 EdgeNode<W>* nextNode; // 指向下个结点 EdgeNode(size_t start, size_t end, const W& _weight) : startIndex(start) , endIndex(end) , weight(_weight) {} }; // V -- 图顶点的数据类型 // W -- 图边权值的类型 template <typename V, typename W> class GraphLink { public: typedef EdgeNode<W> node; GraphLink(const V* _vertex, size_t _size, bool _isDirected = false); // 打印图中的边 void printEdge(); // 向图中添加一条边 void addEdge(const V& v1, const V& v2, const W& weight); private: // 获取顶点所在索引 size_t getIndexOfVertex(const V& v); // 添加一条边 void __addEdge(size_t startIndex, size_t endIndex, const W& weight); private: bool isDirected; vector<V> vertex; // 存储所有顶点 vector<node*> linkTable; // 存储顶点的边 }; #endif //GRAPH_H

graph.cpp

#include "graph.h" /* * public 函数 */ template<typename V, typename W> GraphLink<V, W>::GraphLink(const V* _vertex, size_t _size, bool _isDirected) { // 开辟空间并初始化数据 this->vertex.resize(_size); this->linkTable.resize(_size); this->isDirected = _isDirected; for (size_t i = 0; i < _size; i++) { this->vertex[i] = _vertex[i]; } } template<typename V, typename W> void GraphLink<V, W>::printEdge() { for (size_t idx = 0; idx < vertex.size(); ++idx) { cout << vertex[idx] << ": "; node* pEdge = linkTable[idx]; while (pEdge) { cout << pEdge->weight << "[" << vertex[pEdge->endIndex] << "]-->"; pEdge = pEdge->nextNode; } cout << "NULL" << endl; } cout << endl; } template<typename V, typename W> void GraphLink<V, W>::addEdge(const V& v1, const V& v2, const W& weight) { size_t startIndex = getIndexOfVertex(v1); size_t endIndex = getIndexOfVertex(v2); // 防止填加自己指向自己的边 assert( startIndex!=endIndex); __addEdge(startIndex, endIndex, weight); // 无向图需要添加对称的一条边 if (!isDirected) __addEdge(endIndex, startIndex, weight); } /* * private 函数 */ template <typename V, typename W> void GraphLink<V, W>::__addEdge(size_t startIndex, size_t endIndex, const W& weight) { // 头插的方式添加边到链表中 node* pNewEdge = new node(startIndex, endIndex, weight); pNewEdge->nextNode = linkTable[startIndex]; linkTable[startIndex] = pNewEdge; } template<typename V, typename W> size_t GraphLink<V, W>::getIndexOfVertex(const V& v) { for (int idx = 0; idx < vertex.size(); idx++) { if (vertex[idx] == v) return idx; } // 如果没有找到就说明发生了错误 assert(false); return -1; }

test.cpp

#include "graph.cpp" #include <string> #include <vector> #include <iostream> using namespace std; void TestGraphLink() { // 无向图 char* str = "ABCDE"; GraphLink<char, int> graph1(str, strlen(str)); graph1.addEdge('A', 'C', 2); graph1.addEdge('D', 'B', 6); graph1.addEdge('A', 'B', 4); graph1.addEdge('E', 'D', 9); graph1.printEdge(); cout << "------------" << endl; // 有向图 GraphLink<char, int> graph2(str, strlen(str), true); graph2.addEdge('D', 'C', 2); graph2.addEdge('B', 'E', 6); graph2.addEdge('A', 'D', 4); graph2.addEdge('E', 'D', 9); graph2.printEdge(); } int main() { TestGraphLink(); return 0; }

输出结果：

A: 4[B]-->2[C]-->NULL B: 4[A]-->6[D]-->NULL C: 2[A]-->NULL D: 9[E]-->6[B]-->NULL E: 9[D]-->NULL ---------------------- A: 4[D]-->NULL B: 6[E]-->NULL C: NULL D: 2[C]-->NULL E: 9[D]-->NULL

总结与对比

1、在邻接矩阵表示中，无向图的邻接矩阵是对称的。矩阵中第 i 行或 第 i 列有效元素个数之和就是顶点的读。

在有向图中 第 i 行有效元素个数之和是顶点的出度，第 i 列有效元素个数之和是顶点的入度。

2、在邻接表的表示中，无向图的同一条边在邻接表中存储的两次。如果想要知道顶点的读，只需要求出所对应链表的结点个数即可。

有向图中每条边在邻接表中只出现一此，求顶点的出度只需要遍历所对应链表即可。求出度则需要遍历其他顶点的链表。

3、邻接矩阵与邻接表优缺点：

邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。而其缺点是如果顶点之间的边比较少，会比较浪费空间。因为是一个 n∗n 的矩阵。

而邻接表的优点是节省空间，只存储实际存在的边。其缺点是关注顶点的度时，就可能需要遍历一个链表。还有一个缺点是，对于无向图，如果需要删除一条边，就需要在两个链表上查找并删除。

扩展

逆邻接表

在邻接表中对于有向图有一个很大的缺陷，如果我们比较关心顶点入度那么就需要遍历所有链表。为了避免这种情况出现，我们可以采用逆邻接表来存储，它存储的链表是别的顶点指向它。这样就可以快速求得顶点的入度。

如何对有向图的入度和出度都关心，那么久可以采取十字链表的方式。相当于每一个顶点对应两个链表，一个是它指向别的顶点，一个是别的顶点指向它。

全文完