前面已经介绍了两种基本的数据结构线性表和树.doc

PAGE PAGE 40 第7章 图 前面已经介绍了两种基本的数据结构：线性表和树。 线性表是一种线性结构，除了第一个元素（首元）和最后一个元素（尾元）外，每个数据元素都只有一个前趋元素和后继元素。 树是一种非线性结构，数据元素（结点）之间存在父子关系。除根结点外，每个结点有且仅有一个双亲结点（前趋），但却可以有零个或多个孩子结点（后继）。显然，树结构结点之间具有层次关系，一个结点可以和下一层的若干个结点相关，但只能和上一层的一个结点相关。 本章讨论的图结构是一种比树更为一般且更为复杂的非线性结构。在图结构中，数据元素（顶点）之间的关系是任意的，每个结点的前趋和后继不再加以限制，即每个顶点都可以和其它任何顶点相关。图结构也称为网状结构，而树结构可以看作是图的一种特殊形式。 本章先介绍图的概念，然后讨论图的各种存储表示以及图的几个典型应用问题。 7.1 图的基本概念 7.1.1 图的定义及运算 1)·图的定义 图（graph）是由两个集合V和E所限定的一种数据结构，记作 G=(V，E) 其中：V是构成图的顶点的非空有限集, E是表示顶点之间关系的边的集合。 在实际图的应用中，可能会同时接触若干个图，为了区别不同图的顶点集和边集，常常将图记作G=(V(G)，E(V))。 2) 图的运算 对图可以进行下述各种 操作: (1) CreateGraph(G，V，E): 根据顶点集V和边集E创建图G. (2) DestroyGraph(G): 销毁图G. (3) FirstAdjVex(G，v): 求图G中顶点v的第一个邻接顶点. (4) NextAdjVex(G，v，w): 求图G中顶点v的相对于其邻接顶点w的下一个邻接顶点. (5) InsertVex(G，v): 在图G中插入顶点v. (6) DeleteVex(G，v): 在图G中删除顶点v及其与v相关的边. (7) InsertArc(G，v，w): 在图G中插入边（v，w）或v，w. (8) DeletArc(G，v，w): 在图G中删除边（v，w）或v，w. (9) DFSTraverse(G，v): 从图G的v顶点出发，深度优先遍历图. (10) BFSTraverse(G，v): 从图G的v顶点出发，广度优先遍历图. 7.1.2 图的基本术语 * 图结构中的数据元素为顶点（Vertex），在图的逻辑表示中，常常用一个小圆圈表示。往往在圆圈内标出顶点的值或者是人为给它指定的编号（该编号有时也称为顶点在图中的位置）以区别不同的顶点。在图的实际应用中，除在顶点内标注顶点值外，另外还标注上顶点的编号，称为双重标记法。 * 当两个顶点间存在关系时，用一条直线段（或曲线段）将这两个顶点连接起来，且称该线段为边（edge）。图中的边可以用顶点对表示。 * 如果顶点对是无序的，则称这样的边为无向边（edge）； * 如果顶点对是有序的，则称这样的边为有向边或弧（arc）。 例如，如果顶点i和顶点j之间存在一条无向边，则用（i，j）表示；而如果顶点i和顶点j之间有一条有向边，则用i，j表示，称i为有向边的弧尾（始点），j称为有向边的弧头（终点）。为了表示顶点对的有序性，往往用带箭头的线段表示，而无向边用不带箭头的线段表示。应该注意的是：（i，j）=（j，i），但i，j≠j，i。 * 由顶点集和无向边集构成的图称为无向图（undirected graph）， * 而由顶点集和有向边集构成的图称为有向图（directed graph）。 i i j 弧尾(始点) 弧头(终点) 附注： G1 3 1 2 4 5 1 2 3 4 G3 G2 4 1 2 3 1 2 3 G4 图7.1 图的示例 E(G1)={(1,2)，(1,3)，(2,3)，(3,4)，(3,5)，(4,5)}E(G2)={(1,2)，(1,3)，(1,4)，(2,3)，(2,4)，(3,4)}E(G3)={1,3，2,1，2,4，3,2，4,1，4,3}E(G4)={1,2，2,1，2,3} E(G1)={(1,2)，(1,3)，(2,3)，(3,4)，(3,5)，(4,5)} E(G2)={(1,2)，(1,3)，(1,4)，(2,3)，(2,4)，(3,4)} E(G3)={1,3，2,1，2,4，3,2，4,1，4,3} E(G4)={1,2，2,1，2,3} V(G1)={1,2,3,4,5}， V(G2)={1,2,3,4}， V(G3)={1,2,3,4}， V(G4)={1,2,3}， * 显然，n个顶点的无向图最多有n(n-1)/2条边，即任意两个顶点之间都有一条边。称具有n个顶点且有n(n-1)/2条边