数据结构及应用算法教程(修订版) 数据结构_第7章_图和广义表.ppt
《数据结构及应用算法教程(修订版) 数据结构_第7章_图和广义表.ppt》由会员分享,可在线阅读,更多相关《数据结构及应用算法教程(修订版) 数据结构_第7章_图和广义表.ppt(157页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、7.1 图的定义和术语 7.2 图的存储表示 7.3 图的遍历 7.4 图的连通性问题 7.5 单源最短路径 7.6 拓扑排序 7.7 关键路径 7.8 广义表,主要内容,图是一种比线性表和树都复杂的数据结构。 在线性表中每个元素(除了开始和结束)只有一个直接的前驱和一个直接的后继; 在树型结构中,元素之间有着明显的层次关系,而每一层元素都只与它临近层上的元素有关系,而且是上层元素和下层的多个元素有关系; 在图结构中,结点之间的关系是任意的,图中任意两个元素之间都可能有关系。,7.1 图的定义和术语 1. 图的结构定义 (1)定义 图(graph)是由一个顶点(vertex)集V和一个弧(ar
2、c)集E构成的数据结构。通常记作:G = (V , E ) G表示一个图,图中的顶点集V为数据结构中的数据元素集合,弧集E是定义在顶点集合上的一个关系集合。 (2)表示(描述) 有向图:若图中的每条弧都是有方向的,则称为有向图。在有向图中,一条弧是由两个顶点组成的有序对,通常用表示。,例如:表示一条有向边, v是边的始点,w是边的终点,故是从v到w的一条弧,并称w为弧头,v为弧尾。 例如: G1 = (V1, E1) 其中: V1=A, B, C, D, E E1=, , , , , ,无向图:在图G中,若E 且E, 则称 (v,w) 为顶点v 和顶点 w 之间存在一条边,此时的图在顶点之间不
3、再强调方向性,称作无向图。 例如: G2=(V2,E2) V2= A, B, C, D, E, F E2=(A,B), (A,E), (B,E), (B,F), (C,D), (C,F), (D,F) ,例1:已知某图的形式化定义如下: G=(V,E) V=v1,v2,v3,v4,v5,v6 E=(v1,v2),(v1,v4),(v1,v5),(v2,v3),(v2,v6), (v3,v6),(v5,v6) 试画出此图.,2. 名词和术语 网、子图 完全图、稀疏图、稠密图 邻接点、度、入度、出度 路径、路径长度、简单路径、简单回路 连通图、连通分量、强连通图、强连通分量 生成树、生成森林,B,
4、F,C,B,B,C,子图:假设有两个图G=(V,E)和 G= (V,E),若 VV ,且 EE,则称 G为G的子图。,网:在实际应用中,图的弧或边与具有一定意义的数相关,称这些数为“权”。 弧或边带权的图分别称作有向网或无向网。,返 回,完全图:假设图G中有n个顶点,e条边,若不考虑顶点到其自身的弧或边,则: (1)对于无向图,边数e的范围是0到n(n-1)/2。 含有e=n(n-1)/2条边的无向图称作完全图; (2)对于有向图,弧的数目e的范围是0到n(n-1)。 含有e=n(n-1)条弧的有向图称作有向完全图; 稀疏图:若边数 e=nlogn,则称作稠密图。,返 回,无向图中: 邻接点:
5、假若顶点v和顶点w之间存在一条边,则称顶点v和w互为邻接点,边(v,w) 和顶点v 和w相关联。 顶点的度:和顶点v 关联的边的数目。,例如: TD(B) = 3 TD(A) = 2,有向图中: 顶点V的出度(OD): 以顶点v为弧尾的弧的数目; 顶点V的入度(ID) : 以顶点v为弧头的弧的数目。 顶点的度(TD)=出度(OD)+入度(ID),返 回,结论:一般情况下,如果顶点vi的度记作TD(vi),则一个含有n个顶点,e条边或弧的图,满足如下关系:,例如: OD(B) = 1 ID( B) = 2 TD(B) = 3,路径和回路:若有向图G中k+1个顶点之间都有弧存在(即, ,是图G中的
6、弧),则这个顶点序列v0,v1,vk为从顶点v0到顶点vk的一条有向路径,路径上弧的数目称作路径长度。 若序列中的顶点都不相同,则为简单路径。同理,无向图中的路径称为无向路径。如果v0和vk是同一个顶点,则该路径为回路或者环。,返 回,简单路径: C,F,A,E 回路:B,C,F,B,若无向图G中任意两个顶点之间都有路径相通,则称此图为连通图,若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量。,对有向图,若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图。否则,其各个极大强连通子图称作它的强连通分量。,A,B,E,C,F,A,B,E,C,F,返 回,假设一个连通图有 n
7、个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树。,对非连通图,则称由各个连通分量的生成树的集合为此非连通图的生成森林。,返 回,补充习题: 1.在一个无向图中,所有顶点的度数之和等于所有边数的( )倍。 A) 1/2 B) 1 C) 2 D) 4 2.具有5个顶点的有向完全图有( )条弧。 A) 10 B) 16 C) 20 D) 25 3.一个有10个顶点,6条边的无向图,该图是否连通( )。 A) 能 B) 不能 4.在任一有向图中,所有顶点的入度之和一定等于所有顶点的出度之和( )。 A) 正确 B) 不正确,1.C 2.C
8、3.B 4.A,3. 图的基本操作 1)结构的建立和销毁 CreatGraph( 初始条件:图G存在,v是G中的某个顶点,w是v的邻 接顶点。 操作结果:返回 v 的(相对于w的) “下一个邻接点”。若 w 是 v 的最后一个邻接点,则返回“空”。 4)插入或删除顶点 InsertVex( /最大值设为MAX const MAX_VERTEX_NUM=20; /最大顶点个数 typedef enum DG, DN, AG, AN GraphKind; /图的类型(有向图,有向网,无向图,无向网) typedef char vextype ; / 顶点的数据类型 typedef struct A
9、rcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。对无权图, /用1或0表示相邻否;对带权图,则为权值类型。 InfoType *info; / 指向弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef struct / 图的定义 vextype vexsMAX_VERTEX_NUM; / 顶点信息数组 AdjMatrix arcs; / 弧的信息 (邻接矩阵) int vexnum, arcnum; / 顶点数,弧数 GraphKind kind; / 图的种类标志 Graph;,构
10、造图的算法: void CreateGraph(Graph *G) /建立图的邻接矩阵的结构 cinG-kind; switch (G-kind) case DG : CreateDG(G); break; case DN : CreateDN(G); break; case AG : CreateAG(G); break; case AN : CreateAN(G); break; default : return ERROR; ,void CreateAN(Graph *G) /建立无向网 int i, j, k; int w; for ( i=0 ; ivexnum; +i ) cinG
11、-vexsi ; /读入顶点信息,建立顶点表 for ( i=0 ; ivexnum; +i ) for( j=0 ; jvexnum; +j ) G-arcsij=MAX; /邻接矩阵初始化 for (k=0;karcnum;k+) cinijw; G-arcsij=w; G-arcsji= G-arcsij; /对称矩阵 /CreateAN,7.2.2 图的邻接表存储表示 邻接表(adjacency)是图的一种链式存储表示方法,它类似于树的孩子链表法。在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。,其中:数据域(inf
12、o):存储和边或弧相关的信息,如权值等。 邻接点域(adjvex):指示与顶点vi邻接的点在图中的存储位置。链域(nextarc):指示下一条边或弧的结点。,相应的结点结构为: 每个单链表上附设一个表头结点,在表头结点中,除了设有链域(firstarc)指向链表中第1个结点之外, 还设有存 储顶点vi有关信息的数据域data。,这些表头结点 通常以顺序存储结构存储,便于访问任意结点。,G1有向图的邻接表:,MAX_VERTEX_NUM,可见,在有向图的邻接表中不易找到指向该顶点的弧。,G2无向图的邻接表:,MAX_VERTEX_NUM,A,F,B,C,D,E,typedef struct Ar
13、cNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;,adjvex nextarc info,弧的结点结构,类型描述如下:,typedef struct VNode char data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,data firstarc.,表头结点结构,图的结构定义,typedef struct AdjList vert
14、ices; /表头结点顺序表 int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;,总结: 无向图的邻接表中结点个数是边数的两倍。 在无向图的邻接表中,顶点vi的度恰为第i个链表中 的结点个数。 在有向图的邻接表中,第i个单链表中的结点个数只 是顶点vi的出度。 顶点的入度值不容易得出。为了便于确定顶点vi的入度,则建立一个以顶点vi为头的弧的单链表,称为有 向图的逆邻接表。,利用邻接表构造无向图算法如下: void CreateGraph(ALGraph *G) /建立图的邻接表的结构 cinG-kind; switch (G-kind) case
15、DG : CreateDG(G); break; case DN : CreateDN(G); break; case UDG : CreateUDG(G); break; case UDN : CreateUDN(G); break; ,算法 7.1 void CreateUDG(ALGraph / 初始化链表头指针为空 /for,for (k=0; k v1 v2; / 输入一条弧的始点和终点 i = LocateVex(G, v1); j = LocateVex(G, v2); / 确定v1和v2在G中位置,即顶点的序号 pi = new ArcNode; pi - adjvex = j
16、; / 对弧结点赋邻接点位置信息 pi - nextarc = G.verticesi.firstarc; G.verticesi.firstarc = pi; / 插入链表G.verticesi,pj = new ArcNode; pj - adjvex = i; / 对弧结点赋邻接点位置信息 pj - nextarc = G.verticesj.firstarc; G.verticesj.firstarc = pj; / 插入链表G.verticesj if (IncInfo) / 若弧含有相关信息,则输入 cin pj-info; pi-info=pj-info; /if /for /
17、CreateUDG,知识小结: 1.图的定义与形式化描述(表示) 2.相关术语(有向图、无向图、权、网、子图、完全图、稀疏图、稠密图、邻接点、度、入度、出度、路径与路径长度、回路、连通图、连通分量、强连通图与强连通分量、生成树) 3.图的基本操作(建立与销毁、对顶点的访问、对邻接点的访问、插入与删除顶点、遍历) 4.图的存储结构:顺序存储(邻接矩阵)、链式存储(邻接表),每种存储结构的特点 5.构造图的算法,7.3 图的遍历 从图中某个顶点出发遍访图中其余顶点,并且使图中的每个顶点仅被访问一次的过程。 由图的定义知,图中的任意顶点都可能和其余的顶点相邻接,所以在访问了某个顶点之后,可能沿着某条
18、搜索路 径,又回到该顶点上。 为了避免同一顶点被访问多次,在遍历图的过程中,必须记下每个已访问过的顶点。为此,设计一个辅助数组visitedn,它的初始值置为假或零,一旦访问了顶点vi,便 置相应的visitedi为真或为被访问时的次序号。,7.3.1 深度优先搜索遍历 深度优先搜索( Depth First Search)遍历类似于树的先根遍历,可看成是树的先根遍历的推广。 假设给定图G的初始状态是所有顶点均未曾访问过,则深度优先搜索可从图中某个顶点V出发,访问此顶点,然后依次从V的各个未被访问的邻接点出发深度优先搜索遍历 图,直至图中所有和V有路径相通的顶点都被访问到。 上述搜索法是递归定
19、义的。尽可能先对纵深方向进行 搜索,故称为深度优先搜索。,V,w1,SG1,SG2,SG3,W1、W2和W3均为V的邻接点, SG1、SG2和SG3分别为含顶点W1、W2 和W3的子图,访问顶点 V : for (W1、W2、W3 ) 若V的邻接点Wi未被访问, 则从它出发进行深度优先搜索遍历。,w2,w3,w2,Y,N,判别V的邻接点是否被访问的办法:为每个顶点设立一个 “访问标志visitedi”,其初值为假,一旦某个顶点被访问,则相应的分量为真。 由讨论可得到dfs算法的流程图:,Y,visite(v); visitedv=TRUE;,W=0?,W被访问过?,dfs(w);,w=next
20、adjvex(G,v,w),w=firstadjvex(G,v),void DFS(Graph G, int v)(算法7.2) / 从第v个顶点出发递归地深度优先遍历连通图G visitedv = TRUE; VisitFunc(v); / 访问第v个顶点 for (w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w) ) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w递归调用DFS /DFS,dfs(8),dfs(9),dfs(4),dfs(3),下面以下图为例来分析dfs算法的递归过程:调用dfs(1),此箭头表示是从
21、遍历运算dfs(1)中调用dfs(2),即从顶点1直接转到2,此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中,即从顶点3返回到2,6,7,1,2,5,3,4,8,10,9,dfs(1),dfs(2),dfs(5),dfs(6),dfs(7),dfs(10),在访问顶点3后,由于顶点3的邻接点已全被访问,故dfs(3)执行到此结束,应返回到调用层,即返回到dfs(2),dfs(1)包含如下两部分操作: (1)访问顶点1; (2)依次执行dfs(2)和dfs(8),dfs(9),dfs(8),dfs(4),dfs(3),3,2,1,4,9,6,5,8,7,3,2,1,4,9,6
22、,5,8,7,序列:3 2 4 9 1 6 5 8 7 为连通图的生成树 结论:一个图的深度优先搜索DFS序列不一定惟一,它与算法、图的存储结构及初始出发点有关。,上述算法只能访问到所有与初始顶点有路径相通的顶点,对非连通图,尚需从所有未被访问的顶点起调用算 法7.2。 void DFSTraverse(Graph G) / 算法7.3 bool visitedG.vexnum; / 附设访问标志数组 for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DF
23、S(G, v); / 对尚未访问的顶点调用DFS /DFSTraverse,a,c,h,k,f,e,d,b,g,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,访问标志:,访问次序:,选用邻接表表示图,深度优先遍历(算法 7.4) void DFS(ALGraph G, int v) / 从第v个顶点出发递归地深度优先遍历图G。 visitedv = TRUE; VisitFunc(G.verticesv.data); / 访问第v个顶点 for ( p=G.verticesv.firstarc; p; p=p-nextarc) w = p-adjvex; if (!v
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构及应用算法教程修订版 数据结构_第7章_图和广义表 数据结构 应用 算法 教程 修订版 广义
限制150内