第五章图.ppt
《第五章图.ppt》由会员分享,可在线阅读,更多相关《第五章图.ppt(195页珍藏版)》请在三一文库上搜索。
1、图,图的定义和术语 图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中:V(G)是顶点的非空有限集 E(G)是边的有限集合,边是顶点的无序对或有序对 有向图有向图G是由两个集合V(G)和E(G)组成的 其中:V(G)是顶点的非空有限集 E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为,v,w是顶点,v为弧尾,w为弧头 无向图无向图G是由两个集合V(G)和E(G)组成的 其中:V(G)是顶点的非空有限集 E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v),图G1中:V(G1)=1,2,3,4,5,6 E(G
2、1)=, , , , , , ,图G2中:V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),有向完备图 n个顶点的有向图,最大边数是n(n-1) 无向完备图 n个顶点的无向图,最大边数是n(n-1)/2 权 与图的边或弧相关的数叫 网 带权的图叫 子图如果图G(V,E)和图G(V,E),满足: VV EE 则称G为G的子图,顶点的度 无向图中,顶点的度为与每个顶点相连的边数 有向图中,顶点的度分成入度与出度 入度:以该顶点为头的弧的数目 出度:以该顶点为尾的弧的数目 路径 路径是顶点的序列 V=Vi
3、0,Vi1,Vin,满足 (Vij-1,Vij)E (1jn),路径长度 沿路径边的数目或沿路径各边权值之和 回路 第一个顶点和最后一个顶点相同的路径叫 简单路径 序列中顶点不重复出现的路径叫 简单回路 除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路叫 连通 从顶点V到顶点W有一条路径,则说V和W是连通的 连通图 图中任意两个顶点都是连通的叫 连通分量 非连通图的每一个连通部分叫 强连通图 有向图中,如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径,则称G是,路径:1,2,3,5,6,3 路径长度:5 简单路径:1,2,3,5 回路:1,2,3,5,6,
4、3,1 简单回路:3,5,6,3,路径:1,2,5,7,6,5,2,3 路径长度:7 简单路径:1,2,5,7,6 回路:1,2,5,7,6,5,2,1 简单回路:1,2,3,1,连通图,强连通图,非连通图 连通分量,图的存储结构 多重链表,优点? 缺点?,邻接矩阵表示顶点间相联关系的矩阵 定义:设G=(V,E)是有n1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵,特点: 无向图的邻接矩阵对称,可压缩存储; 有向图邻接矩阵不一定对称;有n个顶点的有向图需存储空间为n 无向图中顶点Vi的度TD(Vi)是 邻接矩阵A中第i行元素之和 有向图中, 顶点Vi的出度是 A中第i行元素之和 顶点Vi
5、的入度是 A中第i列元素之和,网络的邻接矩阵可定义为:,关联矩阵表示顶点与边的关联关系的矩阵 定义:设G=(V,E)是有n1个顶点,e0条边的图,G的关联矩阵A是具有以下性质的ne阶矩阵,特点 关联矩阵每列只有两个非零元素,是稀疏矩阵;n越大,零元素比率越大 无向图中顶点Vi的度TD(Vi)是 关联矩阵A中第i行元素之和 有向图中, 顶点Vi的出度是 A中第i行中“1”的个数 顶点Vi的入度是 A中第i行中“-1”的个数,邻接表 实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),特点 无向图中顶点Vi的度为 第i个单链表中的结点数 有向
6、图中 顶点Vi的出度为 第i个单链表中的结点个数 顶点Vi的入度为 整个单链表中邻接点域值是i的结点个数,逆邻接表 有向图中对每个结点建立以Vi为头的弧的单链表,有向图的十字链表表示法,无向图的邻接多重表表示法,图的遍历 广度优先遍历(BFS) 从图的某一顶点V0出发,访问此顶点; 依次访问V0的各个未曾访问过的邻接点; 分别从这些邻接点出发,广度优先遍历图; 直至图中所有已被访问的顶点的邻接点都被访问到; 若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止,节点1,距离为1的节点? 2, 3, 7, 9,距离为2的节点? 4, 5, 6
7、, 8,距离为3的节点? 0,广度遍历:V1 V2 V3 V4 V5 V6 V7 V8,广度遍历:V1 V2 V3 V4 V5 V6 V7 V8,广度遍历:V1 V2 V3 V4 V5 V6 V7 V8,广度遍历:V1 V2 V3 V4 V6 V7 V8 V5,节点1,距离为1的节点? 2, 3, 7, 9,距离为2的节点? 4, 5, 6, 8,距离为3的节点? 0,如何得到?,暂存已经访问的节点!,用什么数据结构?,算法主要结构?,算法结束条件?,按需求次序访问暂存的节点,1,2,3,7,9,4,8,5,6,0,广度优先遍历算法(邻接表),void traver(TD g,int n) i
8、nt i; static int visitedM; for(i=1;i=n;i+) visitedi=0; for(i=1;i=n;i+) if(visitedi=0) bfs(g,i,visited); ,void bfs(TD g,int v,int visited) int quM,f=0,r=0; JD *p; printf(“%dn“,v); visitedv=1; qu0=v; while(f=r) v=quf+; p=gv.firstarc;,while(p!=NULL) v=p-adjvex; if(visitedv=0) visitedv=1; printf(“%dn“,v
9、); qu+r=v; p=p-next; ,图的遍历 深度优先遍历(DFS) 从图的某一顶点V0出发,访问此顶点; 依次从V0的未被访问的邻接点出发,深度优先遍历图; 直至图中所有和V0相通的顶点都被访问到; 若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止,DFS Algorithm,Example,Adjacency List,source,Visited Table (T/F),Initialize visited table (all False) Initialize Pred to -1,Pred,Example,Adjac
10、ency List,source,Visited Table (T/F),Mark 2 as visited,Pred,RDFS( 2 ) Now visit RDFS(8),Example,Adjacency List,source,Visited Table (T/F),Mark 8 as visited mark Pred8,Pred,RDFS( 2 ) RDFS(8) 2 is already visited, so visit RDFS(0),Recursive calls,Example,Adjacency List,source,Visited Table (T/F),Mark
11、0 as visited Mark Pred0,Pred,RDFS( 2 ) RDFS(8) RDFS(0) - no unvisited neighbors, return to call RDFS(8),Recursive calls,Example,Adjacency List,source,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) Now visit 9 - RDFS(9),Recursive calls,Back to 8,Example,Adjacency List,source,Visited Table (T/F),Mark 9 as
12、 visited Mark Pred9,Pred,RDFS( 2 ) RDFS(8) RDFS(9) - visit 1, RDFS(1),Recursive calls,Example,Adjacency List,source,Visited Table (T/F),Mark 1 as visited Mark Pred1,Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) visit RDFS(3),Recursive calls,Example,Adjacency List,source,Visited Table (T/F),Mark 3 as visite
13、d Mark Pred3,Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) visit RDFS(4),Recursive calls,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(4) STOP all of 4s neighbors have been visited return back to call RDFS(3),Example,Adjacency List,source,Visited Table (T/F),Mark 4 as visited Mark Pred4,Pred,Recur
14、sive calls,Example,Adjacency List,source,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) visit 5 - RDFS(5),Recursive calls,Back to 3,Example,Adjacency List,source,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(5) 3 is already visited, so visit 6 - RDFS(6),
15、Recursive calls,Mark 5 as visited Mark Pred5,Example,Adjacency List,source,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(5) RDFS(6) visit 7 - RDFS(7),Recursive calls,Mark 6 as visited Mark Pred6,Example,Adjacency List,source,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9
16、) RDFS(1) RDFS(3) RDFS(5) RDFS(6) RDFS(7) - Stop no more unvisited neighbors,Recursive calls,Mark 7 as visited Mark Pred7,Example,Adjacency List,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(5) RDFS(6) - Stop,Recursive calls,source,Example,Adjacency List,Visited Table (T/F)
17、,Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) RDFS(5) - Stop,Recursive calls,source,Example,Adjacency List,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) RDFS(3) - Stop,Recursive calls,source,Example,Adjacency List,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9) RDFS(1) - Stop,Recur
18、sive calls,source,Example,Adjacency List,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) RDFS(9) - Stop,Recursive calls,source,Example,Adjacency List,Visited Table (T/F),Pred,RDFS( 2 ) RDFS(8) - Stop,Recursive calls,source,Example,Adjacency List,Visited Table (T/F),Pred,RDFS( 2 ) - Stop,Recursive calls,s
19、ource,Example,Adjacency List,Visited Table (T/F),Pred,Try some examples. Path(0) - Path(6) - Path(7) -,Check our paths, does DFS find valid paths? Yes.,source,深度遍历: V1 V2 V4 V8 V5 V3 V6 V7,深度遍历:V1 V2 V4 V8 V5 V6 V3 V7,深度遍历:V1 V2 V4 V8 V5 V6 V3 V7,深度遍历:V1 V2 V4 V8 V3 V6 V7 V5,深度优先遍历算法 递归算法,Ch6_1.c,vo
20、id traver(TD g,int n) int i; static int visitedM; for(i=1;i=n;i+) visitedi=0; for(i=1;i=n;i+) if(visitedi=0) dfs(g,i,visited); ,void dfs(TD g,int v,int visited) JD *w; int i; printf(“%d “,v); visitedv=1; w=gv.firstarc; while(w!=NULL) i=w-adjvex; if(visitedi=0) dfs(g,i,visited); w=w-next; ,深度遍历:V1,V3
21、 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,深度遍历:V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,迷宫问题,迷宫:,不使用栈,可否?,生成树 生成树 定义:所有顶点均由边连接在一起,但不存在回路的图叫 深度优先生成树与广度优先生成树 生成森林:非连通图每个连通分量的生成树一起组成非连通图的 说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点: 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树,
22、深度遍历:V1 V2 V4 V8 V5 V3 V6 V7,广度遍历:V1 V2 V3 V4 V5 V6 V7 V8,最小生成树 问题提出,要在n个城市间建立通信联络网 建立该通信网所需花费的总代价最小 顶点表示城市 权城市间建立通信线路所需花费代价 希望找到一棵生成树,它的每条边上的权值之和最小 最小代价生成树,问题分析,n个城市间,最多可设置n(n-1)/2条线路 n个城市间建立通信网,只需n-1条线路 问题转化为: 如何在可能的线路中选择n-1条 能把所有城市(顶点)均连起来 且总耗费(各边权值之和)最小,最小生成树性质(MST性质),设 N=(V, E) 是一连通网 U 是顶点集V的一个
23、非空子集 其中uU, vV-U 若(u , v)是一条具有最小权值的边 则存在一棵包含边(u , v)的最小生成树 证明: 假设不存在这样一棵包含边(u , v)的最小生成树 任取一棵最小生成树T,将(u , v)加入T中 根据树的性质,此时T中必形成一个包含(u , v)的回路, 且回路中必有一条边(u, v)的权值大于或等于(u , v)的权值 删除(u, v),则得到一棵代价小于等于T的生成树T,且T为一棵包含边(u , v)的最小生成树 这与假设矛盾, 故该性质得证,构造最小生成树方法 方法一:普里姆(Prim)算法(边割法) 算法思想:设N=(V,E)是连通网,TE是N上最小生成树中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五
链接地址:https://www.31doc.com/p-2968712.html