图的算法.docVIP

数据结构 图 ??????????????????????? 图 1.3-1 在线性结构中每个元素只有一个前趋和一个后续，而图 1.3-1中的各个图则与之不同，它是一种较为复杂的非线性数据结构，在图结构中的任意两个元素之间都可能相互联系，即每个元素都可能有多个前趋或多个后续。图作为一种数据结构，通常又可被定义为： graph=(V， E)或 G=(V， E)，即一个图是由顶点的集合 V和边的集合 E组成。 在图 1.3-1中 ⑴图中的边没有方向，这类图称为无向图 (undirected graph)。在记录无向图时， (v 1， v 2 )等价于 (v 2， v 1)。 在图 1.3-1中 ⑵图中的边上有一个箭头，它表示边的方向，这类图称为有向图 (directed graph)。在记录有向图时， v 1， v 2 与 v 2， v 1 是两条不同的边。 图 1.3-1中 ⑴图的顶点集合为： V ＝｛ v 1， v 2， v 3， v 4｝ 边集合为： E ＝｛（ v 1， v 2），（ v 1， v 3），（ v 2， v 3），（ v 2， v 4），（ v 3， v 4）｝ 图 1.3-1中 ⑵图的顶点集合为： V ＝｛ v 1， v 2， v 3， v 4｝ 边集合为： E ＝｛ v 1， v 2 ， v 1， v 3 ， v 1， v 4 ， v 2， v 1 ， v 4， v 2 } 2 ．图的常用术语 环 (cycle)：图 1.3-1中 ⑶图中的 v 1点本身也有边相连，这种边称为环。 有限图：顶点与边数均为有限的图，如图 1.3-1中的三个图均属于有限图。 简单图：没有环且每两个顶点间最多只有一条边相连的图，如图 1.3-1中的 ⑴图。 邻接与关联：当（ v 1， v 2） ∈E，或 v 1， v 2 ∈E，即 v 1， v 2间有边相连时，则称 v 1和 v 2是相邻的，它们互为邻接点（ adjacent），同时称（ v 1， v 2）或 v 1， v 2 是与顶点 v 1、 v 2相关联的边。 顶点的度数 (degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。图 1.3-1中 ⑴、 ⑵图的各顶点的度见下表： 顶点 v 1 v 2 v 3 v 4 图 2 3 3 2 图 4 3 1 2 顶点 v 1 v 2 v 3 v 4 入度 1 2 1 1 出度 3 1 0 1 ??????????? 图 1.3-2 二、图的存储 图的最常见的存储方式是用邻接矩阵和邻接表。 1. 　邻接矩阵存储 ⑴ 邻接矩阵 邻接矩阵 (Adjacency Matrix)是表示顶点间邻接关系的矩阵。在图的邻接矩阵表示法中通常用一个邻接矩阵表示顶点间的相邻关系，另外用一个顺序表来存储顶点信息。 具有 n个顶点的图 G=(V， E)的邻接矩阵可以定义为： 图 1.3-1中 ⑴图和 ⑵图的邻接矩阵表示为： ? 带权图的邻接矩阵可以定义为： 图 1.3-2邻接矩阵表示为： ⑵ 建立已知图的邻接矩阵 如要建立图 1.3-1中 ⑴、 ⑵的已知图，则可用常量数组直接说明如下： const ?graph1:array[1..4,1..4] of integer=((0,1,1,0),(1,0,1,1),(1,1,0,1),(0,1,1,0)); graph2:array[1..4,1..4] of integer=((0,1,1,1),(1,0,0,0),(0,0,0,0),(0,1,0,0)); 同样图 1.3-2中的图也可用常量数组直接说明如下： const? graph3:array[1..4,1..4] of integer=((0,3,4,0),(3,0,9,2),(4,9,0,6),(0,2,6,0)); ⑶ 建立任意带权无向图的邻接矩阵 程序如下： Program? adjmatrix(input,output); var? vi,vj,vn,ei,en,wn:integer; graph:array[1..20,1..20] of integer; Begin ???? read(vn,en);? { 读入顶点数和边数 } for vi:=1 to vn do ?????? for vj:=1 to vn do ????????????? graph[vi,vj]:=0; for ei:=1 to en do begin ?????? read(vi,vj,wn);? { 读入每条边的两个顶点及边上的