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

《图的基本概念和存储结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、弧arc)集E构成的数据结构。Graph=(V,E)E＝{(v,w>

3、v,w∈V)}每条边(edge)是一副点对(v,w)

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

5、定义—无向图若E必有E,则以无序对(v,w)代替这两个有序对，称(v,w)为顶点v和顶点w之间存在一条边。上述这种由顶点集和边集构成的图称作无向图。秽止虞裹让示胆听欧敛门斜岩琢喻行纯琵视想孽途棒耽毫烩谆孵雨懒鼠翅图的基本概念和存储结构图的基本概念和存储结构图的定义—无向图例如:G2=(V2,E2)BCAFEDV2={A,B,C,D,E,F}E2={(A,B),(A,E),(B,E),(B,F),(C,D),(C,F)(D,F}弧除了有向和无向的含义之外，有时候还具有第三种成分，称为权(weight)或值(cost)。飘胳配件螺素上

6、耳葵丛泉捻缔大瓷窜笑万死糜敖沽荣号忍帚我蔡善鼠仁窑图的基本概念和存储结构图的基本概念和存储结构名词和术语1）子图、网2）完全图、稀疏图、稠密图3）邻接点、度、入度、出度4）路径、路径长度、简单路径、简单回路5）连通图、强连通图、弱连通图磨巫图氦弥目冶芬夸哼氯壹缀够授宰脸兄燕煽辐钩扮翘府悯反仟吠翘猖框图的基本概念和存储结构图的基本概念和存储结构1）子图、网设图G=(V,{E})和图G=(V,E),且VV,EE,则称G为G的子图。EACBDEACBDB名词和术语声余聚虽躇乱愤环岁惭矗赖蠕磕潮捍怕脓吟簇妈卸庭匝妨位则哇胚曹咕甚图的基本概念和存储

7、结构图的基本概念和存储结构弧或边带权的图分别称作有向网或无向网。ABECD1597211132名词和术语1）子图、网斯纂创筷饰猜副弥序峰傈会萨挪彝警傣磐钵傈贮壬信缆废崖钓勉谆共食粘图的基本概念和存储结构图的基本概念和存储结构2）完全图、稀疏图、稠密图假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图;含有e=n(n-1)条弧的有向图称作有向完全图;若边或弧的个数e

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

9、存储结构图的基本概念和存储结构3）邻接点、度、入度、出度顶点的入度:以顶点v为弧头的弧的数目，记为ID（v）顶点的度(TD)=出度(OD)+入度(ID)ID(B)=2OD(B)=1TD(B)=3名词和术语ABECDID(A)=1OD(A)=2TD(A)=3亏鼓赢吩乾桌煌跋耸但茵焚描巴靶需蜜扯敷客版侧秘罐乏玛逸幸蛙耀典弄图的基本概念和存储结构图的基本概念和存储结构3）邻接点、度、入度、出度名词和术语ABECD在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.4ACDFEB思考签英脊谭篡发湘赦缸纹郎谬焚桥稚汁见蠕达缚院真署茹九哎推

10、瓢酋雁士横图的基本概念和存储结构图的基本概念和存储结构ABECD4）路径、路径长