《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－7》由会员分享，可在线阅读，更多相关《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－7（49页珍藏版）》请在金锄头文库上搜索。
1、1,计算机软件技术基础,课件,第一章 数据结构,第二章 操作系统,第三章 软件工程,第四章 数据库,制作者：张选芳 Email: 电话:5182508,2,第一章 数据结构,第一单元,第二单元,第三单元,第四单元,第五单元,第六单元,第七单元,第八单元,3,图的基本概念,第七单元,第一章 数据结构,4,1.4.1 图的基本概念,图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合； E = (x, y) | x, y V 或 E = | x, y V & Path (x, y) 是顶点之间
2、关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。,图定义:,5,1.4.2有向图和无向图 1. 有向图(Directed Graph) 在有向图中，若图G中的每条边都是有方向的，顶点对是有序的。则称G为有向图,图1-59有向图G1,图1-60无向图G2,6,(1) 有向边的表示 在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。 弧(Arc) 有向边也称为弧(Arc)， 弧尾(Tail) 边的始点称为弧尾(Tail)， 弧头(Head) 终点称为弧头(Head)。 和是两条不同的有向边。,7,例: 表示一
3、条有向边，Vi是边的始点(起点)，Vj是边的终点。因此，和是两条不同的有向边。 (2) 有向图的表示：图157中的G1是一个有向图。该有向图G1的顶点集和边集分别为：V(G1)=A, B, C, D, E E(G1)=, , , , , ,图1-59 有向图G1,8,2.无向图(Undigraph) 在无向图中，若图G中的每条边都是没有方向的，则称G为无向图。如图160的无向图G2。顶点对(x, y)是无序的。 无向边的表示： 无向图中的边均是 顶点的无序对， 无序对通常用圆括号表示。 例: 无序对(Vi，Vj)和(Vj，Vi)表示同一条边。,9,(2) 无向图的表示：例如，对于图158的无向
4、图G2 ，其顶点集和边集分别为： V(G2)=A，B，C，D，E E(G2)=(A，B)，(A，E)，(C，A)， (C，D)，(C，E)，(E，D),图160的无向图G2。,注意： 在以后的讨论中，不考虑顶点到其自身的边。 即若(V1，V2)或是E(G)中的一条边，则要求V1V2。此外，不允许一条边在图中重复出现，即只讨论简单的图。,10,3图G的顶点数n和边数e的关系 (1)完全无向图 若G是无向图，则0en(n-1)/2。恰有n(n-1)/2条边的无向图称为完全无向图(Undirected Complete Graph)。 例: 图161的完全无向图G3。,图1-61完全无向图G3,11
5、,(2)完全有向图 若G是有向图，则0en(n-1)。恰有n(n-1)条边的有向图称为完全有向图(Directed Complete Graph)。 例: 如图162的完全有向图G4。 注意：完全图具有最多的边数。任意一对顶点间均有边相连。,图1-62完全有向图,12,4图的边和顶点的关系 (1)无向边和顶点关系： 若(Vi , Vj)是一条无向边, 则称顶点Vi和Vj互为邻接点(Adjacent), 或称Vi和Vj相邻接；并称(Vi, Vj)依附或关联(Incident)于顶点Vi和Vj, 或称(Vi，Vj)与顶点Vi和Vj相关联。 (2) 有向边和顶点关系： 若是一条有向边，则称顶点Vi邻
6、接到Vj，顶点Vj邻接于顶点Vi；并称边关联于Vi和Vj或称与顶点Vi和Vj相关联。,13,5顶点的度(Degree) (1)无向图中顶点v的度(Degree)： 一个顶点v的度是与它相关联的边的条数。记作TD(v)。,无向图,如图G1所示v3的 度是3。,(2)有向图顶点v的度(Degree)： 在有向图中, 顶点的度等于该顶点的入度与出度之和。,14,顶点 v 的入度 是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度 是以 v 为始点的有向边的条数, 记作 OD(v)。 例：图G2中顶点v1的入度: ID(v1) = 1 顶点v1的出度: OD(v1) = 2 度：T
7、D(v1) = ID(v1) + OD(v1) = 3,有向图,15,边与度的关系 另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有,16,1.4.3子图与路径 1.子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图,17,例:设V=v1，v2，v3，E=(vl，v2)，(v2，v4)，显然，V属于V(G3)，E属于E(G3)，但因为E中有序偶对(v2，v4)所关联的顶点v4不在V中，所以(V，E)不是图，也就不可能是G3的子图。,图1-61完全无向图,图1-62完全有向图,G3,18,2路径(Path) (1) 无向图的路
8、径： 在无向图G中，若存在一个顶点序列vp,vi1，vi2,，vim，vq，使得(vp，vi1)，(vi1，vi2)，(vim，vq)均属于E(G)，则称顶点vp到vq存在一条路径(Path)。,(2) 有向图的路径： 在有向图G中，路径也是有向的,它由E(G)中的有向边，组成。,19,(3) 路径长度： 路径长度定义为该路径上边的数目。 1.4.4连通图和连通分量 1. 顶点间的连通性 在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。,2.连通图 若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-necte
9、d Graph)。例如，图G2是连通图。,20,3. 连通分量 无向图G的极大连通子图称为G的连通分量(Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。,21,4强连通图 有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。,22,5强连通分量 有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。,V2,(a)有向图G,(b)有向图G的两个强连通分量,图1-63有向图及其强连通分量,23,1.4.5
10、图的存储结构,在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 A.edgenn，定义：,一邻接矩阵(Adjacency Matrix),24,在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。,25,26, 公式表示 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。,在无向图中,
11、 统计第 i 行 (列) 1 的个数可得顶点i 的度。,27,无向图的邻接表,二.邻接表 (Adjacency List),把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标 dest 和指向同一链表中下一个边结点的指针 link。,28,有向图的邻接表和逆邻接表,在有向图的邻接表中，第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。 在有向图的逆邻接表中，第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表。,29,链表中的结点类型的定义 struct node int vertex; /*ver
12、tex为顶点域*/ struct node* link; /*指向下一个邻接点的链域*/ 为了能够随机访问任一顶点的链表，可以在每个链表的表头设立一个结点，并以数组的形式存储这些结点，表头结点类型可定义如下：,30,struct tnode int data; /*data为数据域*/ struct node* link; /*链域指向与本顶点有边相连的第一个邻接点的结点*/ ,有向图G1,无向图G2,31,顶点序号, ,(c) 无向图G2的邻接表,data link,vertex link,32,顶点序号, ,(d) 有向图G1的邻接表,data link,vertex link,33,顶点
13、序号, ,(e) 有向图G1的邻接表,data link,vertex link,34,三.邻接多重表(Adjacency Multilist),在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。 无向图的情形 边结点的结构,其中，mark 是记录是否处理过的标记； ivex和jvex是依附于该边的两顶点位置。 ilink域是链接指针，指向下一条依附于顶点ivex的边；jlink也是链接指针，指向下一条依附于顶点jvex的边。需要时还可设置一个存放与该边相关的权值的域info。,35,顶点结点的结构,存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，da
14、ta 存放与该顶点相关的信息， firstdge是指示第一条依附于该顶点的边的指针。在邻接多重表中, 所有依附于同一个顶点的边都链接在同一个单链表中。 从顶点 i 出发, 可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。 邻接多重表的结构,36,三.邻接多重表(Adjacency Multilist),37,有向图的情形 在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表(十字链表)可把这两个表结合起来表示。 边结点的结构,其中，mark是处理标记；vertex1和vertex2指明该有向边始顶点和终顶点的位置。,38,path1是指向始顶点与该边相同
15、的下一条边的指针；path2是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域cost。 顶点结点的结构,每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员data存放与该顶点相关的信息，指针Firstin指示以该顶点为始顶点的入边表的第一条边，Firstout指示以该顶点为终顶点的出边表的第一条边。,39,邻接多重表的结构,40,1.4.6 图的遍历,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。,41,一深度优先搜索DFS(Depth_First Searth),深度优先搜索的示例,深度优先搜索过程 深度优先生成树,42, DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1
