6.1 图的基本概念
图作为一种非线性数据结构，被广泛应用于多个技术领域，诸如系统工程、化学分斩、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决问题的数学手段之一。在离散数学中侧重于对图的理论进行系统的研究。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。
在图中，数据元素之间是多对多关系，因此图用于表达数据元素之间存在着的复杂关系，这种关系称为网状结构关系。实际上，前面讨论的线性表和树都可看成是简单的图。本章介绍图的基本概念、存储结构和相关算法的实现过程。
本章主要内容
& 图的定义、特性和相关的概念
& 图的存储结构
& 图的遍历算法
& 最小生成树的算法
& 图最短距离的算法和拓扑排序方法
& 图关键路径的求法
6.1 图的基本概念
图结构与表结构和树结构的不同表现在节点之间的关系上，线性表中节点之间的关系是一对一的，即每个节点仅有一个前驱和一个后继（若存在前驱或后继时）；树是按分层关系组织的结构，树结构中节点之间的关系是一对多，即一个双亲可以有多个孩于，每个孩子节点仅有一个双亲；对于图结构，图中顶点之间的关系可以是多对多，即一顶点和其他顶点间的关系是任意的，可以有关也可以无关。图是一种比较复杂的非线性数据结构。
6.1.1 图的定义
图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的集合组成，它可以形式化地定义为：
G=(V,E)
V={vi | vi?VertexType }
E={<vi,vj> | vi,vj?V∧P(vi,vj) }
其中，G表示一个图；V是图G中的顶点集合；E是V中顶点偶对的有限集。这些顶点偶对也称为边，VertexType是用于描述顶点的类型，类似于以前使用的ElemType，集合E中P(vi,vj)的含义是：对于有向图P(vi,vj)表示顶点vi和顶点vj之间存在一条从vi到vj的边，通常用<vi,vj>表示；对于无向图P(vi,vj)表示顶点vi和顶点vj之间存在一条从vi到vj的边和一条从vj到vi的边，通常用(vi,vj)表示。
通常，V(G)和E(G)分别表示图G的顶点集合和边集合。E(G)也可以为空集。若E(G)为空，则图G只有顶点而没有边。
【例6-1】有一个图G1=(V1,E1)，其中：
V1={0,1,2,3,4}
E1={(0,1),(1,2),(2,3),(3,4),(2,4),(0,3)}
有另一个图G2=(V2,E2)，其中：
V2={0,1,2,3,4}
E2={<0,1>,<1,2>,<1,3>,<2,4>,<0,4>,<4,3>,<3,2>}
画出这两个图的逻辑结构。
解：它们的逻辑结构如图6-1所示，从中看到图G1是无向图，图G2是有向图。
图6-1 G1和G2的逻辑结构
6.1.2 图的基本术语
· 顶点（Vertex）：图6-2中的圆圈称为顶点。
· 边（Edge）：图6-2中的每个顶点之间的连线称为边。
· 无向图（Undirected Graph）：在边上没有箭头的图称为无向图，如图6-2中G1和G2为无向图。
· 有向图（Directed Graph）：在边上有箭头的图称为有向图，如图6-2中G3为有向图。
· 图（Graph）：图是由所有顶点和所有边组合而成的，以G=(V,E)表示。在无向图中(V1,V2)和(V2,V1)代表相同的边，但在有向图中<V2,V1>和<V1,V2>是不一样的边。在有向图中的<V1,V2>，V1表示边的弧头（Head）而V2表示边的弧尾（Tail）。
在图6-2中，V(G1)={1,2,3,4}；E(G1)={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}；V(G2)={1,2,3,4, 5,6,7}；E(G2)={(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)}；V(G3)={1,2,3}；E(G3)={<1,2>,<2,3>,<3,2>}。
图6-2 图结构示意图
· 多重图（Mutigraph）：假如两个顶点有多条相同的边，则称之为多重图，而不是图形。如图6-2中的G4。
· 完全图（Complete Graph）：在n个顶点的无向图中，假如有n(n-1)/2个边，则这样的图称为完全图。如图6-2中的G1是完全图，其余都不是（因为G1有4(4-1)/2=6个边）。
· 邻接（Adjacent）：在图的某一边(V1,V2)中，称顶点V1与顶点V2是邻接的，但在有向图中称<V1,V2>为V1是邻接到V2或V2邻接自V1。
· 依附（Incident）：在图6-2中，顶点V1和顶点V2是邻接的，而边(V1,V2)依附在顶点V1与顶点V2上。可以发现在G3中依附在顶点V2的边有<1,2>、<2,3>及<3,2>。
· 子图（Subgraph）：假设V(G') V(G)及E(G') E(G)，则称G'是G的子图。如图6-3是图6-2中G1的部分子图，图6-4是图6-2中G3的部分子图。
（a） （b） （c） （d）
图6-3 图6-2中G1的部分子图
（a） （b） （c） （d）
图6-4 图6-2中G3的部分子图
· 路径（Path）：在图G中，从顶点Vp到顶点Vq的路径是指一系列的顶点Vp、Vi1、Vi2、…、Vin、Vq，其中(Vp,Vi1)、(Vi1,Vi2)、…、(Vin,Vq)是E(G)上的边。假如G'是有向图，则<Vp,Vi1>、<Vi1,Vi2>、…、<Vin,Vq>是E(G')上的边，故一条路径是由一个或一个以上的边所组成的。
· 长度（Length）：一条路径上的长度是指该路径上所有边的数目。
· 简单路径（Simple Path）：除头尾顶点之外，其余顶点都在不相同的路径上。如图6-2中，G1的两条路径1、2、4、3和1、2、4、2，其长度都为3，但前者是简单路径，而后者不是简单路径。
· 回路或环（Cycle）：回路或环是指第一个顶点和最后一个顶点相同的简单路径，如图6-2中，G1的1、2、3、1或G3的1、2、1。
· 连通（Connected）：在一个图G中，如果有一条路径从V1到V2，那么就说V1与V2是连通的。如果V(G)中的每一对不同的顶点Vi、Vj都有一条由Vi到Vj的路径，则称该图是连通的。如图6-5中的G5不是连通的（因为G1与G2无法连接起来）。
图6-5 G5示意图
· 连通分量（Connected Component）：或称分量（Component）是指该图中最大的连通子图（Maximal Connected Subgraph），如图6-5中的G5有两个分量G1和G2。
|
图6-6 G3的强连通分量
|
· 强连通分量（Strongly Connected Component）：是指一个强连通最大子图。图6-2中G3有两个强连通分量，如图6-6所示。
· 度（Degree）：依附在顶点的边数。如图6-2中G1的顶点1度为3。若为有向图，则其度为入度与出度之和。
· 入度（In-degree）：顶点V的入度是指以V为终点（即箭头指向V）的边数，如图6-2中G3顶点2的入度为2，而顶点3的入度为1。
· 出度（Out-degree）：顶点V的出度是以V为起点的边数，如图6-2中G3中顶点2的出度为1，而顶点1和3的出度为1。