图知识（全面）

 

目录

转载 https://blog.csdn.net/luobo140716/article/details/51695264

图

无向边

有向边

简单图

无向完全图

有向完全图：

稀疏图和稠密图：

子图的概念：

连通图

图的存储结构

邻接矩阵（无向图）

邻接表（无向图）

邻接表（网）

十字链表

链接多重表

边集数组

图的遍历

图

是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是图G中顶点的集合,E是图G中边的集合。

线性表中我们把数据元素叫做元素，树中叫结点，在图中数据元素我们称之为顶点（Vertex）。

线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在咱国内大部分的教材中强调顶点集合V要有穷非空。

线性表中相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

无向边

若顶点Vi到Vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶（Vi，Vj）来表示。

上图G1是一个无向图，G1={V1，E1}，其中

-V1={A,B,C,D}，

-E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

有向边

若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶来表示，Vi称为弧尾，Vj称为弧头。

上图G2是一个无向图，G2={V2，E2}，其中

-V2={A,B,C,D}，

-E2={,,,}

简单图

在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

无向完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有N个顶点的无向完全图有n*（n-1）/2条边。

有向完全图：

在有向图中，如果任意两个顶点之间都存在方向护卫相反的两条弧，则称该图为有向完全图，含有n个顶点的有向完全图有n*（n-1）条边。

稀疏图和稠密图：

相对而言，通常认为边或弧数小于n*logn（n是顶点个数）的图称为稀疏图，反之为稠密图。

有些图的边或弧带有与它相关的数字，这种与图的边或弧相关的数叫做权（weight），带权的图通常称为网。

子图的概念：

 

图的顶点与边之间的关系

对于无向图G=（V,G），如果边（V1,V2）属于E，则称顶点V1和V2互为邻接点，即V1和V2相连接。变（V1,V2）依附于顶点V1和V2,或者说边（V1,V2）

与顶点V1和V2相关联。

顶点V的度适合V相关联的边的数目，记为TD（V）如下图，顶点A和B互为邻接点，边（A,B）依附于顶点A与B上，顶点A的度为3.

对于有向图G=（V,E），如果有属于E，则称顶点V1邻接到顶点V2，顶点V2链接自顶点V1.

以顶点V为头的弧的数目称为V的入度，记为ID（V），以V为尾的数目称为V的出度。记为OD（V），因此顶点V的度为TD（V）=ID（V）+OD(V).

下图顶点A的入度为2，出度是1，所以顶点A的度是3.

无向图G=（V,E）中从顶点V1到顶点V2的路径。

下图用红线列举了从顶点B到顶点D的四种不同路径：

如果G是有向图，则路径也是有向的。

修用红线列举顶点B到顶点D的两种路径，而顶点A到顶点B就不存在路径啦：

路径的长度是路径上的边或弧的数目，

第一个顶点到最后一个顶点相同的路径称为回路或环。

序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简答环。下图左侧是简单环，右侧不是简单环。

连通图

在无向图G中，如果从顶点V1到顶点V2有路径，则称V1和V2是连通的，如果对于途中任意两个顶点Vi和Vj都是连通的，则称G是连通图。下图左侧不是连通图，右侧是连通图。

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

注意以下概念：

-首先要是子图，并且子图是要连通的。

-连通子图含有极大顶点数。

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

在有向图G中，如果对于每一对Vi到Vj都存在路径，则称G是强连通图。

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

下图左侧并不是强连通图，右侧是。并且右侧是左侧的极大强连通子图，也是左侧的强连通分量。

最后我们再来看连通图的生成树定义：

所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。

如果一个有向图恰有一个顶点入度为0，其余顶点的入度为1，则是一棵有向树。

图的存储结构

图的存储结构相比较线性表与树来说就复杂很多。我们回顾与Ixia，对于线性表来说，是一对一的关系， 所以用数组或者链表均可简单存放。树结构是一对多的关系，所以我们要将数组和链表的特性结合在一起才能更好的存放，。

那么我们的图，是多对多的情况，另外图上的任何一个顶点都可以被看做是第一个顶点，任一顶点的邻接点之间也不存在次序关系。

因为任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系（内存物理位置是线性的，图的元素关系是平面的）。

如果用多重链表来描述是可以做到，但在几节课前的树章节我们已经讨论过，纯粹用多重链表导致的浪费是无法想象的（如果各个顶点的度数相差太大，就会造成巨大的浪费）。

所幸，前辈们已经帮我们想好了出路，我们接下来会谈吐的五种不同的存储结构：

邻接矩阵（无向图）

考虑到图是由顶点和边或弧两部分组成，合在一起比较困难，那就是很自然地考虑到分为两个结构来分别存储。

顶点因为不区分大小，主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点和顶点之间的关系，一维数组就肯定搞不定了，那我们不妨考虑用一个二维数组来存储。

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

我们可以设置两个数组，顶点数组为verTex[4] = {V0，V1，V2，V3};边数组arc[4][4]为对称矩阵（0表示不存在顶点间的边，1表示顶点间存在边）

对称矩阵：所谓对称矩阵就是n阶矩阵的元满足a[i][j] =a[j][i]（0