图及其图的概念.doc

图及其图的概念
在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，图的应用极为广泛。如：电子线路分析、寻找最短路径、工程计划分析、统计力学、控制论等技术领域都把图结构作为解决问题的主要手段之一。
相关定义
（一）图
图G由两个集合V和E组成。V是一个有限的非空的顶点集合，E是边的集合。图1中G1、G2、G3就是三个图。

图1
图G1、G2中代表边的顶点偶数对是无序的，则称图G1、G2为无向图，边(Vi，Vj)和(Vj，Vi)代表的是同一条边。
图G3中代表边的顶点偶数对是有序的，则称图G3为有向图，有向图中的边又称为弧。弧(Vi，Vj)表示从顶点i指向顶点j，顶点Vi称为弧(Vi，Vj)的尾，Vj称为弧(Vi，Vj)的头。故有向图中(Vi，Vj)和(Vj，Vi)代表着两条不同的弧。
在一个有ｎ个顶点的无向图中，若每一个顶点和其它（ｎ-1）个顶点之间都有边相连，则共有ｎ(ｎ－1)/2条边。这是任何ｎ个顶点的无向图的最大边数。一个拥有ｎ(ｎ－1)/2条边的ｎ个顶点的无向图称为无向完全图。如图13.11中的G1是有4个顶点的无向完全图。类似地在有ｎ个顶点的有向图中，最多可能有ｎ（ｎ－１）条弧，具有ｎ（ｎ－１）条弧的ｎ个顶点的有向图称为有向完全图。
在一些实际应用问题中，图的边往往与具有一定意义的数相关，这种与图的边相关的数叫权，这个权，可以表示从一个顶点到另一个顶点的距离或花费的代价等等。我们称边拥有权的图为网。
（二）邻接
若(V1，V2)是E(G)中的一条边，则称顶点V1和V2为相邻接的顶点，而称边(V1，V2)是依附于顶点V1和V2的边。
例如，在图13.11的G2中，与V2顶点相邻接的顶点是V1、V4和V5。若(V1，V2)是有向图G中的一条弧，则称顶点V1邻接至顶点V2，顶点V2邻接至顶点V1，弧(V1，V2)依附于顶点V1和V2。
（三）度
依附于顶点的边的数目称为该顶点的度。有向图中，把以顶点V为头的弧的数目称作顶点V的入度，而把以V为尾的弧的数目称之为顶点V的出度，顶点V的出度与入度之和就是它的度。
（四）路径
在图G中，从顶点Vp到顶点Vq的路径是顶点序列(Vp，Vi1，Vi2，......，Vin，Vq)，且(Vp，Vi1)，(Vi1，Vi2)，......，(Vin，Vq)是E(G)中的边。
若G是有向图，则路径也是有向的，由弧(Vp，Vi1)，(Vi1，Vi2)，......，(Vin，Vq)组成。路径上的边数称为路径长度。在一条路径中，如果除了第一个顶点和最后一个顶点外，其余顶点都各不相同，则称这样的路径为简单路径。
例如，在图13.11中，由边(V1，V2)，(V2，V4)，(V4，V3)构成从顶点V1到顶点V3的路径可以写成顶点序列(V1，V2，V4，V3)。路径(V1，V2，V4，V3)和(V1，V2，V4，V2)都是长度为3的路径，显然，前者是一条简单的路径，而后者则不是。我们把第一个顶点和最后一个顶点相同的路径称为回路，若一个简单路径的第一个顶点和最后一个顶点相同，则称为简单回路。
图的存储结构
表示图的存储结构有多种形式，我们只介绍其中常用的两种，即邻接矩阵表示法和邻接表表示法。
（一）邻接矩阵表示法
若某图G有ｎ个顶点V1，V2，......，Vn，则其邻接矩阵是这样的一个ｎ阶方阵：
1(顶点Vi，Vj有相连)
A(i，j)＝{
0(顶点Vi，Vj不相连)
显然，无向图的邻接矩阵是对称的，因此，在赋值时只要对上三角矩阵(或下三角矩阵)赋值即可。而有向图的邻接矩阵不一定是对称的。
对于网的邻接矩阵可定义为：
Wij(顶点Vi，Vj有相连时的权值)
A(i，j)＝{
0(顶点Vi，Vj不相连)
采用邻接矩阵的方法来表示一个图，我们可以很容易地判定任意两个顶点之间是否有边相连，并容易求得各个顶点的度，但是所耗费的存储空间是十分大的--需要ｎ×ｎ个存储单元。当一个图的顶点数较多而边数较少时，这时对应的邻接矩阵为稀疏矩阵，这种存储结构浪费了许多存储单元，在这种情况下，也可采取图的另一种表示方法--邻接表表示法。
（二）邻接表表示法
这种表示法是为图中的每一个顶点Vi建立一个链表，即把邻接矩阵中的ｎ行表示成ｎ个链表。对于无向图，第i个链表是把图中与顶点Vi相邻接的所有顶点链接在一起，链表中的每个结点表示一条依附于顶点Vi的边（见图13.12(ａ)）。而有向图的第i个链表是把邻接自顶点Vi的所有顶点链接在一起，链表中的每个结点表示一条以顶点Vi为尾的弧（见图13.12(ｂ)）。链表的结构为，每个结点有两个域：
顶点域--用来表示与顶点Vi相邻接的顶点序号；
指针域--用来指向依附于顶点Vi的另一条边或弧。
对于网，结点中还需增加一个存放权值的域，每个链表都有一个起始结点，为