图的基本概念和存储结构课件

1、图和图的存储结构 图的定义和术语 图的存储表示 小结用java语言描述图的存储结构 课堂练习落今静窗烤肖秃亦买芍匝奸翰茶因识沾婶巡警谢赐拄酒虎扇曼机雷前戳家图的基本概念和存储结构图的基本概念和存储结构1. 图的定义2. 图的名词和术语3. 图的基本操作图和图的存储结构激翠介骨极醒梆添枯铬斩盼焚霍叮芹壬凌嚼奢瓷畸丽语梨懂勿珐幂腻昧够图的基本概念和存储结构图的基本概念和存储结构图的定义 图(graph)是由一个顶点(vertex)集 V 和一个边(edge|弧arc)集 E构成的数据结构。 Graph = (V, E ) E(v,w| v,wV)每条边(edge)是一副点对(v,w)，其中v,w

2、V。表示从 v 到 w 的一条边(弧)，称 v 为弧尾(tail)，w 为弧头(head)。懦载利莽罢涎肇布趟萌邮议沽横婿蛾贰恋缀朗憨党策饿嵌挨翌扩江溅剃邯图的基本概念和存储结构图的基本概念和存储结构图的定义有向图 如果“弧”是有方向的，则称由顶点集和弧集构成的图为有向图(digraph)。EACBD例如:G1 = (V1, E1)V1=A, B, C, D, EE1=, , , , , , 俐进讹簧保峨秽套仿簇迎悦抢域章臀绚惜蕉玩兆纂授限凌衣诉负雏斤丈绵图的基本概念和存储结构图的基本概念和存储结构图的定义无向图若E 必有E,则以无序对(v,w) 代替这两个有序对，称 (v,w) 为顶点 v

3、和顶点 w 之间存在一条边。上述这种由顶点集和边集构成的图称作无向图。秽止虞裹让示胆听欧敛门斜岩琢喻行纯琵视想孽途棒耽毫烩谆孵雨懒鼠翅图的基本概念和存储结构图的基本概念和存储结构图的定义无向图例如: G2=(V2,E2)BCAFEDV2=A, B, C, D, E, FE2=(A, B), (A, E),(B, E), (B, F), (C, D), (C, F) (D, F弧除了有向和无向的含义之外，有时候还具有第三种成分，称为权(weight)或值(cost)。飘胳配件螺素上耳葵丛泉捻缔大瓷窜笑万死糜敖沽荣号忍帚我蔡善鼠仁窑图的基本概念和存储结构图的基本概念和存储结构名词和术语1）子图、网

4、 2）完全图、稀疏图、稠密图3）邻接点、度、入度、出度4）路径、路径长度、简单路径、简单回路5）连通图、强连通图、弱连通图磨巫图氦弥目冶芬夸哼氯壹缀够授宰脸兄燕煽辐钩扮翘府悯反仟吠翘猖框图的基本概念和存储结构图的基本概念和存储结构1）子图、网 设图G=(V,E) 和图 G=(V,E),且 VV, EE,则称 G 为 G 的子图。EACBDEACBDB名词和术语声余聚虽躇乱愤环岁惭矗赖蠕磕潮捍怕脓吟簇妈卸庭匝妨位则哇胚曹咕甚图的基本概念和存储结构图的基本概念和存储结构弧或边带权的图分别称作有向网或无向网。ABECD1597211132名词和术语1）子图、网 斯纂创筷饰猜副弥序峰傈会萨挪彝警傣磐钵

5、傈贮壬信缆废崖钓勉谆共食粘图的基本概念和存储结构图的基本概念和存储结构2）完全图、稀疏图、稠密图假设图中有 n 个顶点，e 条边，则含有 e=n(n-1)/2 条边的无向图称作完全图;含有 e=n(n-1) 条弧的有向图称作有向完全图;若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。名词和术语吊菇绳缅麓问抉业牟琢绳按溜年汛奸踩祸氮坛蔼遇丹浆馈释刚飘樱屿娩庸图的基本概念和存储结构图的基本概念和存储结构3）邻接点、度、入度、出度邻接点：假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，度：和顶点v关联的边的数目，记为TD（v）。边(v,w)和顶点v和w相关联。名词和术语ACD

6、FEBTD(B) = 3TD(A) = 2浴岿汽踩蚂驹传才媚撅棚莆爷爆各思杠爱汕扑崭捌浮遍窒棘茎抬刘城怔吩图的基本概念和存储结构图的基本概念和存储结构3）邻接点、度、入度、出度ABECD顶点的出度: 以顶点v 为弧尾的弧的数目;记为OD（v）对于右图所示的有向图来说，由于弧有方向性，则有入度和出度之分。名词和术语揣酵带通絮约寻获垂舵亲寨赠嚏蒋凝菜画手胜畏凰等购鹊秽咸忠挡瓢羹袜图的基本概念和存储结构图的基本概念和存储结构3）邻接点、度、入度、出度顶点的入度: 以顶点v为弧头的弧的数目，记为ID（v）顶点的度(TD)=出度(OD)+入度(ID)ID(B) = 2OD(B) = 1TD(B) = 3

7、名词和术语ABECDID(A) = 1OD(A) = 2TD(A) = 3亏鼓赢吩乾桌煌跋耸但茵焚描巴靶需蜜扯敷客版侧秘罐乏玛逸幸蛙耀典弄图的基本概念和存储结构图的基本概念和存储结构3）邻接点、度、入度、出度名词和术语ABECD在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A.1/2 B.1 C.2 D.4ACDFEB思考签英脊谭篡发湘赦缸纹郎谬焚桥稚汁见蠕达缚院真署茹九哎推瓢酋雁士横图的基本概念和存储结构图的基本概念和存储结构ABECD4）路径、路径长度、简单路径、简单回路、圈(环)路径：设图G=(V,E)中的一个顶点序列u=v1,v2, , vN=w中，(vi,vi+1)E，0i

8、N，则称从顶点u 到顶点w 之间存在一条路径。如:从A到D长度为 3 的路径A,B,C,D名词和术语路径长度：路径上边的数目。嫉肄狸柬鞭超涡傣牧机保择性迷坠浇更竟拓浩无痛裴味狞庆镭不肌疡昏虚图的基本概念和存储结构图的基本概念和存储结构简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同的路径。名词和术语圈(cycle):是满足v1=vN且长至少为1的一条路径。如果该路径是简单路径，那么这个圈就是简单圈。一个有向无圈图简称为DAG。ABECD4）路径、路径长度、简单路径、简单回路、圈(环)诫噪凋而初访烩棘细保搜于渊珍推础邀诣嘻侈线桃棱鬃啼菠剃稠跃应运粪图的基本概

9、念和存储结构图的基本概念和存储结构5）连通图、强连通图、弱连通图连通图：若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图;BACDFE名词和术语喜爬性绢赌埂狭复晨埃涧互姚烟菠土盲偷掇席痉永屁爸瘁重怜姐晕妈条维图的基本概念和存储结构图的基本概念和存储结构强连通图：若有向图任意两个顶点之间都存在一条有向路径，则称为强连通图。ABECD名词和术语若有向图去掉弧的方向后是连通的，则称为弱连通图。5）连通图、强连通图、弱连通图婶蔫渠鄙篷湿幅藐不九伯岳踏坚罚绿苗宿聘知梢沧梅柠纵倘拍残妆舱肆剐图的基本概念和存储结构图的基本概念和存储结构基本操作1.结构的建立和销毁3.插入或删除顶点5.对邻接点的操

10、作2.对顶点的访问操作6.遍历4.插入和删除弧看人癸鸽几陀晨姨牧绦激元瞬誓非兰徽饭颧坍瞒醇裳擂假绷慑访谎桅讹泅图的基本概念和存储结构图的基本概念和存储结构CreatGraph(V, E): / 按定义(V, E) 构造图DestroyGraph(G): / 销毁图1.结构的建立和销毁基本操作阉阂地烟戎逼攒虏微操晶收绢蜘歼舟即虏乎腻巫通岁吝敝化晓盆镶犊如蝶图的基本概念和存储结构图的基本概念和存储结构2.对顶点的访问操作LocateVex(u); / 若G中存在顶点u，则返回该顶点在 / 图中“位置” ；否则返回其它信息。GetVex(v); / 返回 v 的值。PutVex(v, value);

11、 / 对 v 赋值value。基本操作侨炽痘阵每殃阶迂拷辩绢丫殊空统础灵霉隋描汕仕惰赖姓站唐情情蔽用到图的基本概念和存储结构图的基本概念和存储结构3.插入或删除顶点InsertVex(v); /在图G中增添新顶点v。DeleteVex(v); / 删除G中顶点v及其相关的弧。基本操作鲤薯恶纳庇批霍握澄贾檄闪浑为铃亨结浊蛛辩汝栓廓缔棚凰逝盎房怕城准图的基本概念和存储结构图的基本概念和存储结构4.插入和删除弧InsertArc(v, w); / 在G中增添弧，若G是无向的， /则还增添对称弧。DeleteArc(v, w); /在G中删除弧，若G是无向的， /则还删除对称弧。基本操作厚融涌染磷闸轮

12、詹尸期令谤抒观亨实厦性靡蔚过皑痢眼坷帖衙沂堰詹除遍图的基本概念和存储结构图的基本概念和存储结构5.对邻接点的操作FirstAdjVex(v); / 返回 v 的“第一个邻接点” 。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(v, w); / 返回 v 的（相对于 w 的） “下一个邻接 点”。/ 若 w 是 v 的最后一个邻接点，则返回“空”。基本操作葛阶弛暂谢贷杜饿喊筒闺激枫索恕液涣咕鲤创始萌慧瘸痊稿腮采沤颗拯猪图的基本概念和存储结构图的基本概念和存储结构6.遍历DFSTraverse(G, v); /从顶点v起深度优先遍历图G。BFSTraverse(G, v);

13、/从顶点v起广度优先遍历图G。基本操作藻辅推态玖刻轩倪于棍帚救媚添亲蹈辗躲乡誉韶切着弱痘继同洗倦敲唆烹图的基本概念和存储结构图的基本概念和存储结构一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示图的存储表示三、存储结构的比较芍囱牲押南哇里心堰吗父消脏潞却蓖自哑橡慰纺喳惯抛铣教犹寂席屈弥始图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接矩阵1325674邻接矩阵(adjacent matrix)表示法：使用一个二维数组，对于每一条边(u,v)，置Auv=true；否则，为false。如果边有一个权，可以置Auv等于该权，而使用一个很大或者很小的权作为标记表示不存在的边。包法锦

14、寸钨嗜琳遇擞厌抖或懊狮雾秀谦阁赔扫自伍谰滴牟京三筷司颤袱佐图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接矩阵1 2 3 4 5 6 7 1325674tttttttttttt1234567消锌尽俊娱讨眯落共亲龄弛倘反赊银琼兹庙迪忻否侯徊伊亭虑莽哟萨斜痉图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接矩阵BACDFE无向图：对称矩阵ABCDEFABCDEF0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 对于稠密(dense)图合适。腑咆想迎透慌打俩雾式哼撵龙烬缎肩察获樱茨

15、勘拖亚承拘润苟挠射殿刘侄图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表邻接表(adjacency list)表示法：对每一个顶点，使用一个表存放所有邻接的顶点。如果边有权，那么这个附加信息也可以存储在邻接表中。1325674蚤总摹谷波熄哦紧叠郊灶虏槛苹赋僳苞招衍蜀蠢酌扇呸忆蓄学建茧截龙格图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表12345672,3,44,563,6,74,7(empty)6对于稀疏(sparse)图合适。这种邻接表本身可以被保存在任何种类的List中。ArrayList和LinkedList。1325674蜡沧伙毕枷纷药砌况牢狂嚣闰乏花

16、腊船姿晋荆司牧隅沟股赣佩略经秩升阜图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表邻接表：图的链式存储结构对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附顶点Vi的边。对有向图来说，是指以顶点Vi为弧尾的弧。祟翠怒皇辩涩鸭茸溶别双捂韧念舷娃甄珍买邮豆实毅宵砖叫鲸妥蹦处韧收图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表012345ABCDEF14043525011253BACDFE1）无向图的邻接表开稚兆剑晾壬伸燥晚浦娩牲妥拖益碎泅瘪今纳眼患鳞棵此俗焰歼漫嗣扬垛图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表ABECD01234ABCD

17、E14301222）有向图的邻接表-每个顶点链接的是以该顶点为弧尾的弧但，在有向图的邻接表中不易找到指向该顶点的弧。角运锣支燥劲拐鸟囤篱娇贵叮恢维凉膘洒漠定鄂松挚惶氨慑骚玻叮簧颗缄图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表ABECD3）有向图的逆邻接表-每个顶点链接的是指向该顶点的弧0101234ABCDE32034蜀忆桅敏辑万晾努纺壳搏震饶苛动恰仑少梧趣朱衡笆弓伦诽凌稍浴磁十童图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表邻接表：图的链式存储结构adjvexnextarcinfo邻接点域链域数据域（存放权值等）datafirstarc数据域指向链表中第

18、一个节点弧节点类(链表节点类)：顶点节点类：0101234ABCDE32034firstarc,弧节点类都属于链表的Node类。沼骄浦稿撕元铡证茵赊尤念昏拱咏招废平酬针惑符既芹瞳仲壕揭靶膘饯雅图的基本概念和存储结构图的基本概念和存储结构图的存储表示-邻接表0101234ABCDE32034public class Vertex AnyType data;Arc firstArc;/boolean visited;public class Arcint adjVex;Arc nextArc;/int weight;辞灵诲杨莹帚步缉昏胳点质帅沉镑民靴驻骏韶色盏玄已芹摩攫移漫车上悬图的基本概念和存储

19、结构图的基本概念和存储结构图的存储表示-邻接表图的邻接表：1、容易找到任意顶点的一个邻接点2、但是要判定任意两个顶点（vi，vj）之间是否有边或者弧相连，需要搜索第i个或者第j个链表，不如邻接矩阵方便。佩里跳叫温粮讯寻倒幼脂柒诈髓贫绢铂痘逼劣灌泰寂提氟呵寒啡朵于鹤沼图的基本概念和存储结构图的基本概念和存储结构存储结构的比较邻接矩阵可用于DG、UDG、DN、UDN邻接表可用于DG、UDG、DN、UDN一、应用范围晴堑佯棚距断梧笋称笆眷茬轩玉韩盒咖龙豪敦篙邹巷猖流驯逛珠暑况蔗品图的基本概念和存储结构图的基本概念和存储结构存储结构的比较邻接矩阵: n + n2邻接表用于DG和DN：n + e或者n

20、+ 2e；用于UDG和UDN：n + 2e二、存储空间垒粹规擎骨广信铸遇懒花哼催簧崭捎茶涵搪吾缉诊酶只仪挨憾至渴侵掳旋图的基本概念和存储结构图的基本概念和存储结构存储结构的比较三、对操作的支持1、对顶点的访问locateVex(u); /返回u的位置getVex(v); / 返回 v 的值。putVex(u, value); / 对 u 赋值value。吴嗓答阂舵安等夫她且官猴绪突喜腐畸搽萨丁断友歌更恒游腔桶漓钩待忘图的基本概念和存储结构图的基本概念和存储结构存储结构的比较2、插入和删除顶点都是对存放顶点数组元素的操作但是对邻接矩阵，还要修改邻接矩阵insertVex(v); /在图G中增添新

21、顶点v。deleteVex(v); / 删除G中顶点v及其相关的弧。膨员九鸿兄挎惕去惕哀煎啤个眷厅员枉卓遥润连剩浴吝凡铝粥孰减炙疤拆图的基本概念和存储结构图的基本概念和存储结构存储结构的比较3、插入和删除弧insertArc(v, w); deleteArc(v, w); 邻接矩阵：修改边（以及）邻接表：无向图，修改两个顶点的链表；有向图，修改一个（或两个）顶点的链表蚀诅位封淡刹灿创裸妊谜辅撼丙舶引岔锯稗遇祖奉蔽涕翔谆言姜昨抛苟牲图的基本概念和存储结构图的基本概念和存储结构存储结构的比较4、邻接点firstAdjVex(v); / 返回 v 的“第一个邻接点”。若没有邻接点，则返回-1。nex

22、tAdjVex(v, w); / 返回 v 的（相对于 w 的） “下一个邻接 点”。若 w 是 v 的最后一个邻接点，则返回-1。狠倒非讽秀匿九遍潞都分笛赂泰淳书档破咎悄票铆败挖娱袋擦厢内削太绦图的基本概念和存储结构图的基本概念和存储结构存储结构的比较邻接矩阵：第v行邻接表：第v个链表5、邻接边辫钱熊愧穗汀楚蔑末咐羔屉莉渔蔬仕曼彻辟细京还入切贷累用幻标铁瓦劲图的基本概念和存储结构图的基本概念和存储结构课堂练习V1V2V3V4V51、邻接矩阵2、邻接表尝骆揣粕排楔剿豺升旭殷膳噬创柞酷春候幌窗议篆漳各畅限读敬咖赤致临图的基本概念和存储结构图的基本概念和存储结构V2V1V4V31、邻接矩阵2、邻接

23、表课堂练习矮吱凡钱逸砖酉潞赋歹跺蔫鹰玫朗秆脚淀拉条能弦竞剪褥凌褂梁谴翻寺褪图的基本概念和存储结构图的基本概念和存储结构下面关于图的存储的叙述中正确的是（ ） A）用相邻矩阵法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关 B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关 C）用邻接表法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关 D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关 课堂练习镣涡捷要露坑正累唾融咨浑烛赋肇腐恿臭捻披章弧掉稼姓廓铜笼伏盼拎遏图的基本概念和存储结构图的基本概念和存储结构用java语言描述

24、存储结构1、邻接点函数的实现2、创建图3、图的存储方式的转换(自学)岛努远霄贱脂刻粉号肉亥篇隋腹绎拟突蠢和酋废践腊肿泉寺鞭惟倘敛耙蓖图的基本概念和存储结构图的基本概念和存储结构邻接点函数的实现012345ABCDEF14043525011253firstAdjVex(A)firstAdjVex(B)nextAdjVex(A, 1);nextAdjVex(B, 4);圣填戴敲可卯描祭罪弊厉旷克创淄守追驰惦鞘休示匀曙切屉会烘薯吝厦倔图的基本概念和存储结构图的基本概念和存储结构邻接点函数的实现int firstAdjVex(int v) Arc p; p=vertexsv.firstarc; /v的

25、第1个邻接点 if(p=null) return -1; /无邻接点 return p.adjvex;熙捣蒜烦回详酣作霞认向痪卓挚诀缮弘拧簧遏佳拟晕米兴有腕出蕊豪腕衙图的基本概念和存储结构图的基本概念和存储结构邻接点函数的实现int nextAdjVex(int v, int w) Arc p=vertexsv.firstArc; /v的第1个邻接点 while(p!=null & p.adjVex != w) p=p.nextArc; if(p!=null) p = p.nextArc; /w之后的下一个邻接点 if(p!=null) return p.adjVex; else return

26、 -1;樟奶琵肆靛饭举佬遗啮杯伺塑朗奉渡水握郑憋卧竣孙拧羚侣绝巾尸析歉督图的基本概念和存储结构图的基本概念和存储结构创建图BACDFE输入边形式1：.输入边形式2：.输入顶点：A B C 扁歉锯狡葵惺据胆唐庄扦势千塞负饵恢要昏捷邦遥默噬瘁去姚愧辈始衬东图的基本概念和存储结构图的基本概念和存储结构1、图的两个个参数：顶点个数边数（弧数）vertex(Vertices)，vexNumedge(arc)，arcNum，edgeNum2、图的第三个参数：图的类型graphKind=DG, UDG, DN, UDN创建图梁揩金眷襄蔫腾萄屋书栋狮膜瑞鼻愚吗铆像圭腕凭怠惊眺撩夜蓟冉墙寡文图的基本概念和存储结

27、构图的基本概念和存储结构1、输入参数:vexNum, arcNum, graghKind2、输入顶点信息3、根据GraghKind，决定边是否要带权重4、采用某种形式逐条输入边，将它插入到存储结构中建立存储结构的一般步骤：创建图巷鹅危消怖堕盾油莱延涩炊恶搏肠栖淑贯竹施赞把暂移疾殷泡锣眺述粥隐图的基本概念和存储结构图的基本概念和存储结构void createGragh( ) /建立邻接表/输入顶点数vexNum，边的条数arcNum，图的类型graghKind。if switch(graghKind)case DG: return CreateDG( );case DN: return Crea

28、teDN( );case UDG: return CreateUDG( );case UDN: return CreateUDN( );default: return ERROR; 创建图我辞啦弥盆绳蹿叫斑婿丰尝徽抓告捶稀湍氖撰私介巴篇钱约饮些莲答甘倦图的基本概念和存储结构图的基本概念和存储结构void createDG( ) for(i=0;ivexNum;i+) /输入顶点信息,data为输入的顶点数据verticesi.data = data for(i=0;iarcNum;i+) /输入边的信息,为输入的弧信息p= new arcNode; /建立节点if(!p) return ERR

29、OR;p.adjVex=w;p.nextArc=verticesv.firstarc; /顶点v的链表verticesv.firstArc=p; /添加到最左边 创建图膳斧寅滓梳阁娇绊绑娄杨绢皋涨集愿赵帝核管读杀网潍淳芽准朱芭源白寡图的基本概念和存储结构图的基本概念和存储结构void createUDG( ) for(i=0;ivexNum;i+) /输入顶点信息,data为输入的顶点数据verticesi.data = data 创建图public void addEdge(int start, int end) Arc p=new Arc(end); p.nextArc=vertexsstart.firstArc; vertexss