第二章基本数据结构及其运算精品.ppt

结点的出度、入度和度；图的度 在图中，一个结点的后件个数称为该结点的出度；其前件 个数称为该结点的入度；一个结点的出度与入度之和称为该结 点的度 图中结点的最大度称为该图的度 无向图无出度与入度之分，只有度(与它相连的边的数目) 连通图：G为无向图时若每一对顶点之间都有路径，则称G为连 通图。 G为有向图时若每一对顶点u和v之间都存在v到 u及u到v的路径则称该图为有向连通图，简称强连通图 连通分量:一个连通子图称为连通分量 V5 V1 V2 V3 V4 V6 V1 V2 V6 V3 V5 V4 无向图G1是非连通图,G1有两个连 通分量。 V5 V1 V2 V3 V4 V6 V1 V2 V6 V3 V5 V4 有向图G2不是强连通图，G2有 三个连通分量。 2.6.2 图的存储结构 1、关联矩阵(邻接矩阵) 设图G=(D,R)有n个结点,编号为d1,d2,…dn,为存储图G,可用一个长度为n的一维数组D(1:n)来存储图G中各结点信息,再用一个二维数组R(1:n,1:n)来存储图G中各结点的关联情况,它反映了各结点之间的关系,R称为关联矩阵,它的值为:。 由定义可看出，无向图的关联矩阵是对称的， (di,di)∈R，(dj,di) ∈R 对无向图只需存储其上或下三角矩阵，需n(n+1)/2大的空间 R[ i, j] = 1 (di,dj)?R 0 (di,dj)?R A1 = A2 = V5 V1 V2 V3 V4 例: V4 V1 V2 V3 V5 V6 由关联矩阵可很方便地判断图中任意两个结点之间是否 有边相连，也可很方便求出各结点的度 2、求值矩阵 一个图中两顶点之间往往还有关联两顶点的求值运算，我们把它称为求值函数，例如在交通图中，两顶点表示城市，邻接(关联）矩阵表示交通连接关系，求值函数就是两城市间交通里程。 V5 V1 V2 V3 V4 45 25 74 61 58 同样，我们可以用一个求值矩阵来表示它。相邻边矩阵元为对应里程或运费，无相邻关系矩阵元为-1。 显然，求值矩阵与邻接(关联）矩阵一样，只是对应的矩阵元表示的是求值函数值。如图： V1 = 0 61 -1 -1 -1 61 0 74 -1 -1 -1 74 0 58 25 -1 -1 58 0 45 -1 -1 25 45 0 3、图的邻接表存储结构 邻接表是一种链式存储结构,在这种存储结构中对应于图中每一个结点di(i=1,2,3,…,n)构造一个单链表,用以连接di的所有后件，如为有值图，再加一个域存储相应边的权值: 指向di的下一个邻接点的指针 存储di到dj这条边的权值 顶点di的某个邻接点dj的相关信息:如位置编号等 V 1 V 2 V 3 V 5 V 6 V 4 A B C D E 1 2 5 3 4 6 例： 2 A 3 C 4 B ? 1 A ? 1 C 1 B ? 3 D 5 E ^ 6 E ? 5 D ? 所有结点按顺序放在一个顺序存储空间中，它有两个域，一个数据域，用于存放结点的相关信息，一个指针域，用于存放由该结点的所有后件形成的链，其结构为： V 1 V 2 V 3 V 5 V 6 V 4 A B C D E 1 2 5 3 4 6 例： 2 A 3 C 4 B ? 1 A ? 1 C 1 B ? 3 D 5 E ^ 6 E ? 5 D ? 1 2 3 4 5 6 指向di邻接点链表的指针 存储结点di的相关信息 算法2.29 图邻接表的构造 PROCEDURE CREATGP (D, n) 定义 DATA (1:n), LINK (1:n) FOR k=1 TO n DO { DATA (k)=D[k] LINK (k)=0 INPUT m, v WHILE (m=0) DO { NEW (p) NUM (p) =m VAL (p) =v NEXT (p) =LINK (k) LINK (k)=p INPUT m, v } } RETURN 1 2 3 4 5 6 2 A 3 C 4 B ? 1 A ? 1 C 1 B ? 3 D 5 E ^ 6 E ? 5 D ? DATA LINK NUM VAL NEXT 对无向图G1, D[k]= {