非线性数据结构--图.ppt

非线性数据结构--图.ppt

ID:52404094

大小:197.00 KB

页数:32页

时间:2020-04-05

非线性数据结构--图.ppt_第1页
非线性数据结构--图.ppt_第2页
非线性数据结构--图.ppt_第3页
非线性数据结构--图.ppt_第4页
非线性数据结构--图.ppt_第5页
资源描述:

《非线性数据结构--图.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库

1、非线性数据结构--图概念有向图、无向图、网存储邻接矩阵、邻接表遍历深度优先、广度优先12.5图的逻辑结构图是对结点的前趋和后继个数不加限制的数据结构,用来描述元素之间“多对多”的关系。2一.图的定义1.定义:图G=(V,E)其中:V:顶点的非空集合E:顶点的偶对---边的集合例V={v1,v2,v3,v4}E={(v1,v2),(v1,v3),(v2,v1),(v2,v3),(v2,v4),(v3,v1),(v3,v2),(v4,v2)}oooov1v2v3v4G132.有向图、无向图无向图:图中顶点的偶对是无序的,称此图为无向图,其偶对用(vx,vy)表示

2、。有向图:图中顶点的偶对是有序的,称此图为有向图,偶对用表示。G2=(V,E)V={1,2,3,4}E={〈1,2>,<1,3>,<3,4>,<4,1>}1324G243.边和弧边:无向图中顶点的偶对,写成(Vx,Vy)或(Vy,Vx)。弧:有向图中顶点的偶对,〈Vx,Vy〉表示从Vx到Vy。弧头:弧的终点弧尾:弧的起点弧〈Vx,Vy〉弧尾Vx弧头Vy54.邻接点顶点:图中的结点邻接点:无向图中,若边(Vx,Vy)E,则Vx、Vy互为邻接点。有向图中,若弧(Vx,Vy)E,则Vy是Vx的邻接点。VxVyVx、Vy互为邻接点VxVyVy是Vx

3、的邻接点65.顶点的度无向图:顶点的度是连接该顶点的边的条数。例如,G1中V2的度为3,V4的度为1。有向图1)入度:以某顶点为弧头的弧的数目。G2中顶点1的入度为1。2)出度:以某顶点为弧尾的弧的数目。顶点1的出度为2。3)顶点的度=入度+出度。顶点1的度=2+1=3。oooov1v2v3v4G11342G276.路径、长度路径图中从顶点Vx到顶点Vy的顶点序列称为从Vx到Vy的路径,路径可能是不唯一的。例如:G1中V1到V3的路径为:(V1V2V3)或(V1V3)G2中,1到4的路径为<134>。长度路径上边或弧的数目。例如,G1中V1到V3的长度为1或

4、2;G2中1到4的长度为2。1324G2oooov1v2v3v4G187.网、权权若图的边或弧带有与之相关的数,称此数为该边或弧的权。权通常用来表示从一个顶点到另一个顶点的距离或费用。网带权的图称为网。V1V2V3V4G5235792.6图类的存储结构常用的存储结构:邻接矩阵表示法邻接表表示法10一.邻接矩阵图为V和E的集合,因此:用一个一维数组存放所有顶点;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。111.无向图邻接矩阵定义设图G=(V,E)是有n(n1)个顶点的图,则G的邻接矩

5、阵是具有下述性质的对称阵:1(Vi,Vj)EA[i][j]=A[j][i]=0(Vi,Vj)EG1的邻接矩阵为:G.nodes=1234A=G.edge=01101011110001004x4oooov1v2v3v4G1122.有向图邻接矩阵定义设图G=(V,E)是有n(n1)个顶点的图,则G的邻接矩阵是具有下述性质的nxn的方阵:1〈Vi,Vj>EA[i][j]=0〈Vi,Vj>E例如,G2的邻接矩阵为:G.nodes=1234A=G.Arc=01100000000110004x41324G2133.借助邻接矩阵求顶点的度无向图第i行(或第i列)

6、的元素之和是顶点Vi的度。例,G1中V2的度是3。有向图第i行的元素之和为顶点Vi的出度;第j列的元素之和为顶点Vj的入度。例,G2中,V2的出度为0,V1的入度为1。G1A=G.Arc=01100000000110001324G2144.网的邻接矩阵定义:Wij(Vi,Vj)或〈Vi,Vj〉EA[i][j]=(Vi,Vj)或〈Vi,Vj〉EG.nodes=V1V2V3V4A=G.Arc=53274x4G5的邻接矩阵。V1V2V3V4G5235715二.邻接表图的链式存储结构1)为每个顶点建立一个单链表,2)第i个单链表中包含顶

7、点Vi的所有邻接顶点。16二.邻接表结点组成:每个链表附设一个头结点,结构为:adjvexdatanextarc顶点Vi的邻接点与边或弧有关的权值指向Vi的下一个邻接点的指针Vexdatafirstarc指向Vi单链表的第一个结点存放Vi信息171.无向图的邻接表V1V2V3V4V2顶点Vi的度恰好就是第i个单链表中的结点数。oooov1v2v3v4G1NULLV3V2NULLV2NULLV2V1V1V4NULLV3182.有向图G2的邻接表1234NULL231NULL1324G2NULL4NULL192.7图的遍历图的遍历从指定顶点出发访问图中每一个顶点

8、,使每个顶点都被访问且只被访问一次常用的遍历方法:深

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。