数据结构入门-图的基本概念与存储结构

前言

        图和树都是图论的内容，树是特殊的图。数据结构中的图论部分和离散数学有大量重叠，代码内容占少数，定义占多数，平时多看两眼可以帮助记忆。

图的定义

图是由顶点（vertex）的有穷非空集合和顶点之间的边（eage）的集合组成的。

通常记为G(V,E),其中G表示一个图，V是图G中顶点的集合，E是边的集合。

V(G)和E(G)通常分别表示图G的顶点和边集合。

注意：对于图这种数据结构，不允许没有顶点，但边集可以为空。

 无向图与有向图

V(G)={0,1,2,3}

E(G)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}

无向图边集用圆括号表示

V(G)={0,1,2}

E(G)={<0,1>,<1,2>,<1,0>}

有向图边集用尖括号表示 

边也称为弧，有向图的弧由弧尾指向弧头。

 简单图与多重图

限制一：图中不能有从顶点到其自身的边。

限制二：同一条边再图中不能出现两次或者两次以上。

不满足以上两条限制的图称为多重图。

 在数据结构的学习中，如果没有特殊提及，我们所学习的所有图都是指简单图。

完全图

 完全图：具有最多边数的图称为完全图。

对于一个具有n个顶点的无向完全图，边数量的最大值尾n(n-1)/2

对于一个具有n个顶点的有向完全图，边数量的最大值为n(n-1)

 

 路径和路径长度

路径：从一个顶点开始，经过一系列的边到达另外一个顶点形成的顶点序列。

路径长度：路径上边的条数。

回路(环)：起点和终点相同，路径{0，3，1，0}是一个回路(环)。

 

 简单路径

简单路径：如果路径中不出现相同的顶点，则称为简单路径。

简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

 顶点的度

度：对于无向图，顶点的度指的是与顶点相关联边的数目。

入度：在有向图中，对于顶点v，箭头指向v的边的数目。

出度：在有向图中，对于顶点v，从该顶点出发的边的数目。

 

 度与边的关系

在无向图中，假设具有n个顶点，e条边

图中所有顶点度之和等于边数的两倍

对于有向图，所有顶点的出度之和与入度之和相等，弧的数量也相等。

子图

图G的子图H，H满足V(H)是V(G)子集且E(H)是E(G)子集。

 

 连通图

连通：在无向图中，如果从顶点v到顶点w有路径，则称顶点v到顶点w是连通的。

如果对于图中任意两个顶点都是连通的，则称此图为连通图。

 连通分量

无向图中的极大连通子图称为连通分量。

连通分量为子图

子图为连通图

连通子图含有极大顶点数

具有极大顶点数的连通子图包含依附于这些顶点的所有边。

 

强连通图

强连通图：在有向图中，对于每一对顶点v和w，从v到w和从w到v都有路径，则称该有向图为强连通图。

有向图中顶点极大强连通子图称为有向图的强连通分量。

 

 生成树

生成树：指含有图中全部顶点的极小连通子树。

注意：包含所有顶点n，但只有足以构成一棵树的n-1条边。

 边的权和网

在一个图中，每条边可以标注上一个代表某种含义的数值，该数值称为这个边的权值网；边上带有权值的图，也称为带权图。

 图的存储结构

 邻接矩阵-无向

 将上面的图以两个数组的形式存储起来：

 

 在两个顶点之间，如果有连线，就用1表示，无连线就用0表示。

无向图的邻接矩阵具有按对角线对称的性质。

邻接矩阵-有向

 

 

 

 邻接矩阵-带权值

 

在带权图的边数组中，用∞符号来表示两个边之间没有关系，用权值来表示该边的权。 

邻接表-无向

 

 

 邻接表中用链表来表示每个顶点的关系，用数组下标来标记顶点，头节点是该顶点，链表节点中存储的数字是与该顶点相连的顶点下标。

邻接表-有向

 

 在这个邻接表中节点存储的都是出边的对应顶点，逆邻接表则存储入边的对应顶点。

逆邻接表

 

 十字链表

 

 tailvex表示弧尾，headvex表示弧头，headlink指向该节点被弧头链接的顶点的节点，tailink指向被弧尾链接的顶点的节点。

 如上图第一个链表的首节点中，0和3就代表从顶点V0指向顶点V3的一条边。

 在上述链表中，用横向链接的节点表示出边关系，用纵向链接的节点表示入边关系，横纵交错，构成十字链表。

邻接多重表

 

 ivex和jvex是某一条便连接的两个顶点的下标

ilink指同连接顶点ivex的下一条边

jlink指同连接顶点jvex的下一条边

 

 

先给出四个顶点的节点和五条边的节点。

 

按照每个顶点的顺序依次连接节点 。这样就解决了无向图的邻接表过于冗杂的问题。