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

《非线性数据结构--图.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.邻接点顶点:图中的结点邻接点:无向图中，若边(Ｖx,Ｖy)E，则Ｖx、Ｖy互为邻接点。有向图中，若弧(Ｖx,Ｖy)E，则Ｖy是Ｖx的邻接点。VxVyＶx、Ｖy互为邻接点VxVyＶy是Ｖx

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、，使每个顶点都被访问且只被访问一次常用的遍历方法：深