图的定义与存储结构精品文稿.ppt

《图的定义与存储结构精品文稿.ppt》由会员分享，可在线阅读，更多相关《图的定义与存储结构精品文稿.ppt（25页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、图的定义与存储结构第1页，本讲稿共25页基本概念lG=(V,E)V是顶点集，E是顶点间二元关系的集合。l与树的区别：树有特殊的根结点；树的结点和关系能分成互不相交的若干子集第2页，本讲稿共25页无向图无向图 有向图有向图 边边：二元关系是无序的。弧弧：二元关系是有序的。(vi,vj)：vi,vj互为邻接点邻接点：弧头弧头vj、弧尾、弧尾vi G1=(V1,E1)V1=v1,v2,v3,v4E1=(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)G2=(V2,E2)V2=v1,v2,v3,v4E2=,第3页，本讲稿共25页l不予讨论的图:(总能转换为简

2、单图)基本操作基本操作对整体的操作对整体的操作(遍历遍历)深度遍历DFSTraverse、广度遍历BFSTraverse对顶点的操作对顶点的操作InsertVex、DeleteVex、GetVex、SetVex对弧对弧/边的操作边的操作InsertArc、DeleteArc、GetArc、SetArc第4页，本讲稿共25页l常见应用常见应用信息的组织：家庭照片管理运输问题：最短路径问题、最优乘车路线问题网络规划：小区设店问题、区域连通的规划问题进度组织：工程进度管理第5页，本讲稿共25页图的分类图的分类l存储结构的选择l图的分解无向完全图无向完全图边数：n*(n-1)/2有向完全图有向完全图弧

3、数：n*(n-1)稀疏图稀疏图边数顶点数稠密图稠密图边数顶点数2带权图带权图边或顶点带权值子图子图V(B)V(A)，E(B)E(A)，称图B是图A的子图54613241510215203041010第6页，本讲稿共25页l顶点的参数 度度无向图中，依附于某顶点的边数出度出度有向图中，以某顶点为弧尾的弧数入度入度有向图中，以某顶点为弧头的弧数度的应用：以下哪个图能够一笔画完成？为什么？一笔画问题的本质：图结构中的边遍历问题。应用领域：车间/厂房布置、行走路线的安排、交通设计 第7页，本讲稿共25页有关路径有关路径l着眼点：顶点间的联系 顶点间路径路径Vi,Vj顶点间连通连通若从Vi到Vj有路径，

4、称Vi到Vj是连通的路径长度路径长度路径上边/弧的数目。简单路径简单路径路径中所有顶点各不相同。回路回路路径中，起点和终点是同一顶点。简单回路简单回路除起点和终点外，其余顶点各不相同第8页，本讲稿共25页有关连通有关连通l着眼点：将不连通图简化为连通图 连通图连通图无向图中,任意二个顶点之间是连通的无向图的无向图的连通分量连通分量无向图的极大连通子图。强连通图强连通图有向图中,任意二个顶点之间存在来往路径。有向图的有向图的强连通分量强连通分量有向图的极大强连通子图。V0V0 V1V1 V2V2 V3V3非强连通图非强连通图 V0V0 V1V1 V2V2 V3V3有两个强连通分量有两个强连通分量

5、第9页，本讲稿共25页生成树生成树l着眼点：将图简化为树 无向图生成树生成树连通无向图中，n个顶点和n-1条边，构成的连通子图。（原连通图的极小连通子图）生成森林生成森林不连通的无向图中，各连通分量的生成树的集合。有向图生成树生成树强连通有向图中，n个顶点和n-1条弧，构成的单向连通子图(vi、vj间存在一条路径)一个顶点入度为，其余顶点入度为。生成森林生成森林非强连通的有向图中，各强连通分量的生成树的集合。第10页，本讲稿共25页图的存储结构图的存储结构图的存储结构图的存储结构至少要保存两类信息：至少要保存两类信息：1)1)顶点的数据顶点的数据 2)2)顶点间的关系（边或弧）顶点间的关系（边

6、或弧）3)3)权的信息（可以没有）权的信息（可以没有）如何表示顶点间的关系？如何表示顶点间的关系？V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3图的抽象数据类型的定义（自学）图的抽象数据类型的定义（自学）第11页，本讲稿共25页图的数组表示法在数组表示法中，在数组表示法中，顶点存储在连续的存储空间（数组）中顶点存储在连续的存储空间（数组）中，用用邻接矩阵表示顶点间的关系邻接矩阵表示顶点间的关系。#define MaxVnum 50typedef VertexType VexsMaxVnum;typedef double AdjMatrixMaxVnum

7、MaxVnum;typedef struct int vexnum,arcnum;/图的当前顶点数和边数图的当前顶点数和边数 Vexs vexs;/顶点数组顶点数组 AdjMatrix arcs;/邻接矩阵邻接矩阵Graph;arcsij=arcsij=1 1 顶点顶点v vi i与与v vj j间有边间有边(弧弧)0 0 顶点顶点v vi i与与v vj j间无边间无边(弧弧)第12页，本讲稿共25页图的数组表示法0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 12 20 1 0 1 0 1 0 1 1 13 30 1 0 00 1 0 04 40 1 1 0 0 1 1

8、 0 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3Graph G1;G1.arcs=G1.vexnum=5；G1.arcnum=6;G1.vexs=V0,V1,V2,V3,V4;Graph G2;G2.arcs=G2.vexnum=4；G2.arcnum=4;G2.vexs=V0,V1,V2,V3;第13页，本讲稿共25页1 1）无向图的邻接矩阵是）无向图的邻接矩阵是对称矩阵，对称矩阵，有向图的邻接矩阵不一定有向图的邻接矩阵不一定是对

9、称的是对称的；2）顶点）顶点v的度：等于二维数组对应行（或列）中值为的度：等于二维数组对应行（或列）中值为1的元素的元素个数；个数；顶点顶点v的出度：等于二维数组对应行中值为的出度：等于二维数组对应行中值为1的元素个数；的元素个数；顶点顶点v的入度：等于二维数组对应列中值为的入度：等于二维数组对应列中值为1的元素个数；的元素个数；3 3）判断两顶点）判断两顶点v v、u u是否为邻接点：只需判二维数组对应分量是否为邻接点：只需判二维数组对应分量是否为是否为1 14 4）顶点不变，在图中增加、删除边：只需对二维数组对应分）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值量赋值1 1或清或

10、清0 0；5 5）设图）设图G G的顶点数为的顶点数为 n,n,则则G G占用的存储空间为：占用的存储空间为：n+nn+n2 2；图的图的存储空间占用量只与它的顶点数有关存储空间占用量只与它的顶点数有关，与边数无关，与边数无关，适用于边适用于边稠密的图。稠密的图。数组表示法的特点第14页，本讲稿共25页网的数组表示法8273496221V32V2V4V1V6V5 8 7 4 9 8 2 1 2 3 2 7 1 3 2 4 2 6 9 2 2 6 1234561 2 3 4 5 6arcsij=arcsij=权值权值 顶点顶点v vi i与与v vj j间有边间有边(弧弧)顶点顶点v vi i与

11、与v vj j间无边间无边(弧弧)第15页，本讲稿共25页图的邻接表存储结构例例 V0V0 V4V4 V3V3 V1V1 V2V2下标下标v01v1v2v3v43 024 134 02 12 01234无向图的邻接表无向图的邻接表顶点：顺序结构顶点：顺序结构关联同一顶点的关联同一顶点的边：用线性链表存储边：用线性链表存储该结点表示边（该结点表示边（V0,V1V0,V1）,其中其中1 1是是V1V1在一维数组中的下标在一维数组中的下标顶点数据顶点数据指向第一个指向第一个邻接顶点的指针邻接顶点的指针数组元素结构数组元素结构无向图的邻接表无向图的邻接表第16页，本讲稿共25页下标下标v01v1v2v

12、32 3 0 0123例例 V0V0 V1V1 V2V2 V3V3例例 V0V0 V1V1 V2V2 V3V3下标下标v0v1v2v33 0 2 01230 有向图的邻接表有向图的邻接表顶点：顺序结构顶点：顺序结构以同一顶点为以同一顶点为起点起点的的弧：用线性链表存储弧：用线性链表存储（出边表出边表）有向图的逆邻接表有向图的逆邻接表以同一顶点为以同一顶点为终点终点的弧：用线性链表存储（的弧：用线性链表存储（入边表入边表）第17页，本讲稿共25页网的邻接表表示8273496221V32V2V4V1V6V5(c)邻接链表邻接链表12345628546947183241225262431721336

13、214663219425632V1V2V3V4V5V6顶点：顺序结构顶点：顺序结构关联同一顶点的关联同一顶点的边：用线性链表存储边：用线性链表存储表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶点的指针(a)表结点结构表结点结构第18页，本讲稿共25页图的邻接表表示typedef struct VertexType data;ArcNode *firstarc;AVexNode;typedef AVexNode AdjListMaxVnum;typedef struct ArcNode int adjvex;double weig

14、ht;struct ArcNode*nextarc;ArcNode;表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶点的指针(a)表结点结构表结点结构顶点数据顶点数据指向第一个指向第一个邻接顶点的指针邻接顶点的指针(b)头结点结构头结点结构typedef struct int vexnum,arcnum;AdjList vertices;AGraph;第19页，本讲稿共25页有向图的十字链表表示v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结

15、点存储数据元素，存储数据元素，弧结点弧结点存储弧及其上的信息。存储弧及其上的信息。V0V0 V1V1 V2V2 V3V3v0v1v2v30012310 22 030313223邻接链表邻接链表tailvex headvexhlinktlinkinfo弧结点弧结点datafirstinfirstout顶点结点顶点结点第20页，本讲稿共25页有向图的十字链表表示v0v1v2v30012310 22 030313223逆邻接链表逆邻接链表 V0V0 V1V1 V2V2 V3V3v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，

16、顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧及其存储弧及其上的信息。上的信息。第21页，本讲稿共25页有向图的十字链表表示v0v1v2v30012310 22 030313223十字链表十字链表 V0V0 V1V1 V2V2 V3V3v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧存储弧及其上的信息。及其上的信息。第22页，本讲稿共25页无向图的邻接多重表表示v无向图的邻接多重表表示中，无向图的邻接多重表表示中，每条边只表示一次每条边只表示

17、一次。v0v1v2v30123010 3（v0,v1）（v0,v3）V0V0 V4V4 V3V3 V1V1 V2V221v342341 42 markivexilinkjvexjlink(vi,vj)第23页，本讲稿共25页无向图的邻接多重表表示v无向图的邻接多重表表示中，每条边只表示一次。无向图的邻接多重表表示中，每条边只表示一次。v0v1v2v30123010 3（v0,v1）（v0,v3）V0V0 V4V4 V3V3 V1V1 V2V221v442341 42 markivexilinkjvexjlink(vi,vj)第24页，本讲稿共25页根据邻接表绘制逆邻接表l已知某图的出边表如下所示，请写出该图的入边表。第25页，本讲稿共25页