首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


如树 T=A(B(D,E),C(#,F(H,I)))存储如表 1 所示: 表 6-1 树 T 的存储 1 7 A B C D E F G H I 2 4 0 0 0 8 0 0 0 3 5 6 0 7 9 0 0 0 8 9 2 3 4 5 6

第七章
【实验目的】

图的建立和应用

1.熟练掌握图的邻接矩阵和邻接表的存储方式; 2.实现图的一些基本运算,特别是深度遍历和广度遍历; 3.掌握以图为基础的一些常用算法,如最小生成树、拓扑排序、最短路径等。

第一节 知识准备
一、图的基本术语 图中数据元素称为顶点,数据元素之间的关系称之为边(或弧)。 1. 图:图 G 是由顶点和边两个有穷集合组成,记为 G=<V,E>。其中 V 是顶点的非空有穷集合;E 是边的 集合。设有两个图 G=<V,E>,G’=<V’,E’>,若有:V’ V 而且 E’ E,则称 G’是 G 的子图。 2. 图的种类 (1) 无向图:边是顶点的无序对,即(Vi,Vj)=(Vj,Vi)。特别有,当顶点数为 n,有 n(n-1)/2 条 边时,称为无向完全图。 (2) 有向图:边是顶点的有序对,即<Vi,Vj>≠<Vj,Vi>。此时,称边为有向边或弧。特别有,当顶点 数为 n,有 n(n-1)条边时,称为有向完全图。 (3) 网:边赋有权值的有向/无向图。 3.度与路径 (1) 入度:在有向图中,以顶点 V 为头的弧的数目,称为 V 的入度,记为 ID(V)。 (2) 出度:在有向图中,以顶点 V 为尾的弧的数目,称为 V 的出度,记为 OD(V)。 (3) 度:顶点 V 的度,在无向图中等于与 V 相关联的边的条数; (4) 在有向图中,等于 V 的入度和出度之和。 (5) 握手定律:在有 n 个顶点,e 条边或弧的图中,所有顶点的度数之和等于边数的 2 倍。 (6) 路径:顶点 Vi 到顶点 Vj 的路径是从 Vi 出发沿边或弧到达 Vj 所经过顶点序列。 (7) 回路:始顶点和终顶点相同的路径。 (8) 路径长度:路径上边弧或弧的数目。在网中,路径长度则为路径上边或弧的权值之和。 4.连通性 (1) 连通:在无向/有向图中,若顶点 Vi 和顶点 Vj 之间存在路径,则称 Vi 和 Vj 是连通的。 (2) 连通图:在无向图中,如果任意两个顶点之间都是连同的,则称该图为连通图。

(3) 强连通图:在有向图中,如果任意两个顶点都是连通的(任何两个顶点都是相互可达的),则称该有 向图是强连通图。 (4) 连通分量:无向图中,极大的连通子图。 (5) 强连通分量:有向图中,极大的强连通子图。 (6) 生成树:连通图的极小连通子图。它包含图中全部的 n 个顶点,只有 n-1 条边,并且,任加一条边 必构成回路。

二、图的存储结构 1.邻接矩阵:设图 G 有 n 个顶点,其邻接矩阵为一个如下定义的 n 阶方阵 A:

(1)无向图的邻接矩阵是以主对角线对称的矩阵,顶点 (2)在有向图中,顶点

的度是矩阵中第 i 行元素之和,即 ;

的出度为矩阵中第 i 行元素之和,即

顶点 的入度为矩阵中第 i 列元素之和,即 。 (3)网的邻接矩阵为:

其中, 是弧

或边

上的权值。

2.邻接表:由头结点和单链表两部分组成。每个顶点对应一个单链表,单链表中的节点表示依附于该顶点 的边(对有向图是以该顶点为尾的弧)。 有 n 个顶点,e 条边的无向图的邻接表需要 n 个头节点和 2e 个表节点。顶点 的度为第 i 个链表中的节点 数;而在有向图中,第 i 个链表中的节点数是顶点 的出度。 为了便于得到顶点的入度,可对每个顶点 建立一个以 为头的弧的链表,称为有向图的逆邻接表。

3.十字链表:由弧节点和顶点组成,每一条弧有一个弧节点,每一个顶点也有一个顶点节点。弧头相同的 弧节点在同一链表上,弧为相同的弧节点也在同一链表上,顶点节点作为它们的链头节点。用于存储有向 图。 4.邻接多重表:由边节点和顶点节点组成,每一条边有一个边节点,每一个顶点也有一个顶点节点。所有 依附于统一节点的边形成一个单链表,其链头节点为该顶点节点。用于存储无向图。 5.示例:对图 G1(见图 7-1)求出: (1) 各顶点的入度/出度 (2) 邻接矩阵存储表示 (3) 邻接表存储表示

(4) 逆邻接表表示 解:(1)各顶点的入度和出度 顶点号 入度 出度 3 0 1 1 2 3 1 1 2 2 3 1 2 3 3 4 5 6

(2)邻接矩阵 A

1

2

3

4

5

6

1 2 3 4 5 6

0 1 0 0 1 1

0 0 1 0 0 0

0 0 0 1 0 1

0 1 0 0 0 0

0 0 0 1 0 1

0 1 0 1 0 0

(3)邻接表

(4)逆邻接表

第二节 图的遍历

【问题描述】从图中某一个顶点出发访问图中其余顶点,每个顶点被且仅被访问一次的过程。称为图的遍 历,又称为图的搜索。它是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 【算法描述】 适合于无向/有向图的两种常用遍历图的方法是: 1. 深度优先搜索过程(DFS) (1) 基本思想: 假设初始状态是图中所有顶点未曾被访问, 则深度优先搜索可以从图中某个顶点 v 出发,

访问此顶点,然后依次从 v 的未被访问的邻接点出发深度优先遍历图,直至图中所有和 v 有路径相通的顶 点都被访问到,则另选图中一个未曾被访问的顶点做始点,重复上述过程,直至图中所有顶点都被访问到 为止。 (2) 由于深度优先搜索时,可选择同一深度邻接点中任何一个继续进行邻接点深度优先搜索,故其遍历 序列不是唯一的。我们以邻接表作为图的存储结构。 (3) 遍历过程示例分析: 通过对图 G2(见图 7-2)的深度优先搜索的描述,来了解对图的深度优先搜索工作原理。首先约定图 G2 的 邻接表按结点值从小到大排列。其搜索过程中栈的变化见图 7-3。 step Step Step Step Step 1: 2: 3: 4: 5: 若从顶点 1 开始,访问顶点 1,并将顶点 1 入栈; 顶点 1 的邻接点有 2 和 3,选择顶点 2 访问,并将 2 入栈。

顶点 2 的邻接点为 1、4、5;而 1 已访问,所以访问顶点 4,并将 4 入栈。 顶点 4 的邻接点为 2、8;而 1、2 已访问,访问顶点 8,并将 8 入栈。 顶点 8 的邻接点为 4、5、6、7,而顶点 4 已访问了, 图 7-2 图 G2

选择顶点 5 访问,并将 5 入栈。 Step 6 :顶点 5 的邻接点为 2、8,而顶点 2、8 已访问了,所以回退到顶点 8,将顶点 5 出栈。

3 7 5 6 6 6 8 8 8 8 8 8 4 4 4 4 4 4 4 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) 图 7-3 图 G2 的深度优先搜索时栈的变化

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐