数据结构 幻灯片.ppt
《数据结构 幻灯片.ppt》由会员分享,可在线阅读,更多相关《数据结构 幻灯片.ppt(98页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构课件 第1页,共98页,编辑于2022年,星期六7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 拓扑排序和关键路径拓扑排序和关键路径7.6 7.6 最短路径问题最短路径问题第2页,共98页,编辑于2022年,星期六 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集V R构成构成的数据结构。的数据结构。Graph=(V,VR)其中,VR|v,wV 且 P(v,w)表示从 v 到 w 的一条弧,并称 v 为弧尾弧尾,w 为弧头弧头。谓词 P(v,w)定义了弧 的
2、意义或信息。7.1 7.1 图的定义和术语图的定义和术语第3页,共98页,编辑于2022年,星期六 由于“弧”是有方向的,因此称由顶点集和弧集构成的图为有向图有向图。EACBD例如例如:G1=(V1,VR1)其中V1=A,B,C,D,EVR1=,第4页,共98页,编辑于2022年,星期六若VR 必有VR,则称(v,w)为顶点 v 和顶点 w 之间存在一条边边。BCAFED由顶点集和边集构成的图称作无向图无向图。例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)第5页,共98页,编辑于2022年,星期
3、六名词和术语名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林第6页,共98页,编辑于2022年,星期六ABECFAEFBBC设图G=(V,VR)和图 G=(V,VR),且 VV,VRVR,则称 G 为 G 的子图子图。1597211132 弧或边带权的图分别称作有向网有向网或无向无向网网。第7页,共98页,编辑于2022年,星期六假设图中有 n 个顶点,e 条边,则 含有 e=n(n-1)/2 条边的无向图称作完完全图全图;含有 e=n(n-1)条弧的有向图称作 有有向完全图向完全图;若边或
4、弧的个数 enlogn,则称作稀稀疏图疏图,否则称作稠密图稠密图。第8页,共98页,编辑于2022年,星期六 假若顶点v 和顶点w 之间存在一条边,则称顶点v 和w 互为邻接点邻接点,例如例如:TD(B)=3TD(A)=2 边(v,w)和顶点v 和w 相关联相关联。和顶点v相关联的边的数目边的数目定义为顶点v的度,记度,记为为TDTD(v v)。ACDFEB右侧图中第9页,共98页,编辑于2022年,星期六顶点的出度出度:以顶点v 为弧尾的弧的数目;ABECF对有向图来说对有向图来说,顶点的入度入度:以顶点v为弧头的弧的数目。顶点的度度(TD)=)=出度出度(OD)+)+入度入度(ID)例如例
5、如:ID(B)=2OD(B)=1TD(B)=3由于弧有方向性,则有入入度度和出度出度之分第10页,共98页,编辑于2022年,星期六设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中,(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECF如如:从A到F长度为 3 的路径A,B,C,F简单路径简单路径:指序列中顶点不重复出现的路径。简单回路简单回路:指序列中第一个顶点和最后一个顶点相同的路径。第11页,共98页,编辑于2022年,星期六若图G中任意两个顶点之间都有路径相通,则称此图为连通图连通
6、图;若无向图为非连通图,则图中各个极大连通子图称作此图的连通连通分量分量。BACDFEBACDFE第12页,共98页,编辑于2022年,星期六 若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图强连通图。ABECFABECF对有向图,对有向图,否则,其各个强连通子图称作它的强连强连通分量通分量。第13页,共98页,编辑于2022年,星期六 假设一个连通图有 n 个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成生成树树。对非连通图,则称由各个连通分量的生成树的集合为此非连通图的生成森生成森林林。BACDFE第14页,共98页,编
7、辑于2022年,星期六结构的建立和销毁结构的建立和销毁插入和删除顶点插入和删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧基本操作基本操作第15页,共98页,编辑于2022年,星期六CreatGraph(&G,V,VR);/按定义(V,VR)构造图DestroyGraph(&G);/销毁图结构的建立和销毁结构的建立和销毁第16页,共98页,编辑于2022年,星期六对顶点的访问操作对顶点的访问操作LocateVex(G,u);/若G中存在顶点u,则返回该顶点在/图中“位置位置”;否则返回其它信息。GetVex(G,v);/返回 v 的值。Put
8、Vex(&G,v,value);/对 v 赋值value。第17页,共98页,编辑于2022年,星期六对邻接点的操作对邻接点的操作FirstAdjVex(G,v);/返回 v 的“第一个邻接点第一个邻接点”。若该顶点/在 G 中没有邻接点,则返回“空”。NextAdjVex(G,v,w);/返回 v 的(相对于 w 的)“下一个邻接下一个邻接/点点”。若 w 是 v 的最后一个邻接点,则/返回“空”。第18页,共98页,编辑于2022年,星期六插入和删除顶点插入和删除顶点InsertVex(&G,v);/在图G中增添新顶点v。DeleteVex(&G,v);/删除G中顶点v及其相关的弧。第19
9、页,共98页,编辑于2022年,星期六插入和删除弧插入和删除弧InsertArc(&G,v,w);/在G中增添弧,若G是无向的,/则还增添对称弧。DeleteArc(&G,v,w);/在G中删除弧,若G是无向的,/则还删除对称弧。第20页,共98页,编辑于2022年,星期六遍遍 历历DFSTraverse(G,v,Visit();/从顶点v起深度优先深度优先遍历图G,并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit();/从顶点v起广度优先广度优先遍历图G,并对每/个顶点调用函数Visit一次且仅一次。第21页,共98页,编辑于2022年,星期六7.2
10、图的存储结构图的存储结构一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示第22页,共98页,编辑于2022年,星期六Aij=0 (i,j)VR1 (i,j)VR一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为第23页,共98页,编辑于2022年,星期六有向图的邻接矩阵为有向图的邻接矩阵为非对称矩阵非对称矩阵ABECD第24页,共98页,编辑于2022年,星期六#define MAXVERTEXNUM 20typedef enum DG,DN,UDG,UDN GraphKind;typedef
11、 struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图,用1或0表示相邻否;/对带权图,则为权值类型。InfoType *info;/该弧相关信息的指针 ArcCell,AdjMatrixMAXVERTEXNUMMAXVERTEXNUM;第25页,共98页,编辑于2022年,星期六typedef struct /图的定义图的定义 VertexType vexsMAXVERTEXNUM;/顶点信息 AdjMatrix arcs;/弧的信息 int vexnum,arcnum;/顶点数,弧数 GraphKind kind;/图的种类标志
12、MGraph;第26页,共98页,编辑于2022年,星期六DBACFE二、图的邻接表二、图的邻接表 存储表示存储表示 A 1 4 B 0 4 5 C 3 5 D 2 5 E 0 1 F 1 2 30 1 2 3 4 5第27页,共98页,编辑于2022年,星期六有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C D EABECD可见,在有向图的邻接表中不易找到指向该顶点的弧第28页,共98页,编辑于2022年,星期六ABECD有向图的逆邻接表有向图的逆邻接表在有向图的逆邻接表中,对每个顶点,链接的是指向该顶点的弧01234A B C D E 30320 41 第29页
13、,共98页,编辑于2022年,星期六typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针 InfoType *info;/该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构第30页,共98页,编辑于2022年,星期六typedef struct VNode VertexType data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAXVERTEXNUM;data firstar
14、c顶点的结点结构顶点的结点结构第31页,共98页,编辑于2022年,星期六typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;图的结构定义图的结构定义(邻接表)第32页,共98页,编辑于2022年,星期六三、有向图的十字链表存储表示三、有向图的十字链表存储表示 ABCABC0 1 20 2 0 12 1 2 0 第33页,共98页,编辑于2022年,星期六弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有有相同弧尾相同弧尾的结点指向下一个有有相同弧头相同弧头的结点type
15、def struct ArcBox /弧的结构表示弧的结构表示 int tailvex,headvex;InfoType *info;struct ArcBox *hlink,*tlink;ArcBox;tailvexheadvexhlinktlinkinfo第34页,共98页,编辑于2022年,星期六顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第第一条入弧一条入弧指向该顶点的第一条出弧第一条出弧typedef struct VexNode /顶点的结构表示顶点的结构表示 VertexType data;ArcBox *firstin,*firstout;VexNode;datafi
16、rstinfirstout第35页,共98页,编辑于2022年,星期六typedef struct VexNode xlistMAXVERTEXNUM;/顶点结点(表头向量)int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)第36页,共98页,编辑于2022年,星期六四、无向图的邻接多重表存储表示typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox *ilink,*jlink;InfoType *info;/该
17、边信息指针 EBox;边的结构表示边的结构表示第37页,共98页,编辑于2022年,星期六typedef struct /邻接多重表邻接多重表 VexBox adjmulistMAXVERTEXNUM;int vexnum,edgenum;AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data;EBox *firstedge;/指向第一条依附该顶点的边 VexBox;无向图的结构表示无向图的结构表示第38页,共98页,编辑于2022年,星期六7.3 图的遍历图的遍历 从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中的每个顶
18、点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索第39页,共98页,编辑于2022年,星期六 从图中某个顶点顶点V0 出发,访问此顶点,然后依次从依次从V0的的各个未被访问的各个未被访问的邻接点出发邻接点出发深度优先搜索遍历图深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图一、深度优先搜索遍历图连通图的深度优先搜索遍历连通图的深度优先搜索遍历第40页,共98页,编辑于2022年,星期六SG1SG2SG3W1、W2和W3 均为 V 的邻接点,SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V ;for(W1
19、、W2、W3)若该邻接点W未被访问,则从它出发进行深度优先搜索遍历。Vw1w3w2第41页,共98页,编辑于2022年,星期六从上页的图解可见从上页的图解可见:1.从深度优先搜索遍历连通图的过程类似于树的先根遍历;解决的办法是:为每个顶点设立一个“访问标志 visitedw”;2.如何判别V的邻接点是否被访问?第42页,共98页,编辑于2022年,星期六如图如图如图如图G4G4:深到底深到底回退回退深到底深到底V1V2V4V8V5(V2V8均已访问)均已访问)深到底深到底V3V6V7回退回退访问访问V1V2V3V4V5V6V7V8 visited0.n-1visited0.n-1是一个辅助数组
20、,记载顶点是否被访问过是一个辅助数组,记载顶点是否被访问过是一个辅助数组,记载顶点是否被访问过是一个辅助数组,记载顶点是否被访问过visitedi=TRUE,已访问过已访问过FALSE,未访问过(初值)未访问过(初值)注意:注意:DFS序列不唯一,它与算法、图的存储结构及初始出发点有关。序列不唯一,它与算法、图的存储结构及初始出发点有关。第43页,共98页,编辑于2022年,星期六深度优先搜索递归过程深度优先搜索递归过程(采用邻接矩阵存储图):采用邻接矩阵存储图):void DFS(MGraph G,int i)coutG.vexi”;visitedi=TRUE;for(j=0;jG.vexn
21、um;+j)if(!visitedj&G.arcsij.adj)DFS(G,j);第44页,共98页,编辑于2022年,星期六深度优先搜索递归过程深度优先搜索递归过程(采用邻接表存储图):采用邻接表存储图):void DFS(ALGraph G,int i)coutG.verticesi.data”;visitedi=TRUE;p=G.verticesi.firstarc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;第45页,共98页,编辑于2022年,星期六 首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点
22、,如果未被访问,则以该顶点为起始点,进行深度优先搜索遍历,否则继续检查下一顶点。非连通图的深度优先搜索遍历非连通图的深度优先搜索遍历第46页,共98页,编辑于2022年,星期六void DFSTraverse(Graph G)/对图对图 G 作深度优先遍历。作深度优先遍历。for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vw1,V-w2,V-w8 的路径长度为1;V-w7,V-w3,V-w5 的路径长度为2;V-w6,V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4第49页,共98页,编辑于2022年,星期六 从图中的某
23、个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点,之后按这些顶点被访问的先后次序依次按这些顶点被访问的先后次序依次访问它们的邻接点访问它们的邻接点,直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。第50页,共98页,编辑于2022年,星期六广度优先搜索(广度优先搜索(广度优先搜索(广度优先搜索(breadth-first-search)breadth-first-search)1)1)首先访问指定首先访问指定首先访问指定首先访问指定顶点顶点顶点顶点v0v
24、0,将,将,将,将v0v0作为当前顶点作为当前顶点作为当前顶点作为当前顶点;2)2)访问当前顶点的访问当前顶点的访问当前顶点的访问当前顶点的所有未访问过的邻接点所有未访问过的邻接点所有未访问过的邻接点所有未访问过的邻接点,3)3)并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点;4)4)重复重复重复重复2 2),),),),直到直到直到直到所有顶点所有顶点所有顶点所有顶点被访问为止。被访问为止。被访问为止。被访问为止。对右图广度优先搜索,访问顶点序列为:对右图广度优先搜索,访问顶点序列为:对右图广度
25、优先搜索,访问顶点序列为:对右图广度优先搜索,访问顶点序列为:V1 V2 V3 V4 V5 V6 V7 V8V1 V2 V3 V4 V5 V6 V7 V8V8V1V2V3V4V5 V6V7注意:注意:BFS序列不唯一,它与算法、图的存储结构及初始出发点有关。序列不唯一,它与算法、图的存储结构及初始出发点有关。第51页,共98页,编辑于2022年,星期六广度优先搜索算法(以邻接矩阵作存储结构):广度优先搜索算法(以邻接矩阵作存储结构):广度优先搜索算法(以邻接矩阵作存储结构):广度优先搜索算法(以邻接矩阵作存储结构):void BFSTraverse(MGraph G)for(i=0;iG.ve
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 幻灯片
限制150内