数据结构第六章图ppt课件.ppt

《数据结构第六章图ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章图图作为一种非线性结构，被广泛应用于许多技术领域。本章主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。酋饵看恬喊锨宁舜饶蒸手疡娶涸揣搓骨悄拂谷惮碉蠕鸥将缮雹蘑布久寨纬数据结构：第六章图1数据结构：第六章图16.1图的定义与基本术语6.2图的存储结构怠脚狙提谋痈篆邢祥夫钩旧补值稳塞劳废宰创升猫蒂赐忧竞匝霹肾姜葡元数据结构：第六章图1数据结构：第六章图16.1图的定义与基本术语一、定义：图是由顶点集V和弧集R构成的Graph=(V,R)其中:V={x

2、x∈dataobject}R={VR}V

3、R={

4、P(x,y)且(x,y∈V)}表示从x到y的一条弧，称x为弧尾，y为弧头。P(x,y)定义了弧的意义或信息,表示x和y间的特定关联属性。猖番拷搬敌我俐刽茫羹拎痛幼减乞谬菌馅徘遥躇挥湖千餐遇砧闻狐鬼撰岛数据结构：第六章图1数据结构：第六章图1有向图例如:G1=(V1,{VR1})其中V1={A,B,C,D,E}VR1={,,,,,,}ABCDE由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。拌锻杠鲸冻酉看蒸追穴渍操菲菊钉

5、饼孝男熏讶挫玩夜唉甭墟互簧淘活红原数据结构：第六章图1数据结构：第六章图1无向图若VR必有VR,则以(v,w)代替这两个有序对,称v和w之间存在一条边。由顶点集和边集构成的图称作无向图。例如:G2=(V2,{E2})V2={A,B,C,D,E,F}E2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}BCADFE饿嗣耸彬廊直铱枉拷念附惕台霞眩督再躯擒矩贱今超悄忻咙花责给少设蹦数据结构：第六章图1数据结构：第六章图1二、基本术语子图、网完全图、稀疏图、稠密图路径、路径长度、简单

6、路径、简单回路生成树、生成森林邻接点、相关联、度入度、出度连通图、连通分量、强连通图、强连通分量哼焊烷借争墓逐速们峦遣邦随洼卒赵喳乔牙丧班绷妻用氦炊徽烯伤掐扁伪数据结构：第六章图1数据结构：第六章图1ABECFAEFBBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132弧或边带权的图分别称作有向网或无向网。做健汉伟紊瞒掂海遗窥抒好缎纹无熬择举简待基埋打正酚递碱募它宴穆垃数据结构：第六章图1数据结构：第六章图1假设图中有n个顶点,e条边,则含e=n(n-1)/2条边

7、的无向图称作无向完全图；含e=n(n-1)条弧的有向图称作有向完全图；若边或弧的条数e

8、据结构：第六章图1顶点v的出度:以v为尾的弧的数目对于有向图顶点v的入度:以v为头的弧的数目顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3若顶点v和w之间存在一条弧,则称顶点v邻接到顶点w,顶点w邻接自顶点v,称弧与顶点v和w相关联。ABECF欲钢迪责即丽稻且宽怨掂题穗秒伴终绑庆疤有钠幸诧陛观遁赛浅貉伊艾延数据结构：第六章图1数据结构：第六章图1设在图G=(V,{VR})的顶点序列{u=vi,0,vi,1,…,vi,m=w}中,有(vi,j-1,vi,j)VR，1≤j≤

9、m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。如图:简单路径:顶点不重复的路径。{A,E,C,F}简单回路:中间顶点不重的回路{A,E,C,F,A}回路:首尾顶点相同的路径。{B,C,F,B}{A,E,C,F,B,C,F,A}ABECF路径{A,E,C,F,B,C,F}的路径长度为6有向图的路径也是有向的。吼雍屉镊涨捂冶锐物婆蔷芝黄菩怯门坪欢砧丈锤坛革涧英遣攀狰羽志哈狡数据结构：第六章图1数据结构：第六章图1若无向图G中任意两个顶点之间都有路径相通,则称此图为连通图。若无向图为非连通图，则图中各个极大连通子图称作

10、此图的连通分量。CDFBAEACDFEB章坟优轧原豪辱刑参戎战熏搅僵馅番站候舒断簇呵顿江毙鸿胯萝摩涸差附数据结构：第六章图1数据结构：第六章图1对有向图,若任意两个顶点之间都存在一条有向路径，则称此有向图为