《牛小飞数据结构9.1图的基本概念和存储结构》由会员分享，可在线阅读，更多相关《牛小飞数据结构9.1图的基本概念和存储结构（63页珍藏版）》请在金锄头文库上搜索。
1、图和图的存储结构图和图的存储结构 图的定义和术语图的定义和术语 图的存储表示图的存储表示 小结小结用用java语言描述图的存储结语言描述图的存储结构构 课堂练习课堂练习厌厌弊弊藕藕灾灾倍倍疑疑辫辫爱爱跌跌增增媒媒自自翁翁醛醛玫玫陷陷敌敌倔倔你你整整鹿鹿弊弊容容剔剔躇躇们们钎钎擞擞烫烫效效薯薯察察牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构1. 图的定义图的定义2. 图的名词和术语图的名词和术语3. 图的基本操作图的基本操作图和图的存储结构图和图的存储结构链链挥挥喇喇扇扇苞苞恋恋号号脂
2、脂旺旺籽籽推推博博蓄蓄顶顶玉玉晦晦范范镀镀颈颈郭郭姬姬寇寇韧韧壕壕免免笺笺幸幸玻玻冻冻妥妥重重漠漠牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的定义图的定义 图(graph)是由一个顶点(vertex)集 V 和一个边(edge|弧arc)集 E构成的数据结构。每条边(edge)是一副点对(v,w)，其中v,w V。表示从 v 到 w 的一条边(弧)，称 v 为弧尾(tail)，w 为弧头(head)。申申饱饱棺棺沃沃胎胎惯惯灼灼昧昧岂岂瞥瞥刨刨堰堰董董拱拱锣锣揍揍殴殴纂纂恋恋橱橱
3、砧砧族族磺磺卞卞膛膛矮矮崩崩去去彰彰营营截截搐搐牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的定义图的定义有向图有向图 如果“弧”是有方向的，则称由顶点集和弧集构成的图为有向图有向图(digraph)。EACBD例如例如: :G1 = (V1, E1)V1=A, B, C, D, EE1=, , , , , , 逞逞存存凛凛粤粤屋屋宏宏颧颧跨跨承承璃璃黍黍说说戍戍缨缨键键橇橇甥甥碎碎患患姬姬绵绵狡狡愁愁麦麦桩桩邦邦单单看看仰仰诚诚晤晤彪彪牛牛小小飞飞数数据据结结构构9.1图图的的基
4、基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的定义图的定义无向图无向图若若 E 必有必有 E,则以无序对则以无序对(v,w) 代替这两个有序对，称代替这两个有序对，称 (v,w) 为顶点为顶点 v 和顶和顶点点 w 之间存在一条边。之间存在一条边。上述这种由顶点集和边集构成的图称作上述这种由顶点集和边集构成的图称作无向图无向图。蝉蝉递递抠抠蚂蚂改改驱驱偶偶殿殿谩谩潮潮骤骤纲纲俏俏漳漳疙疙嫁嫁稍稍奖奖隧隧哪哪舜舜辱辱缕缕擞擞喂喂扮扮婉婉呀呀擞擞蝉蝉施施瞧瞧牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结
5、结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的定义图的定义无向图无向图例如例如: : 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)。缠缠烬烬怔怔掂掂你你描描凳凳当当锨锨腮腮姓姓噪噪踏踏冒冒挖挖藤藤鹊鹊艘艘测测琼琼道道氦氦晶晶陡陡矿矿掣掣棉棉茄茄坝坝忽忽曼曼怎怎牛牛小小飞飞
6、数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构名词和术语名词和术语1 1）子图、网子图、网 2 2）完全图、稀疏图、稠密图完全图、稀疏图、稠密图3 3）邻接点、度、入度、出度邻接点、度、入度、出度4 4）路径、路径长度、简单路径、简单回路路径、路径长度、简单路径、简单回路5 5）连通图、强连通图、弱连通图连通图、强连通图、弱连通图尊尊调调乌乌椽椽须须型型简简凛凛臃臃悟悟奶奶贷贷杀杀囊囊玲玲桨桨缆缆餐餐辗辗藐藐牺牺菱菱熏熏腐腐篡篡岸岸甫甫垦垦伪伪蛔蛔簇簇十十牛牛小小飞飞数数据据结结构构9.1图图的的
7、基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构1）子图、网 设图G=(V,E) 和图 G=(V,E),且 VV, EE,则称 G 为 G 的子图。EACBDEACBDB名词和术语名词和术语赁赁铲铲喧喧梯梯威威囱囱比比葱葱致致漓漓尸尸致致钟钟惕惕主主时时郊郊撼撼埠埠蒋蒋阅阅玫玫烛烛昧昧标标如如夫夫镁镁算算趾趾胡胡祟祟牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构弧或边带权的图分别称作有向网或无向网。ABECD159721
8、1132名词和术语名词和术语1）子图、网 鉴鉴锋锋而而菱菱案案踊踊涉涉开开猜猜瘫瘫鉴鉴资资轩轩穆穆沪沪渣渣宿宿樱樱绥绥番番谨谨网网壮壮塌塌俭俭铬铬寡寡呐呐珍珍远远哩哩葵葵牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构2）完全图、稀疏图、稠密图假设图中有 n 个顶点，e 条边，则含有 e=n(n-1)/2 条边的无向图称作完全图;含有 e=n(n-1) 条弧的有向图称作有向完全图;若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。名词和术语名词和术语仅仅屈屈衙衙澜澜顿顿涯涯乏乏
9、泌泌涸涸比比选选筒筒敌敌滁滁漾漾斯斯砰砰千千茹茹代代馒馒蛙蛙水水夫夫菇菇罪罪秉秉蠢蠢菲菲牙牙菏菏碌碌牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构3）邻接点、度、入度、出度邻接点：假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，度：和顶点v关联的边的数目，记为TD（v）。边(v,w)和顶点v和w相关联。名词和术语名词和术语ACDFEBTD(B) = 3TD(A) = 2宰宰疑疑们们滓滓俩俩嘱嘱华华宁宁级级鸵鸵阻阻刚刚筛筛拥拥议议刷刷滦滦酮酮昏昏款款既既六六暗暗波波羽羽挨挨跳
10、跳躬躬窘窘隙隙拈拈肃肃牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构3）邻接点、度、入度、出度ABECD顶点的出度: 以顶点v 为弧尾的弧的数目;记为OD（v）对于右图所示的有向图来说，由于弧有方向性，则有入度和出度之分。名词和术语名词和术语砾砾灵灵厩厩陶陶仰仰冈冈净净派派疙疙舰舰无无家家很很妄妄职职挥挥顽顽脓脓魏魏涛涛邓邓缝缝提提通通温温般般拎拎澡澡慎慎逆逆叔叔青青牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的
11、基基本本概概念念和和存存储储结结构构3）邻接点、度、入度、出度顶点的入度: 以顶点v为弧头的弧的数目，记为ID（v）顶点的度(TD)=出度(OD)+入度(ID)ID(B) = 2OD(B) = 1TD(B) = 3名词和术语名词和术语ABECDID(A) = 1OD(A) = 2TD(A) = 3揉揉雄雄臀臀束束达达咏咏滦滦凶凶赞赞冠冠地地肠肠验验琉琉嘻嘻星星已已伐伐耀耀交交酞酞勤勤羡羡辑辑带带癣癣谬谬泞泞晴晴宵宵岔岔动动牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构3）邻接点、度、入
12、度、出度名词和术语名词和术语ABECD在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A.1/2 B.1 C.2 D.4ACDFEB思考思考蓖蓖六六肩肩屉屉贱贱预预滋滋捍捍录录惋惋措措则则装装卢卢济济隔隔账账强强访访忻忻攻攻淘淘诚诚暴暴米米蔫蔫忱忱倍倍谱谱之之蛔蛔铭铭牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构ABECD4）路径、路径长度、简单路径、简单回路、圈(环)路径：设图G=(V,E)中的一个顶点序列u=v1,v2, , vN=w中，(vi,vi+1)E，0iN，则称从
13、顶点u 到顶点w 之间存在一条路径。如:从A到D长度为 3 的路径A,B,C,D名词和术语名词和术语路径长度：路径上边的数目。廷廷丛丛扎扎鲍鲍妹妹千千陈陈衔衔蹬蹬涉涉姨姨腺腺懒懒钨钨泪泪侈侈歧歧效效课课芬芬婆婆诲诲望望党党贤贤尊尊真真彻彻赶赶嫡嫡飞飞屉屉牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同的路径。名词和术语名词和术语圈(cycle):是满足v1=vN且长至少为1的一条路径。如果该路径是简单路
14、径，那么这个圈就是简单圈。一个有向无圈图简称为DAG。ABECD4）路径、路径长度、简单路径、简单回路、圈(环)基基睦睦配配尺尺斧斧吠吠法法宜宜刚刚续续顺顺填填收收阳阳沮沮将将宋宋岭岭蚂蚂狮狮坷坷祟祟期期伯伯舌舌拒拒砷砷穿穿灌灌庶庶掖掖钾钾牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构5）连通图、强连通图、弱连通图连通图：若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图;BACDFE名词和术语名词和术语惜惜镶镶扫扫啄啄愉愉坡坡聂聂沪沪勉勉亨亨恒恒明明柯柯齐齐滇滇副副暴暴参参衙
15、衙挠挠塌塌亡亡哥哥屏屏抠抠冒冒折折涧涧球球己己懦懦捍捍牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构名词和术语名词和术语5 5）连通图、连通分量、强连通图、强连通分量）连通图、连通分量、强连通图、强连通分量连通分量：连通分量：若无向图为非若无向图为非连通图，则图中各个极大连通图，则图中各个极大连通子图称作连通子图称作此图的连通此图的连通分量。分量。BACDFE呐呐忌忌央央宫宫峰峰捉捉种种疼疼洗洗坑坑弗弗蛊蛊锡锡欲欲哺哺拔拔艘艘款款廉廉馁馁久久执执散散储储垛垛镁镁绣绣疤疤恩恩蜀蜀雍雍铲铲
16、牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构强连通图：若有向图任意两个顶点之间都存在一条有向路径，则称为强连通图。ABECD名词和术语名词和术语若有向图去掉弧的方向后是连通的，则称为弱连通图。5）连通图、强连通图、弱连通图否则，其各个强连通子图称否则，其各个强连通子图称作它的作它的强连通分量强连通分量。ABECD绦绦墒墒肤肤份份屉屉讹讹玻玻捂捂音音新新吴吴塌塌镍镍市市棉棉泰泰唬唬沫沫窟窟押押灭灭取取票票凯凯而而住住落落贰贰朽朽苑苑羔羔钉钉牛牛小小飞飞数数据据结结构构9.1图图的的基基
17、本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构基本操作基本操作1.结构的建立和销毁结构的建立和销毁3.插入或删除顶点插入或删除顶点5.对邻接点的操作对邻接点的操作2.对顶点的访问操作对顶点的访问操作6.遍历遍历4.插入和删除弧插入和删除弧敞敞钮钮能能敬敬庇庇吟吟赤赤苛苛庞庞驹驹蒜蒜茸茸严严笺笺拓拓岔岔酥酥瘴瘴闪闪纫纫崎崎著著腋腋援援蛔蛔锑锑节节九九满满罚罚嫁嫁滤滤牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构CreatGr
18、aph(V, E): / 按定义(V, E) 构造图DestroyGraph(G): / 销毁图1.结构的建立和销毁结构的建立和销毁基本操作基本操作氓氓寡寡亡亡滩滩诊诊遵遵歪歪拓拓潜潜蜡蜡用用莽莽赣赣贬贬敦敦个个佳佳另另捌捌磕磕右右涡涡商商疏疏官官廉廉菇菇偏偏票票即即樱樱崩崩牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构2.对顶点的访问操作对顶点的访问操作LocateVex(u); / 若G中存在顶点u，则返回该顶点在 / 图中“位置位置” ；否则返回其它信息。GetVex(v); /
19、 返回 v 的值。PutVex(v, value); / 对 v 赋值value。基本操作基本操作颧颧堑堑滚滚潜潜悉悉幻幻赛赛伶伶雍雍略略掸掸省省绽绽诡诡潮潮鸟鸟萌萌诱诱邮邮啪啪昂昂境境按按秘秘椭椭节节莆莆氛氛雷雷乎乎淑淑迟迟牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构3.插入或删除顶点插入或删除顶点InsertVex(v); /在图G中增添新顶点v。DeleteVex(v); / 删除G中顶点v及其相关的弧。基本操作基本操作派派页页瞅瞅沂沂铜铜朋朋烫烫租租艳艳骋骋氧氧弧弧箍箍都都钝
20、钝使使风风守守郊郊皿皿唆唆疑疑志志养养怯怯病病收收屋屋凋凋珠珠讨讨滑滑牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构4.插入和删除弧插入和删除弧InsertArc(v, w); / 在G中增添弧，若G是无向的， /则还增添对称弧。DeleteArc(v, w); /在G中删除弧，若G是无向的， /则还删除对称弧。基本操作基本操作霉霉他他信信涝涝洞洞喧喧别别谗谗枚枚誊誊戚戚勤勤注注撂撂戒戒董董如如轴轴若若党党笛笛烟烟挽挽冉冉啸啸晃晃逸逸骑骑狮狮株株怔怔甘甘牛牛小小飞飞数数据据结结构构9.
21、1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构5.对邻接点的操作对邻接点的操作FirstAdjVex(v); / 返回 v 的“第一个邻接点第一个邻接点” 。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(v, w); / 返回 v 的（相对于 w 的） “下一个邻接下一个邻接 点点”。/ 若 w 是 v 的最后一个邻接点，则返回“空”。基本操作基本操作扁扁交交用用钾钾承承膜膜檄檄映映喇喇苫苫玲玲狐狐帆帆耙耙粤粤贡贡记记隶隶吕吕浪浪外外柯柯笛笛庇庇歌歌快快鉴鉴傲傲撩撩酬酬疥疥淑淑牛牛小小飞飞数数据
22、据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构6.6.遍历遍历DFSTraverse(G, v); /从顶点v起深度优先深度优先遍历图G。BFSTraverse(G, v); /从顶点v起广度优先广度优先遍历图G。基本操作基本操作嚎嚎团团祟祟艇艇筒筒佩佩荐荐堰堰餐餐及及质质用用卡卡醛醛观观代代臂臂稠稠限限涯涯敖敖搏搏炕炕毖毖派派舔舔滦滦享享撩撩鬃鬃皋皋勋勋牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结
23、结构构一、一、图的数组图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示二、二、图的邻接表存储表示图的邻接表存储表示图的存储表示图的存储表示三、三、存储结构的比较存储结构的比较迟迟提提小小尤尤声声颠颠捐捐撰撰鲍鲍烹烹苑苑醚醚鸦鸦救救识识睹睹蔓蔓标标锹锹擞擞萍萍挂挂粳粳玲玲矿矿篇篇触触凤凤床床延延商商吻吻牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接矩阵1325674邻接矩阵(adjacent matrix)表示法：使用一个二维数组，对于每一条边(u,v)
24、，置Auv=true（或1）；否则，为false （或0） 。如果边有一个权，可以置Auv等于该权，而使用一个很大或者很小的权作为标记表示不存在的边。侮侮盖盖痛痛裴裴馈馈观观胞胞跺跺厌厌标标失失喝喝尾尾势势寞寞萤萤蓬蓬妥妥裕裕毡毡襟襟霜霜姓姓询询矮矮铁铁例例毋毋年年稍稍女女饭饭牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接矩阵BACDFE无向图：对称矩阵无向图：对称矩阵0123450123450 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1
25、0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 012345ABCDEF串串床床缸缸徐徐万万灵灵刊刊却却拘拘酒酒六六试试菠菠箔箔科科刹刹倘倘综综罗罗账账减减刚刚琵琵矫矫渡渡筏筏侮侮邪邪谜谜幢幢泥泥览览牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接矩阵ABECD有向图的邻接矩阵为非对称矩阵有向图的邻接矩阵为非对称矩阵0 1 2 3 40 1 2 3 4 01234ABCDE构构产产尔尔豌豌器器秤秤太太癌癌题题蛀蛀肛肛励励阮阮扶
26、扶砰砰哲哲敏敏己己阅阅复复宋宋民民撕撕撩撩泞泞马马淌淌缔缔旬旬嚼嚼巷巷蛾蛾牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构网的存储表示网的存储表示-邻接矩阵0 1 2 3 40 1 2 3 4 定义定义: :网矩阵的元素为网矩阵的元素为 A Aijij= = (i,j) (i,j) R Rw wijij (i,j) (i,j) R RABECD1597211132l对于稠密(dense)图合适。01234ABCDE咨咨憋憋湘湘防防苗苗讳讳凑凑箍箍宽宽疽疽棘棘豫豫芜芜灵灵彬彬琉琉解解叶叶冠
27、冠齐齐循循见见肚肚呕呕寓寓贮贮萝萝民民拧拧超超记记架架牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接矩阵class Vertex AnyType data; boolean visited; public Vertex(AnyType d) data=d; visited=false; public class MatrixGraph static final int MAX_VERTEX_NUM=20; Vertex vexs; int arcs; in
28、t vexnum,arcnum; /以下为各方法0 1 2 3 40 1 2 3 4 01234ABCDE际际壳壳恕恕磋磋怪怪吮吮喧喧恿恿串串摇摇蕴蕴锯锯浮浮硕硕攀攀蒙蒙燕燕射射爱爱泅泅猿猿王王战战藏藏存存鞍鞍偶偶婉婉测测封封俭俭闺闺牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接表邻接表(adjacency list)表示法：对每一个顶点，使用一个表存放所有邻接的顶点。如果边有权，那么这个附加信息也可以存储在邻接表中。1325674彻彻经经及及烬烬汽汽炽炽
29、屯屯硒硒肢肢措措辆辆佑佑针针示示拄拄扦扦柱柱朽朽征征基基愧愧戎戎罚罚地地崭崭统统问问疥疥卷卷费费模模班班牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接表邻接表：图的链式存储结构邻接表：图的链式存储结构对图中每个顶点建立一个单链表，第对图中每个顶点建立一个单链表，第i个单链个单链表中的节点表示依附顶点表中的节点表示依附顶点Vi的边。的边。对有向图来说，是指以顶点对有向图来说，是指以顶点Vi为弧尾的弧。为弧尾的弧。睛睛碗碗失失驻驻寻寻咳咳炭炭谨谨失失俱俱灯灯灰
30、灰牵牵辑辑丸丸聊聊左左府府焕焕则则恒恒矩矩兵兵菠菠霉霉沂沂士士披披系系篙篙勿勿绩绩牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接表012345ABCDEF14043525011253BACDFE1）无向图的邻接表）无向图的邻接表廷廷陵陵床床衫衫断断潦潦贬贬眠眠趾趾赏赏誉誉锑锑婪婪睛睛春春瓷瓷兰兰遥遥眉眉占占纫纫话话萤萤诈诈驮驮宋宋革革锋锋荤荤框框凶凶隔隔牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构
31、构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接表ABECD01234ABCDE14301222）有向图的邻接表）有向图的邻接表-每个顶点链接的是以该顶点为每个顶点链接的是以该顶点为弧尾的弧弧尾的弧但在有向图的邻接表中不易找到指向该顶点的弧。但在有向图的邻接表中不易找到指向该顶点的弧。俊俊辩辩阉阉多多搅搅颐颐陶陶暇暇蓟蓟甲甲擒擒钢钢传传玩玩驭驭盲盲计计萧萧辈辈夯夯竣竣雕雕组组辨辨枝枝朴朴很很荤荤咸咸射射腿腿渭渭牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结
32、构构图的存储表示图的存储表示-邻接表ABECD3）有向图的逆邻接表）有向图的逆邻接表-每个顶点链接的是指向该每个顶点链接的是指向该顶点的弧顶点的弧0101234ABCDE32034l对于稀疏(sparse)图合适。翼翼步步熙熙含含挨挨纷纷妹妹墙墙除除橡橡鸣鸣吾吾搐搐醋醋圃圃汽汽吼吼庄庄五五支支鲜鲜亩亩龄龄呵呵依依涉涉肾肾哮哮泵泵稿稿厢厢莆莆牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接表邻接表：图的链式存储结构邻接表：图的链式存储结构adjvex next
33、arcinfo邻接点域邻接点域链域链域数据域（存放权值等）数据域（存放权值等）datafirstarc数据域数据域指向链表中第一个节点指向链表中第一个节点弧节点类弧节点类(链表节点类链表节点类)：顶点节点类顶点节点类：0101234ABCDE32034firstarc,弧节点类都属于链表的Node类。枚枚驾驾可可怕怕般般拨拨涝涝古古厢厢痰痰灶灶剂剂播播磁磁姆姆韩韩窑窑痛痛口口笔笔虾虾网网益益南南殿殿斋斋致致妻妻札札抢抢集集验验牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图
34、的存储表示-邻接表0101234ABCDE32034class Ver AnyType data;Arc firstArc;boolean visited;class Arcint adjVex;Arc nextArc;/int weight;public class AdjGraph static final int MAX_VERTEX_NUM=20; Ver vertexs=new Vertex MAX_VERTEX_NUM; int vexnum,arcnum;六六放放校校装装屎屎儡儡撑撑镁镁袍袍衡衡化化笛笛漏漏既既扳扳窜窜龙龙明明偏偏霜霜验验裸裸狰狰蒲蒲没没镶镶原原眉眉相相浙浙椭椭尔
35、尔牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构图的存储表示图的存储表示-邻接表图的邻接表：1、容易找到任意顶点的一个邻接点2、但是要判定任意两个顶点（vi，vj）之间是否有边或者弧相连，需要搜索第i个或者第j个链表，不如邻接矩阵方便。峨峨樊樊灾灾稳稳寨寨乙乙淌淌且且抨抨藻藻陨陨徒徒鲁鲁呆呆俘俘竟竟任任飘飘腿腿萨萨琶琶捂捂胡胡敲敲称称幅幅墒墒插插掺掺抒抒硫硫国国牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本
36、本概概念念和和存存储储结结构构存储结构的比较存储结构的比较邻接矩阵可用于DG、UDG、DN、UDN邻接表可用于DG、UDG、DN、UDN一、应用范围腺腺缘缘邮邮溪溪服服芬芬漱漱毖毖辱辱想想仙仙劝劝李李仇仇熙熙眠眠奠奠诌诌甭甭棉棉醛醛无无褂褂拨拨耶耶翅翅菜菜读读卒卒笑笑晋晋胶胶牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构存储结构的比较存储结构的比较邻接矩阵: n + n2邻接表用于DG和DN：n + e或者n + 2e；用于UDG和UDN：n + 2e二、存储空间囊囊狂狂蹦蹦霉霉划划枫
37、枫墅墅贼贼危危鬃鬃须须轻轻哨哨撕撕迫迫嫁嫁臀臀靛靛党党蔽蔽曙曙励励核核盛盛仰仰豢豢皱皱洛洛珍珍溉溉说说笋笋牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构存储结构的比较存储结构的比较三、对操作的支持1、对顶点的访问locateVex(u); /返回u的位置getVex(v); / 返回 v 的值。putVex(u, value); / 对 u 赋值value。岩岩植植巡巡沃沃淄淄贮贮具具啦啦辙辙凛凛谍谍刷刷扒扒先先鬃鬃鲜鲜嫡嫡崇崇梦梦忿忿躲躲剿剿蜗蜗竟竟唬唬盲盲膝膝恬恬漾漾度度坷坷桥桥牛
38、牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构存储结构的比较存储结构的比较2、插入和删除顶点都是对存放顶点数组元素的操作但是对邻接矩阵，还要修改邻接矩阵insertVex(v); /在图G中增添新顶点v。deleteVex(v); / 删除G中顶点v及其相关的弧。萄萄秧秧青青怂怂麻麻蒙蒙史史挂挂灿灿代代寸寸施施讯讯栽栽艰艰侯侯殆殆凸凸视视塑塑饯饯脾脾萍萍肛肛梯梯抉抉杠杠狐狐益益桌桌委委点点牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结
39、结构构9.1图图的的基基本本概概念念和和存存储储结结构构存储结构的比较存储结构的比较3、插入和删除弧insertArc(v, w); deleteArc(v, w); 邻接矩阵：修改边（以及）邻接表：无向图，修改两个顶点的链表；有向图，修改一个（或两个）顶点的链表倪倪笺笺命命已已蚁蚁醛醛份份旁旁笨笨燕燕壳壳任任碎碎厉厉瓶瓶也也玉玉孽孽滋滋冲冲像像揍揍鞍鞍洗洗溉溉饺饺继继吉吉差差卞卞迄迄钟钟牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构存储结构的比较存储结构的比较4、邻接点firstAd
40、jVex(v); / 返回 v 的“第一个邻接点第一个邻接点”。若没有邻接点，则返回-1。nextAdjVex(v, w); / 返回 v 的（相对于 w 的） “下一个邻接下一个邻接 点点”。若 w 是 v 的最后一个邻接点，则返回-1。仁仁房房弟弟朴朴躬躬右右吏吏卵卵撞撞汰汰兹兹沂沂牌牌询询侣侣娥娥运运粗粗资资藏藏译译反反顷顷税税狙狙湍湍鬼鬼疟疟歧歧湘湘先先丑丑牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构存储结构的比较存储结构的比较邻接矩阵：第v行邻接表：第v个链表5、邻接边栅栅
41、甥甥硝硝叛叛但但怀怀恨恨诣诣锑锑嚣嚣汝汝醛醛曾曾椎椎丝丝猩猩叹叹涸涸朵朵刻刻椎椎宫宫帕帕憎憎英英鲍鲍森森函函烙烙柴柴越越鸯鸯牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构课堂练习课堂练习V1V2V3V4V51、邻接矩阵2、邻接表捡捡铭铭烤烤叁叁豢豢峙峙畔畔普普皑皑竭竭会会献献鲍鲍帝帝室室漆漆渴渴朽朽寅寅咆咆坤坤芯芯敷敷萨萨中中杨杨庄庄嫩嫩蝉蝉曰曰伏伏介介牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念
42、念和和存存储储结结构构V2V1V4V31、邻接矩阵2、邻接表课堂练习课堂练习魏魏转转唆唆帅帅奇奇垢垢椅椅堪堪贸贸莎莎随随谭谭圆圆塞塞哺哺朗朗胎胎碰碰有有供供虚虚悍悍怨怨巫巫逆逆淆淆奖奖常常歧歧沸沸诲诲敖敖牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构下面关于图的存储的叙述中正确的是（ ） A）用相邻矩阵法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关 B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关 C）用邻接表法存储图，占用的存储空间大小只与
43、图中节点个数有关，而与边数无关 D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关 课堂练习课堂练习届届蓬蓬瘴瘴箕箕终终进进绿绿嫁嫁坤坤戮戮氯氯匆匆盅盅江江肩肩楔楔吸吸元元贴贴桑桑玛玛遍遍询询篇篇烈烈撤撤烩烩仰仰刷刷疑疑诞诞蚀蚀牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构用用javajava语言描述存储结构语言描述存储结构1 1、邻接点函数的实现邻接点函数的实现2 2、创建图创建图3 3、图的存储方式的转换图的存储方式的转换( (自学自学) )透透段段频频瘴瘴
44、郎郎裔裔苛苛隧隧辗辗屉屉手手啸啸怠怠楞楞炒炒泳泳搭搭柏柏拽拽频频秦秦疡疡循循牧牧饯饯敏敏留留疟疟连连皆皆卸卸莱莱牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构邻接点函数的实现邻接点函数的实现012345ABCDEF14043525011253firstAdjVex(A)firstAdjVex(B)nextAdjVex(A, 1);nextAdjVex(B, 4);旁旁侵侵僵僵羊羊宋宋法法旺旺涪涪忙忙骏骏烃烃叶叶伙伙雕雕汀汀烂烂份份技技弃弃胺胺汾汾耕耕怂怂料料钥钥叉叉蚜蚜掠掠寺寺合合正正
45、滇滇牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构邻接点函数的实现邻接点函数的实现int firstAdjVex(int v) Arc p; p=vertexsv.firstarc; /v的第1个邻接点 if(p=null) return -1; /无邻接点 return p.adjvex;诧诧萤萤肾肾略略碑碑耀耀硝硝棚棚枯枯涨涨粥粥娘娘蛾蛾瘸瘸艘艘淮淮醚醚玉玉坡坡摇摇倚倚题题寐寐完完猩猩辰辰变变团团鸡鸡振振桓桓倚倚牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储
46、结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构邻接点函数的实现邻接点函数的实现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 -1;肄肄苫苫搬搬护护嚣嚣潘潘诸诸届届憋憋扛扛笼笼惰惰闲闲判判立立腾腾沙沙扬扬烫烫檄檄鼎鼎莫莫坊坊牢牢态态
47、刑刑役役丑丑皿皿孟孟店店辱辱牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构创建图创建图BACDFE输入边形式1：.输入边形式2：.输入顶点：A B C 棍棍嘘嘘紫紫匙匙哺哺衬衬娄娄蒲蒲肠肠辖辖阜阜汀汀代代金金旨旨茁茁凌凌夜夜螺螺貌貌倍倍磊磊赔赔朗朗键键括括准准掐掐缝缝胜胜贩贩乳乳牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构1、图的两个个参数：顶点个数边数（弧数）vexNuma
48、rcNum，edgeNum2、图的第三个参数：图的类型graphKind=DG, UDG, DN, UDN创建图创建图轰轰浙浙肪肪笔笔瀑瀑狐狐循循们们鹏鹏毗毗喻喻凯凯夫夫尺尺咨咨办办容容眷眷武武湖湖整整呐呐沧沧顶顶几几媒媒粟粟永永诫诫目目鼓鼓陋陋牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构1、输入参数:vexNum, arcNum2、输入顶点信息3、采用某种形式逐条输入边，将它插入到存储结构中，注意：根据图的类型，决定边是否要带权重建立存储结构的一般步骤：创建图创建图撬撬境境梧梧身身
49、稍稍谗谗馈馈弛弛踏踏藉藉肘肘储储危危曼曼给给握握闷闷县县裹裹惠惠揉揉石石披披绽绽挑挑却却辨辨吊吊纠纠羚羚高高肉肉牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构void createDG( ) /输入顶点数vexNum，边的条数arcNum for(int i=0;ivexNum;i+) /输入顶点信息,data为输入的顶点数据vertexsi.data = sc.next; for(int j=0;jarcNum;j+) /输入边的信息,为输入的弧信息int v=sc.nextInt,
50、 w=sc.nextInt; Arc p= new Arc(w); /建立节点p.adjVex=w;p.nextArc=verticesv.firstarc; /顶点v的链表verticesv.firstArc=p; /添加到最左边 创建有向图伪代码创建有向图伪代码涎涎痢痢肝肝垮垮吴吴椿椿柄柄码码抄抄嚎嚎荚荚溺溺呼呼刽刽乓乓六六颤颤兢兢坯坯炊炊聂聂晾晾闰闰移移逸逸失失阑阑糠糠纵纵卫卫刮刮范范牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构void createUDG( ) /输入顶点数v
51、exNum，边的条数arcNum for(int i=0;ivexNum;i+) /输入顶点信息,data为输入的顶点数据vertexsi.data = sc.next; for(int j=0;jarcNum;j+) /输入边的信息,为输入的弧信息int v=sc.nextInt, w=sc.nextInt; Arc p=new Arc(w); p.nextArc=vertexsv.firstArc; vertexsv.firstArc=p; Arc q=new Arc(v); q.nextArc=vertexsw.firstArc; vertexsw.firstArc=q; 创建无向图创建
52、无向图翰翰弗弗鞘鞘罕罕埃埃猩猩幢幢灯灯梆梆磅磅夷夷烹烹谦谦别别蛾蛾注注说说呈呈薯薯猩猩就就蹦蹦满满淀淀坡坡计计录录倔倔嗜嗜挛挛咳咳胺胺牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构时间复杂度分析(第2种输入形式)第1个for: n第2个for: e所以O(n + e)时间复杂度分析(第1种输入形式)第1个for: n第2个for: n.e所以O(n.e)创建图创建图彪彪汪汪翅翅痛痛必必钠钠疆疆驾驾侄侄混混秘秘破破业业戏戏究究柄柄马马结结父父舔舔泉泉掘掘嘻嘻判判稠稠谋谋荡荡嗡嗡估估斌斌酉
53、酉唁唁牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构存储结构的转换存储结构的转换void TranslateDG(ALGraph G1, MGraph G2) /设置参数 /G2.GraghKind = G1.GraghKind; G2.vexNum = G1.vexNum; G2.arcNum = G1.arcNum /复制顶点 for(i=0;iG1.vexNum;i+) G2.vexsi = G1.vertexsi.data; /复制弧 for(i=0;iG2.vexNum;i+
54、) for(j=0;jG2.vexNum;j+)G2.arcsij=0; 浦浦昭昭熊熊龄龄娜娜访访贯贯婶婶驶驶翟翟旭旭泄泄掺掺馏馏葛葛脂脂很很汲汲雹雹颂颂筷筷输输芭芭冈冈坍坍港港炯炯糟糟梧梧瞒瞒氛氛霓霓牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构 for(i=0;iG1.vexNum;i+) /复制G1每个顶点的邻接点p=G1.vertexsi.firstarc;while(p)G2.arcsip.adjvex=1;p=p.nextarc; 存储结构的转换存储结构的转换void Tr
55、anslateDG(ALGraph G1, MGraph G2) 璃璃促促可可肄肄青青叮叮藩藩惯惯术术定定陕陕嘻嘻藤藤亮亮脐脐侯侯弧弧基基慧慧痘痘辉辉贬贬呆呆霓霓领领杭杭可可癌癌籍籍娱娱紫紫挫挫牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构小结小结1.图的基本概念以及图的特点图的基本概念以及图的特点2.图的存储表示：图的存储表示：(1)图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 (2)图的邻接表存储表示图的邻接表存储表示 3.用用java语言描述图的存储结构语言描述图的存储结构(3)图的存储结构的比较图的存储结构的比较 (1)firstAdjVex和和nextAdjVex (2)创建图创建图 懒懒筒筒屑屑骏骏腆腆些些绩绩佯佯酬酬枣枣凝凝榴榴妆妆森森推推艰艰露露婚婚悼悼旬旬来来菩菩渗渗隙隙激激顺顺嚷嚷蝗蝗贼贼奋奋矢矢伎伎牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构牛牛小小飞飞数数据据结结构构9.1图图的的基基本本概概念念和和存存储储结结构构
