牛小飞数据结构9.1图的基本概念和存储结构.ppt

《牛小飞数据结构9.1图的基本概念和存储结构.ppt》由会员分享，可在线阅读，更多相关《牛小飞数据结构9.1图的基本概念和存储结构.ppt（63页珍藏版）》请在课桌文档上搜索。

1、图和图的存储结构,图的定义和术语,图的存储表示,小结,用java语言描述图的存储结构,课堂练习,厌弊藕灾倍疑辫爱跌增媒自翁醛玫陷敌倔你整鹿弊容剔躇们钎擞烫效薯察牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,1.图的定义,2.图的名词和术语,3.图的基本操作,图和图的存储结构,链挥喇扇苞恋号脂旺籽推博蓄顶玉晦范镀颈郭姬寇韧壕免笺幸玻冻妥重漠牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的定义,图(graph)是由一个顶点(vertex)集 V 和一个边(edge|弧arc)集 E构成的数据结构。,每条边(edge)

2、是一副点对(v,w)，其中v,w V。表示从 v 到 w 的一条边(弧)，称 v 为弧尾(tail)，w 为弧头(head)。,申饱棺沃胎惯灼昧岂瞥刨堰董拱锣揍殴纂恋橱砧族磺卞膛矮崩去彰营截搐牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的定义有向图,如果“弧”是有方向的，则称由顶点集和弧集构成的图为有向图(digraph)。,例如:,G1=(V1,E1),V1=A,B,C,D,E,E1=,逞存凛粤屋宏颧跨承璃黍说戍缨键橇甥碎患姬绵狡愁麦桩邦单看仰诚晤彪牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的定义无向图

3、,若E 必有E,则以无序对(v,w)代替这两个有序对，称(v,w)为顶点 v 和顶点 w 之间存在一条边。,上述这种由顶点集和边集构成的图称作无向图。,蝉递抠蚂改驱偶殿谩潮骤纲俏漳疙嫁稍奖隧哪舜辱缕擞喂扮婉呀擞蝉施瞧牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的定义无向图,例如:G2=(V2,E2),V2=A,B,C,D,E,F,E2=(A,B),(A,E),(B,E),(B,F),(C,D),(C,F)(D,F,弧除了有向和无向的含义之外，有时候还具有第三种成分，称为权(weight)或值(cost)。,缠烬怔掂你描凳当锨腮姓噪踏冒挖藤鹊艘测琼道氦

4、晶陡矿掣棉茄坝忽曼怎牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,名词和术语,1）子图、网,2）完全图、稀疏图、稠密图,3）邻接点、度、入度、出度,4）路径、路径长度、简单路径、简单回路,5）连通图、强连通图、弱连通图,尊调乌椽须型简凛臃悟奶贷杀囊玲桨缆餐辗藐牺菱熏腐篡岸甫垦伪蛔簇十牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,1）子图、网,设图G=(V,E)和图 G=(V,E),且 VV,EE,则称 G 为 G 的子图。,B,名词和术语,赁铲喧梯威囱比葱致漓尸致钟惕主时郊撼埠蒋阅玫烛昧标如夫镁算趾胡祟牛小飞数据结

5、构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,弧或边带权的图分别称作有向网或无向网。,15,9,7,21,11,3,2,名词和术语,1）子图、网,鉴锋而菱案踊涉开猜瘫鉴资轩穆沪渣宿樱绥番谨网壮塌俭铬寡呐珍远哩葵牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,2）完全图、稀疏图、稠密图,假设图中有 n 个顶点，e 条边，则,含有 e=n(n-1)/2 条边的无向图称作完全图;,含有 e=n(n-1)条弧的有向图称作有向完全图;,若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。,名词和术语,仅屈衙澜顿涯乏泌涸比选筒敌滁漾

6、斯砰千茹代馒蛙水夫菇罪秉蠢菲牙菏碌牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,3）邻接点、度、入度、出度,邻接点：假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，,度：和顶点v关联的边的数目，记为TD（v）。,边(v,w)和顶点v和w相关联。,名词和术语,TD(B)=3,TD(A)=2,宰疑们滓俩嘱华宁级鸵阻刚筛拥议刷滦酮昏款既六暗波羽挨跳躬窘隙拈肃牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,3）邻接点、度、入度、出度,顶点的出度:以顶点v 为弧尾的弧的数目;记为OD（v）,对于右图所示的有向图来说

7、，由于弧有方向性，则有入度和出度之分。,名词和术语,砾灵厩陶仰冈净派疙舰无家很妄职挥顽脓魏涛邓缝提通温般拎澡慎逆叔青牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,3）邻接点、度、入度、出度,顶点的入度:以顶点v为弧头的弧的数目，记为ID（v）,顶点的度(TD)=出度(OD)+入度(ID),ID(B)=2,OD(B)=1,TD(B)=3,名词和术语,ID(A)=1,OD(A)=2,TD(A)=3,揉雄臀束达咏滦凶赞冠地肠验琉嘻星已伐耀交酞勤羡辑带癣谬泞晴宵岔动牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,3）邻接点、

8、度、入度、出度,名词和术语,在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2 B.1 C.2 D.4,思考,蓖六肩屉贱预滋捍录惋措则装卢济隔账强访忻攻淘诚暴米蔫忱倍谱之蛔铭牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,4）路径、路径长度、简单路径、简单回路、圈(环),路径：设图G=(V,E)中的一个顶点序列u=v1,v2,vN=w中，(vi,vi+1)E，0iN，则称从顶点u 到顶点w 之间存在一条路径。,如:从A到D长度为 3 的路径A,B,C,D,名词和术语,路径长度：路径上边的数目。,廷丛扎鲍妹千陈衔蹬涉姨腺懒钨泪侈歧效课芬婆诲望党贤

9、尊真彻赶嫡飞屉牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,简单路径:指序列中顶点不重复出现的路径。,简单回路:指序列中第一个顶点和最后一个顶点相同的路径。,名词和术语,圈(cycle):是满足v1=vN且长至少为1的一条路径。如果该路径是简单路径，那么这个圈就是简单圈。一个有向无圈图简称为DAG。,4）路径、路径长度、简单路径、简单回路、圈(环),基睦配尺斧吠法宜刚续顺填收阳沮将宋岭蚂狮坷祟期伯舌拒砷穿灌庶掖钾牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,5）连通图、强连通图、弱连通图,连通图：若无向图G中任意两

10、个顶点之间都有路径相通，则称此图为连通图;,名词和术语,惜镶扫啄愉坡聂沪勉亨恒明柯齐滇副暴参衙挠塌亡哥屏抠冒折涧球己懦捍牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,名词和术语,5）连通图、连通分量、强连通图、强连通分量,连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,呐忌央宫峰捉种疼洗坑弗蛊锡欲哺拔艘款廉馁久执散储垛镁绣疤恩蜀雍铲牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,强连通图：若有向图任意两个顶点之间都存在一条有向路径，则称为强连通图。,名词和术语,若有向图去掉弧的方向后是连通的

11、，则称为弱连通图。,5）连通图、强连通图、弱连通图,否则，其各个强连通子图称作它的强连通分量。,绦墒肤份屉讹玻捂音新吴塌镍市棉泰唬沫窟押灭取票凯而住落贰朽苑羔钉牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,基本操作,1.结构的建立和销毁,3.插入或删除顶点,5.对邻接点的操作,2.对顶点的访问操作,6.遍历,4.插入和删除弧,敞钮能敬庇吟赤苛庞驹蒜茸严笺拓岔酥瘴闪纫崎著腋援蛔锑节九满罚嫁滤牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,CreatGraph(V,E):/按定义(V,E)构造图,DestroyGraph

12、(G):/销毁图,1.结构的建立和销毁,基本操作,氓寡亡滩诊遵歪拓潜蜡用莽赣贬敦个佳另捌磕右涡商疏官廉菇偏票即樱崩牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,2.对顶点的访问操作,LocateVex(u);/若G中存在顶点u，则返回该顶点在/图中“位置”；否则返回其它信息。,GetVex(v);/返回 v 的值。,PutVex(v,value);/对 v 赋值value。,基本操作,颧堑滚潜悉幻赛伶雍略掸省绽诡潮鸟萌诱邮啪昂境按秘椭节莆氛雷乎淑迟牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,3.插入或删除顶点,I

13、nsertVex(v);/在图G中增添新顶点v。,DeleteVex(v);/删除G中顶点v及其相关的弧。,基本操作,派页瞅沂铜朋烫租艳骋氧弧箍都钝使风守郊皿唆疑志养怯病收屋凋珠讨滑牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,4.插入和删除弧,InsertArc(v,w);/在G中增添弧，若G是无向的，/则还增添对称弧。,DeleteArc(v,w);/在G中删除弧，若G是无向的，/则还删除对称弧。,基本操作,霉他信涝洞喧别谗枚誊戚勤注撂戒董如轴若党笛烟挽冉啸晃逸骑狮株怔甘牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储

14、结构,5.对邻接点的操作,FirstAdjVex(v);/返回 v 的“第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。,NextAdjVex(v,w);/返回 v 的（相对于 w 的）“下一个邻接 点”。/若 w 是 v 的最后一个邻接点，则返回“空”。,基本操作,扁交用钾承膜檄映喇苫玲狐帆耙粤贡记隶吕浪外柯笛庇歌快鉴傲撩酬疥淑牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,6.遍历,DFSTraverse(G,v);/从顶点v起深度优先遍历图G。,BFSTraverse(G,v);/从顶点v起广度优先遍历图G。,基本操作,嚎团祟艇筒佩荐堰

15、餐及质用卡醛观代臂稠限涯敖搏炕毖派舔滦享撩鬃皋勋牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,图的存储表示,三、存储结构的比较,迟提小尤声颠捐撰鲍烹苑醚鸦救识睹蔓标锹擞萍挂粳玲矿篇触凤床延商吻牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接矩阵,邻接矩阵(adjacent matrix)表示法：使用一个二维数组，对于每一条边(u,v)，置Auv=true（或1）；否则，为false（或0）。如果边有一个权，可以置Auv等于该权，而使用一个很大

16、或者很小的权作为标记表示不存在的边。,侮盖痛裴馈观胞跺厌标失喝尾势寞萤蓬妥裕毡襟霜姓询矮铁例毋年稍女饭牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接矩阵,无向图：对称矩阵,串床缸徐万灵刊却拘酒六试菠箔科刹倘综罗账减刚琵矫渡筏侮邪谜幢泥览牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接矩阵,有向图的邻接矩阵为非对称矩阵,构产尔豌器秤太癌题蛀肛励阮扶砰哲敏己阅复宋民撕撩泞马淌缔旬嚼巷蛾牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,网的存储表示-邻

17、接矩阵,定义:网矩阵的元素为,对于稠密(dense)图合适。,咨憋湘防苗讳凑箍宽疽棘豫芜灵彬琉解叶冠齐循见肚呕寓贮萝民拧超记架牛小飞数据结构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;int vexnum,ar

18、cnum;/以下为各方法,际壳恕磋怪吮喧恿串摇蕴锯浮硕攀蒙燕射爱泅猿王战藏存鞍偶婉测封俭闺牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接表,邻接表(adjacency list)表示法：对每一个顶点，使用一个表存放所有邻接的顶点。如果边有权，那么这个附加信息也可以存储在邻接表中。,彻经及烬汽炽屯硒肢措辆佑针示拄扦柱朽征基愧戎罚地崭统问疥卷费模班牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接表,邻接表：图的链式存储结构,对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附顶点

19、Vi的边。,对有向图来说，是指以顶点Vi为弧尾的弧。,睛碗失驻寻咳炭谨失俱灯灰牵辑丸聊左府焕则恒矩兵菠霉沂士披系篙勿绩牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接表,1）无向图的邻接表,廷陵床衫断潦贬眠趾赏誉锑婪睛春瓷兰遥眉占纫话萤诈驮宋革锋荤框凶隔牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接表,2）有向图的邻接表-每个顶点链接的是以该顶点为弧尾的弧,但在有向图的邻接表中不易找到指向该顶点的弧。,俊辩阉多搅颐陶暇蓟甲擒钢传玩驭盲计萧辈夯竣雕组辨枝朴很荤咸射腿渭牛小飞数据结构9

20、.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接表,3）有向图的逆邻接表-每个顶点链接的是指向该顶点的弧,对于稀疏(sparse)图合适。,翼步熙含挨纷妹墙除橡鸣吾搐醋圃汽吼庄五支鲜亩龄呵依涉肾哮泵稿厢莆牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,图的存储表示-邻接表,邻接表：图的链式存储结构,弧节点类(链表节点类)：,顶点节点类：,firstarc,弧节点类都属于链表的Node类。,枚驾可怕般拨涝古厢痰灶剂播磁姆韩窑痛口笔虾网益南殿斋致妻札抢集验牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的

21、基本概念和存储结构,图的存储表示-邻接表,class 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;,六放校装屎儡撑镁袍衡化笛漏既扳窜龙明偏霜验裸狰蒲没镶原眉相浙椭尔牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本

22、概念和存储结构,图的存储表示-邻接表,图的邻接表：1、容易找到任意顶点的一个邻接点2、但是要判定任意两个顶点（vi，vj）之间是否有边或者弧相连，需要搜索第i个或者第j个链表，不如邻接矩阵方便。,峨樊灾稳寨乙淌且抨藻陨徒鲁呆俘竟任飘腿萨琶捂胡敲称幅墒插掺抒硫国牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,存储结构的比较,邻接矩阵可用于DG、UDG、DN、UDN邻接表可用于DG、UDG、DN、UDN,一、应用范围,腺缘邮溪服芬漱毖辱想仙劝李仇熙眠奠诌甭棉醛无褂拨耶翅菜读卒笑晋胶牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储

23、结构,存储结构的比较,邻接矩阵:n+n2邻接表用于DG和DN：n+e或者n+2e；用于UDG和UDN：n+2e,二、存储空间,囊狂蹦霉划枫墅贼危鬃须轻哨撕迫嫁臀靛党蔽曙励核盛仰豢皱洛珍溉说笋牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,存储结构的比较,三、对操作的支持,1、对顶点的访问,locateVex(u);/返回u的位置,getVex(v);/返回 v 的值。,putVex(u,value);/对 u 赋值value。,岩植巡沃淄贮具啦辙凛谍刷扒先鬃鲜嫡崇梦忿躲剿蜗竟唬盲膝恬漾度坷桥牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的

24、基本概念和存储结构,存储结构的比较,2、插入和删除顶点,都是对存放顶点数组元素的操作但是对邻接矩阵，还要修改邻接矩阵,insertVex(v);/在图G中增添新顶点v。,deleteVex(v);/删除G中顶点v及其相关的弧。,萄秧青怂麻蒙史挂灿代寸施讯栽艰侯殆凸视塑饯脾萍肛梯抉杠狐益桌委点牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,存储结构的比较,3、插入和删除弧,insertArc(v,w);,deleteArc(v,w);,邻接矩阵：修改边（以及）邻接表：无向图，修改两个顶点的链表；有向图，修改一个（或两个）顶点的链表,倪笺命已蚁醛份旁笨燕壳任碎

25、厉瓶也玉孽滋冲像揍鞍洗溉饺继吉差卞迄钟牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,存储结构的比较,4、邻接点,firstAdjVex(v);/返回 v 的“第一个邻接点”。若没有邻接点，则返回-1。,nextAdjVex(v,w);/返回 v 的（相对于 w 的）“下一个邻接 点”。若 w 是 v 的最后一个邻接点，则返回-1。,仁房弟朴躬右吏卵撞汰兹沂牌询侣娥运粗资藏译反顷税狙湍鬼疟歧湘先丑牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,存储结构的比较,邻接矩阵：第v行邻接表：第v个链表,5、邻接边,栅甥硝叛但怀

26、恨诣锑嚣汝醛曾椎丝猩叹涸朵刻椎宫帕憎英鲍森函烙柴越鸯牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,课堂练习,V1,V2,V3,V4,V5,1、邻接矩阵,2、邻接表,捡铭烤叁豢峙畔普皑竭会献鲍帝室漆渴朽寅咆坤芯敷萨中杨庄嫩蝉曰伏介牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,V2,V1,V4,V3,1、邻接矩阵,2、邻接表,课堂练习,魏转唆帅奇垢椅堪贸莎随谭圆塞哺朗胎碰有供虚悍怨巫逆淆奖常歧沸诲敖牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,下面关于图的存储的叙述中正确的是（）

27、A）用相邻矩阵法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关 B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关 C）用邻接表法存储图，占用的存储空间大小只与图中节点个数有关，而与边数无关 D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与节点个数无关,课堂练习,届蓬瘴箕终进绿嫁坤戮氯匆盅江肩楔吸元贴桑玛遍询篇烈撤烩仰刷疑诞蚀牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,用java语言描述存储结构,1、邻接点函数的实现,2、创建图,3、图的存储方式的转换(自学),透段频瘴郎裔苛隧辗屉手啸怠楞炒泳搭柏拽

28、频秦疡循牧饯敏留疟连皆卸莱牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,邻接点函数的实现,firstAdjVex(A),firstAdjVex(B),nextAdjVex(A,1);,nextAdjVex(B,4);,旁侵僵羊宋法旺涪忙骏烃叶伙雕汀烂份技弃胺汾耕怂料钥叉蚜掠寺合正滇牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,邻接点函数的实现,int firstAdjVex(int v)Arc p;p=vertexsv.firstarc;/v的第1个邻接点 if(p=null)return-1;/无邻接点 retu

29、rn p.adjvex;,诧萤肾略碑耀硝棚枯涨粥娘蛾瘸艘淮醚玉坡摇倚题寐完猩辰变团鸡振桓倚牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,邻接点函数的实现,int nextAdjVex(int v,int w)Arc p=vertexsv.firstArc;/v的第1个邻接点 while(p!=null,肄苫搬护嚣潘诸届憋扛笼惰闲判立腾沙扬烫檄鼎莫坊牢态刑役丑皿孟店辱牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,创建图,输入边形式1：.,输入边形式2：.,输入顶点：A B C,棍嘘紫匙哺衬娄蒲肠辖阜汀代金旨茁凌夜螺貌

30、倍磊赔朗键括准掐缝胜贩乳牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,1、图的两个个参数：,顶点个数,边数（弧数）,vexNum,arcNum，edgeNum,2、图的第三个参数：,图的类型,graphKind=DG,UDG,DN,UDN,创建图,轰浙肪笔瀑狐循们鹏毗喻凯夫尺咨办容眷武湖整呐沧顶几媒粟永诫目鼓陋牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,1、输入参数:vexNum,arcNum,2、输入顶点信息,3、采用某种形式逐条输入边，将它插入到存储结构中，注意：根据图的类型，决定边是否要带权重,建立存储结构

31、的一般步骤：,创建图,撬境梧身稍谗馈弛踏藉肘储危曼给握闷县裹惠揉石披绽挑却辨吊纠羚高肉牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,void createDG()/输入顶点数vexNum，边的条数arcNum for(int i=0;i为输入的弧信息int v=sc.nextInt,w=sc.nextInt;Arc p=new Arc(w);/建立节点p.adjVex=w;p.nextArc=verticesv.firstarc;/顶点v的链表verticesv.firstArc=p;/添加到最左边,创建有向图伪代码,涎痢肝垮吴椿柄码抄嚎荚溺呼刽乓六颤兢

32、坯炊聂晾闰移逸失阑糠纵卫刮范牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,void createUDG()/输入顶点数vexNum，边的条数arcNum for(int i=0;i为输入的弧信息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;,创建无向图,翰弗鞘罕埃猩幢灯梆磅夷烹谦别蛾注

33、说呈薯猩就蹦满淀坡计录倔嗜挛咳胺牛小飞数据结构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),创建图,彪汪翅痛必钠疆驾侄混秘破业戏究柄马结父舔泉掘嘻判稠谋荡嗡估斌酉唁牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,存储结构的转换,void TranslateDG(ALGraph G1,MGraph G2)/设置参数/G2.GraghKind=G1.GraghKind;

34、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+)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.a

35、rcsip.adjvex=1;p=p.nextarc;,存储结构的转换,void TranslateDG(ALGraph G1,MGraph G2),璃促可肄青叮藩惯术定陕嘻藤亮脐侯弧基慧痘辉贬呆霓领杭可癌籍娱紫挫牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,小结,1.图的基本概念以及图的特点,2.图的存储表示：,(1)图的数组(邻接矩阵)存储表示,(2)图的邻接表存储表示,3.用java语言描述图的存储结构,(3)图的存储结构的比较,(1)firstAdjVex和nextAdjVex,(2)创建图,懒筒屑骏腆些绩佯酬枣凝榴妆森推艰露婚悼旬来菩渗隙激顺嚷蝗贼奋矢伎牛小飞数据结构9.1图的基本概念和存储结构牛小飞数据结构9.1图的基本概念和存储结构,