[高阶数据结构四] 初始图论

1.前言

本篇着重讲解图的相关知识，大家跟随我的脚步往下阅读。

本章重点：

本章着重讲解图的基本知识，图的存储结构：邻接矩阵，邻接表以及图的模拟实现

2.图的基本概念

图是由顶点集合及顶点间的关系组成的一种数据结构： G = (V ， E) ，其中：

顶点集合 V = {x|x 属于某个数据对象集 } 是有穷非空集合 ；

E = {(x,y)|x,y 属于 V} 或者 E = {<x, y>|x,y 属于 V && Path(x, y)} 是顶点间关系的有穷集合，也叫

做边的集合 。

(x, y) 表示 x 到 y 的一条双向通路，即 (x, y) 是无方向的； Path(x, y) 表示从 x 到 y 的一条单向通路，即

Path(x, y) 是有方向的。

顶点和边： 图中结点称为顶点 ，第 i 个顶点记作 vi 。 两个顶点 vi 和 vj 相关联称作顶点 vi 和顶点 vj 之间

有一条边 ，图中的第 k 条边记作 ek ， ek = (vi ， vj) 或 <vi ， vj> 。

上述说了这么多抽象概念，相信很多人都不太理解。直接上例子

例：

首先明确一点，二叉树也是图的一种。 G1中的顶点就是结点0,1,2,3.记作v1,v2…,两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，图中的第k条边记作ek，ek = (vi，vj)或<vi，vj>。

有向图和无向图： 在有向图中，顶点对 <x, y> 是有序的，顶点对 <x ， y> 称为顶点 x 到顶点 y 的一条 边 ( 弧 ) ， <x, y> 和 <y, x> 是两条不同的边 ，比如下图 G3 和 G4 为有向图。

在 无向图中，顶点对 (x, y) 是无序的，顶点对 (x,y) 称为顶点 x 和顶点 y 相关联的一条边，这条边没有特定方向， (x, y) 和 (y ， x) 是同一条边 ，比如上图 G1 和 G2 为无向图。注意： 无向边 (x, y) 等于有向边 <x, y> 和 <y, x> 。

例如：

3. 与图相关的专业名词

完全图：在有 n 个顶点的无向图中 ，若有 n * (n-1)/2 条边，即 任意两个顶点之间有且仅有一条边 ，

则称此图为 无向完全图 ，比如上图 G1 ；在 n 个顶点的有向图 中，若有 n * (n-1) 条边，即 任意两个

顶点之间有且仅有方向相反的边 ，则称此图为 有向完全图 ，比如上图 G4 。

邻接顶点：在 无向图中 G 中，若 (u, v) 是 E(G) 中的一条边，则称 u 和 v 互为邻接顶点 ，并称边 (u,v) 依

附于顶点 u 和 v ；在 有向图 G 中，若 <u, v> 是 E(G) 中的一条边，则称顶点 u 邻接到 v ，顶点 v 邻接自顶

点 u ，并称边 <u, v> 与顶点 u 和顶点 v 相关联 。

顶点的度：顶点 v 的度是指与它相关联的边的条数，记作 deg(v) 。在有向图中， 顶点的度等于该顶

点的入度与出度之和 ，其中顶点 v 的 入度是以 v 为终点的有向边的条数 ，记作 indev(v); 顶点 v 的出度

是以 v 为起始点的有向边的条数 ，记作 outdev(v) 。因此： dev(v) = indev(v) + outdev(v) 。注

意：对于 无向图，顶点的度等于该顶点的入度和出度 ，即 dev(v) = indev(v) = outdev(v) 。

例如：

路径：在图 G = (V ， E) 中，若 从顶点 vi 出发有一组边使其可到达顶点 vj ，则称顶点 vi 到顶点 vj 的顶

点序列为从顶点 vi 到顶点 vj 的路径 。

路径长度 ：对于 不带权的图，一条路径的路径长度是指该路径上的边的条数 ；对于 带权的图，一

条路 径的路径长度是指该路径上各个边权值的总和 。

例如：

例如由A->D,那么路径可以有A->E->D / A->C->D /A->E->B->C->D等，路径长度就是相关值进行相+即可。

简单路径与回路 ： 若路径上各顶点 v1 ， v2 ， v3 ， … ， vm 均不重复，则称这样的路径为简单路

径。若路 径上第一个顶点 v1 和最后一个顶点 vm 重合，则称这样的路径为回路或环 。

例如：

子图：设图 G = {V, E} 和图 G1 = {V1 ， E1} ，若 V1 属于 V 且 E1 属于 E ，则称 G1 是 G 的子图 。

例如：

连通图 ：在 无向图 中，若从顶点 v1 到顶点 v2 有路径，则称顶点 v1 与顶点 v2 是连通的。 如果图中任

意一 对顶点都是连通的，则称此图为连通图。也就是说图中可以任意选两个点都可以到达。

强连通图 ：在 有向图 中，若在 每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径，也存在一条从 vj

到 vi 的路径，就称之为强连通图

例如：连通图：

强连通图：

图的概念和相关的转由名词较多，不可能一一记下来，但是经常使用的话这些概念还是能够了解个大概得，概念这种东西不用背，但是你得知道。

4. 图的存储结构

因为图中既有节点，又有边 ( 节点与节点之间的关系 ) ，因此， 在图的存储中，只需要保存：节点和 边关系即可 。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？---通过邻接矩阵或者邻接表来保存

4.1 邻接矩阵

因为节点与节点之间的关系就是连通与否，即为 0 或者 1 ，因此 邻接矩阵 ( 二维数组 ) 即是：先用一

个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系 。如有一个n*n的矩阵，那么数组arr[i][j]表示i顶点到j顶点边的值，如果不是直接相连，那就初始化为最初值，否则就是边的权值。

由于A和B/D是直接相连的，所以他们可以初始化为1.而A与C没有直接相邻，所以初始化为0.

这是对于无向图来说，他们是关于45度对角线对称的，而对于有向图来说就不是这样了。看下面例子：

对于有权值的边来说，如果两个点是连接的，那么就用权值表示，否则就表示无直接相连，用无穷大来表示。

4.2邻接表

邻接表：使用数组表示顶点的集合，使用链表表示边的关系。

1.无向图邻接表存储

A,B,C,D的下标分别是0,1,2,3.所以A顶点有两个相邻的顶点B和C. 链表中存的就是1,2

2.有向图邻接表存储

但是在后续我们只考虑出边表，不考虑入边表。

4.3 两者的优缺点分析

领接表的优点就是可以用比较少的时间，知道哪几个顶点是直接与我相连，而对于邻接矩阵来说不管相连多少都是O（N）--N为顶点的数量

缺点：他想要知道是否能A->C是否能够连通时，那么就必须要遍历一遍

对于邻接矩阵来说优点就是：想要知道A->C是否能够连通，那么只需要O（1）就够了。只需判断数组Arr[i][j]是否存在，存在那么就连通。

缺点就是：如果对于那种顶点很多，但是边很少的情况来说，矩阵就存储了大量的0元素，有点浪费空间。

5.图的模拟实现

在实现之前我们规定，用一个一位数组来存储顶点，二维矩阵则是存储的一位数组里面对应顶点的下标，由于后续需要通过顶点来找到下标，所以还需要一个哈希表来映射。

5.1 邻接矩阵模拟实现图

基本结构：

template<class V, class W, W int_MAX = INT_MAX, bool Direction = false>
class Graph
{
public://图的创建方法: 1. IO输入(不方便测试) 2. 样例写在文件中,读取文件 3. 手动添加边Graph(const V* a,size_t n){_vertex.reserve(n);for (int i = 0; i < n; i++){_vertex.push_back(a[i]);_index[a[i]] = i;}_edge.resize(n);for (int i = 0; i < n; i++)_edge[i].resize(n, int_MAX);}
private:vector<V> _vertex; //图的顶点集合vector<vector<W>> _edge;//图的边的集合unordered_map<V, int> _index;//存储顶点和它映射到vector的下标的关系
};

V表示的是顶点的类型，W表示的是权值的类型，Direction中false表示的是无向，而true表示的是有向，int_MAX表示的是初始化为无穷大。

在邻接矩阵里面我们需要实现的函数是：找顶点的下标的函数，然后添加边的函数。

代码如下：

//找到顶点对应的下标size_t GetIndex(const V& v){if (_index.find(v) == _index.end()){cout << "要添加的边的顶点不存在" << endl;return -1;}return _index[v];}void AddEdge(const V& src, const V& dest, const W& w)//向图中添加边(源点,目标点,以及权值){size_t srci = GetIndex(src);size_t desti = GetIndex(dest);_edge[srci][desti] = w;if (Direction == false) //这里判断的是有向图还是无向图_edge[desti][srci] = w;}

完整代码：

//邻接矩阵版本
template<class V, class W, W int_MAX = INT_MAX, bool Direction = false>
class Graph
{
public://图的创建方法: 1. IO输入(不方便测试) 2. 样例写在文件中,读取文件 3. 手动添加边Graph(const V* a,size_t n){_vertex.reserve(n);for (int i = 0; i < n; i++){_vertex.push_back(a[i]);_index[a[i]] = i;}_edge.resize(n);for (int i = 0; i < n; i++)_edge[i].resize(n, int_MAX);}//找到顶点对应的下标size_t GetIndex(const V& v){if (_index.find(v) == _index.end()){cout << "要添加的边的顶点不存在" << endl;return -1;}return _index[v];}void AddEdge(const V& src, const V& dest, const W& w)//向图中添加边(源点,目标点,以及权值){size_t srci = GetIndex(src);size_t desti = GetIndex(dest);_edge[srci][desti] = w;if (Direction == false)_edge[desti][srci] = w;}void Print(){//打印顶点for (int i = 0; i < _edge[0].size(); i++)cout << "[" << i << "]" << "->" << _vertex[i] << endl;cout << endl;//打印矩阵for (int i = 0; i < _edge[0].size(); i++){for (int j = 0; j < _edge[0].size(); j++){if (_edge[i][j] == int_MAX)cout << "* ";else cout << _edge[i][j] << " ";}cout << endl;}cout << endl;}
private:vector<V> _vertex; //图的顶点集合vector<vector<W>> _edge;//图的边的集合unordered_map<V, int> _index;//存储顶点和它映射到vector的下标的关系
};void TestGraph()
{Graph<char, int, -1, true> g("0123", 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();
}

输出结果如下：

5.2 邻接表的模拟实现

基本框架：

template <class W>struct LinkEdge{int _srcIndex;	//起始点下标int _dstIndex;	//要连接的下标W _w;			//权值LinkEdge* _next;    //下一个链接的边LinkEdge(const W& w):_srcIndex(-1),_dstIndex(-1),_w(w),_next(nullptr){}};
template <class V,class W,bool Direcation=false>class Table {public:typedef LinkEdge<W> Edge;Table(const V* ver,size_t n){//外部传进来几个顶点以及顶点的个数_ver.resize(n);for (int i = 0; i < n; i++){_ver[i] = ver[i];_umapIndex[ver[i]] = i;}//邻接表开辟好空间_Table.resize(n, nullptr);}private:vector<V> _ver;//用来存储顶点unordered_map<V, int> _umapIndex;//用来存储顶点、下标的映射关系vector<Edge*> _Table;//边的集合的临接表};

和邻接矩阵类似，需要知道下标函数和添加边的函数

template <class V,class W,bool Direcation=false>class Table {public://得到下标int GetIndex(const V& v){auto it = _umapIndex.find(v);if (it == _umapIndex.end()){cout << "这个值没有对应的下标，即查找下标出错" << endl;return -1;}else return _umapIndex[v];}//添加边进去void AddEdge(const V& src, const V& dst,const W& w){//先找到下标int srci = GetIndex(src);if (srci == -1) return;int dsti = GetIndex(dst);if (dsti == -1) return;//找到之后开始链接--头插法Edge* newedge = new Edge(w);newedge->_srcIndex = srci;newedge->_dstIndex = dsti;newedge->_next = _Table[srci];_Table[srci] = newedge;//判断有向还是无向图if (Direcation == false){Edge* newedge = new Edge(w);newedge->_srcIndex = dsti;newedge->_dstIndex = srci;newedge->_next = _Table[dsti];_Table[dsti] = newedge;}}};

整体代码：

template <class V,class W,bool Direcation=false>class Table {public:typedef LinkEdge<W> Edge;Table(const V* ver,size_t n){//外部传进来几个顶点以及顶点的个数_ver.resize(n);for (int i = 0; i < n; i++){_ver[i] = ver[i];_umapIndex[ver[i]] = i;}//邻接表开辟好空间_Table.resize(n, nullptr);}//得到下标int GetIndex(const V& v){auto it = _umapIndex.find(v);if (it == _umapIndex.end()){cout << "这个值没有对应的下标，即查找下标出错" << endl;return -1;}else return _umapIndex[v];}//添加边进去void AddEdge(const V& src, const V& dst,const W& w){//先找到下标int srci = GetIndex(src);if (srci == -1) return;int dsti = GetIndex(dst);if (dsti == -1) return;//找到之后开始链接--头插法Edge* newedge = new Edge(w);newedge->_srcIndex = srci;newedge->_dstIndex = dsti;newedge->_next = _Table[srci];_Table[srci] = newedge;//判断有向还是无向图if (Direcation == false){Edge* newedge = new Edge(w);newedge->_srcIndex = dsti;newedge->_dstIndex = srci;newedge->_next = _Table[dsti];_Table[dsti] = newedge;}}void Print(){//先打印下标映射关系for (size_t i = 0; i < _ver.size(); i++){cout << "[" << _ver[i] << "]" << ": " << i << endl;}//然后打印边for (size_t i = 0; i < _Table.size(); i++){cout << i << "->";Edge* cur = _Table[i];while (cur){cout << "[" << cur->_dstIndex <<"]" << "->";cur = cur->_next;}cout << endl;}}private:vector<V> _ver;//用来存储顶点unordered_map<V, int> _umapIndex;//用来存储顶点、下标的映射关系vector<Edge*> _Table;//边的集合的临接表};void TestGraph(){string a[] = { "张三", "李四", "王五", "赵六" };Table<string, int> g1(a, 4);g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.Print();}

6.总结

这里两种图的存储结构的模拟实现都进行了讲解，但是后面真正使用的更多的是在邻接矩阵的基础上，所以一定要非常熟练邻接矩阵的相关实现。且邻接矩阵也是为了后续的图的遍历、最小生成树和最短路径的算法打下基础。一定要好好掌握。