毕业论文 图形结构的算法与设计.doc

图形结构是一种比树形结构更复杂的非线性结构。树形结构中的结点之间具有明显的层次关系，且每一层上的结点只能和上一层中的一个结点相关，但可能和下一层的多个结点相关。在图形结构中，任意两个结点之间都可能相关，即结点与结点之间的邻接关系可以是任意的。因此，图形结构可用来描述更加复杂的对象。
1 图的基本概念和存储结构
1.1 图的定义
图（Graph）是由非空的顶点集合V与描述顶点之间关系——边（或者弧）的集合E组成，其形式化定义为：
G=(V, E)
如果图G中的每一条边都是没有方向的，则称G为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“( )”表示。例如，顶点偶对(vi,vj)表示顶点vi和顶点vj相连的边，并且(vi,vj)与(vj,vi)表示同一条边。
如果图G中的每一条边都是有方向的，则称G为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“”表示。例如，顶点偶对表示从顶点vi指向顶点vj的一条有向边；其中，顶点vi称为有向边的起点，顶点vj称为有向边的终点。有向边也称为弧；对弧来说，vi为弧的起点，称为弧尾；vj为弧的终点，称为弧头。
图是一种复杂的数据结构，表现在不仅各顶点的度可以不同，而且顶点之间的逻辑关系也错综复杂。从图的定义可知：一个图的信息包括两个部分：图中顶点的信息以及描述顶点之间的关系——边或弧的信息。因此无论采取什么方法来建立图的存储结构，都要完整、准确地反映这两部分的信息。为适于用C语言描述，从本节起顶点序号由0开始，即图的顶点集的一般形式为：V={v0,v1,…,vn-1}。
下面介绍几种常用的图的存储结构。
1.2 邻接矩阵
所谓邻接矩阵存储结构，就是用一维数组存储图中顶点的信息，并用矩阵来表示图中各顶点之间的邻接关系。假定图G=(V, E)有n个顶点，即V={v0,v1,…,vn-1}，则表示G中各顶点相邻关系需用一个n×n的矩阵，且矩阵元素为：

A[i][j]=

若G是带权图（网），则邻接矩阵可定义为：

A[i][j]=

其中，wij表示(vi,vj)或上的权值；∞则为计算机上所允许的大于所有边上权值的数值。无向图的邻接矩阵表示如图7-6所示。


图7-6 无向图及邻接矩阵表示
有向图的邻接矩阵表示如图7-7所示。