3.5 图

3.5.1 图的定义

一个图G (Graph) 是由两个集合：V和E所组成的，V是有限的非空顶点(Vertex) 集合，E是用顶点表示的边(Edge) 集合，图G的顶点集和边集分别记为V (G) 和E (G)，而将图G记作G=(V, E)。

可以看出，一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。

在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。

3.5.2 图的相关概念

有向图：图中每条边都是有方向的。从顶点vi到顶点vj表示为<vi,vj>，而从顶点v到顶点v表示为<vj,vi>。有向边也称为弧。起点称为弧尾，终点称为弧头。（<vi,vj> ≠ <vj,vi>）

上面有向图a的顶点集合为：V(a)={1,2,3,4}
边的集合为：E(a)={<1,2>,<1,3>,<4,2>,<1,4>,<4,1>}

无向图：图中每条边都是无方向的。顶点vi和vj之间的边用(vi,vj)表示。在无向图中，(vi,vj) 和(vj, vi)表示的是同一条边 。
 

上面无向图b的顶点集合为：V(b)={1,2,3,4,5}
边的集合为：E(b)={(1,2),(1,3),(1,4),(2,3),(3,4),(3,5),(4,5)} 

完全图：若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图共有n*(n-1)/2条边，类似地，有n个顶点的有向完全图中弧的数目为n*(n-1)，即任意两个不同顶点之间都存在方向相反的两条弧。

度：顶点v的度是指关联于该顶点的边的数目，记作D(v)。若G为有向图，顶点的度表示该顶点的入度和出度之和。

入度和出度：顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为ID(y)和OD(v)。

例如，图3-22 (a)中，顶点1, 2, 3, 4的入度分别为1, 2, 1, 1，出度分别为3, 0, 0, 2。图3-22(b)中，顶点1,2,3,4,5的度分别为3,2,4,3,2。

子图：若有两个图G=(V,E)和G'=(V',E'),如果V'是V的子集且E'是E的子集 ,则称G'为G的子图。

连通图：在无向图G中，若从顶点vi到顶点vj有路径,则称顶点vi和顶点vj是连通的。如果无向图G中任意两个顶点都是连通的，则称其为连通图。图 (b)所示的无向图是连通图。（Tip：如果两个顶点虽然没有直接连通，但是它们通过其他顶点的路径间接连接，则称它们是间接连通的。在图论中，如果存在一条路径可以从一个顶点到另一个顶点，即使这条路径经过其他顶点，那么这两个顶点就是连通的）by chatgpt.

强连通图：在有向图G中，如果对于每一对顶点Vi, Vj∈V且Vi不等于Vj，从顶点Vi到顶点Vj和从顶点Vj到顶点Vi都存在路径，则称图G为强连通图。图 (a) 所示的有向图不是强连通图。以顶点1和顶点3为例，顶点1至顶点3存在路径，而顶点3至顶点1没有路径。

网：边(或弧)具有权值的图称为网。

3.5.3 图的存储结构

（1）邻接矩阵表示法

邻接矩阵表示法利用一个矩阵来表示图中顶点之间的关系。对于具有n个顶点的图G=(V,E)来说，其邻接矩阵是一个n阶方阵，且满足:

 

网(带有权值的图)的邻接矩阵的表示：

 

（2）邻接链表表示法

邻接链表是为图的每一个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的表(对于有向图是以vi为尾的弧)。

邻接链表中的表节点有表节点和表头节点两种类型：

这些表头结点通常以顺序结构的形式存储，以便随机访问任一顶点及其邻接表。 

显然，对于有n个顶点、e条边的无向图来说，其邻接链表需要n个头结点和2e个表结点，下如图所示。对于无向图的邻接链表，顶点vi的度恰为第i个邻接链表中表结点的数目。

下图中，图(b)是图(a)所示有向图的邻接表。从中可以看出，由于第i个邻接链表中表结点的数目只是顶点Vi的出度，因此必须逐个扫描每个顶点的邻接表，才能求出一个顶点的入度。为此，可以建立一个有向图的逆邻接链表，如图(c)所示。

带权值的网的邻接链表表示法：