内蒙古大学《算法与数据结构》讲义12图
39页1、下载第1 2章图恭喜!你已经成功穿越了“树”的森林,下面要学习图这种数据结构。令人惊叹的是,图可以用来描述成千上万的实际问题,不过,我们仅研究其中的一小部分。本章的主要内容如下: 图的若干术语:顶点,边,邻接,关联,度,回路,路径,连通构件,生成树。 图的三种类型:无向图,有向图和加权的图。 图的常用表示方法:邻接矩阵,邻接链表和邻接压缩表。 图的标准搜索方法:宽度优先搜索和深度优先搜索。 在图中寻找路径,在无向图中寻找连通构件以及在无向连通图中寻找生成树的算法。 如何把抽象数据类型表示成一个抽象类。本章所使用的新的C + +特征是:抽象类,虚函数和虚基类。12.1 基本概念简单地说,图(g r a p h)是一个用线或边连接在一起的顶点或节点的集合。正式一点的说法是,图G= (V,E) 是一个V和E的有限集合,元素V称为顶点(vertice, 也叫作节点或点) ,元素E称为边(edge, 也叫作弧或连线) ,E中的每一条边连接V中两个不同的顶点。可以用(i,j)来表示一条边,其中i 和j 是E所连接的两个顶点。一般来说,图是由回路和边组成,如图1 2 - 1所示。在图1 2 - 1中
2、有些边是带方向的(带箭头) ,而有些边是不带方向的。带方向的边叫有向边( directed edge) ,而不带方向的边叫无向边(undirected edge) 。对无向边来说,(i, j) 和(j, i) 是一样的;而对有向边来说,它们是不同的。前者的方向是从i 到j,后者是从j 到i。当且仅当(i, j) 是图中的边时,顶点i 和j 是邻接的(a d j a c e n t) 。边(i, j) 关联(i n c i d e n t)于顶点i 和j。图12-1a 中的顶点1和2是邻接的,顶点1和3,1和4,2和3,3和4也是邻接的,除此之外,这个图中没有其他邻接的顶点。边(1,2)关联于顶点1和2, (2,3)关联于顶点2和3。图12-1 图有些书中用i, j 表示无向边,而用(i, j)表示有向边。还有一些书用(i, j)表示无向边,用表示有向边。本书对两种边使用同一符号(i, j) ,边有向与否可从上下文中看出。a)b)c)在有向图中,有时候对邻接和关联的概念作更精确的定义非常有用。有向边 (i, j) 是关联至(incident to)顶点j 而关联于(incident fr
3、om)顶点i。顶点i 邻接至(adjacent to)顶点j,顶点j邻接于(adjacent from)顶点i。在图12-1c 的图中,顶点2邻接于顶点1,而1邻接至顶点2。边(1,2)关联于顶点1而关联至顶点2。顶点4邻接至顶点3且邻接于顶点3。边(3,4)是关联于顶点3而关联至顶点4。对于无向图来说, “至”和“于”的含义是相同的。如果使用集合的表示方法,图 1 2 - 1中的几个图可以用如下方法表示: G1 =(V1,E1) ;G2 =(V2,E2)和G3 =(V3,E3) ,其中:V1 = 1 , 2 , 3 , 4 ;E1 = ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 3 ) , ( 1 , 4 ) , ( 3 , 4 ) V2 = 1 , 2 , 3 , 4 , 5 , 6 , 7 ;E2 = ( 1 , 2 ) , ( 1 , 3 ) , ( 4 , 5 ) , ( 5 , 6 ) , ( 5 , 7 ) , ( 6 , 7 ) V3 = 1 , 2 , 3 , 4 , 5 ;E3 = ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 4 )
4、, ( 4 , 3 ) , ( 3 , 5 ) , ( 5 , 4 ) 如果图中所有的边都是无向边,那么该图叫作无向图( undirected graph) ,图12-1a 和b 都是无向图。如果所有的边都是有向的,那么该图叫作有向图( directed graph) ,图12-1c 是一个有向图。由定义知道,一个图中不可能包括同一条边的多个副本,因此,在无向图中的任意两个顶点之间,最多只能有一条边。在有向图中的任意两个顶点之间,最多只能有一条边从顶点 i 到顶点j 或从j 到i。并且一个图中不可能包含自连边(s e l f - e d g e) ,即(i,i) 类型的边,自连边也叫作环(l o o p) 。通常把无向图简称为图,有向图仍称为有向图( d i g r a p h) 。在一些图和有向图的应用中,我们会为每条边赋予一个权或耗费,这种情况下,用术语加权有向图( weighted graph)和加权无向图(weighted digraph)来描述所得到的数据对象。术语网络( n e t w o r k)在这里是指一个加权有向图或加权无向图。实际上,这里定义的所有图的变化都可以看
5、作网络的一种特殊情况一个无向(有向)图可以被看作是一个所有边具有相同权的无向(有向)网络。12.2 应用无向图,有向图和网络常常用于电子网络的分析、化合物(特别是碳氢化合物)的分子结构研究、空中航线和通信网络的描述、项目策划、遗传研究、统计、社会科学及它各种领域。这一节将用图来阐述一些实际问题。例12-1 路径问题 城市中有许多街道,每一个十字路口都可以看作图中一个顶点,邻接两个十字路口之间的每一段街道既可以看作一条,也可以看作两条有向边。如果街道是双向的,就用两条有向边。如果街道是单向的,就用一条有向边。图1 2 - 2给出了假想的街道和相应的有向图。图中有三条街道:街道1,街道2和街道3以及两条大街:大街1和大街2。十字路口用数字1到6进行编号,相应的有向图(如图12-2b所示)的顶点标号与图12-2a 给出的十字路口的标号相同。当且仅当对于每一个j(1jk) ,边(ij , ij+ 1)都在E中时,顶点序列P=i1 , i2 , ik是图或有向图G= (V, E)中一条从i1到ik的路径。当且仅当相应的有向图中顶点i 到顶点j 有一条路径时,十字路口i 到j 之间存在一条路径。在
《内蒙古大学《算法与数据结构》讲义12图》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义12图》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页