图的定义与存储结构幻灯片.ppt

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

1、图的定义与存储结构第1页，共25页，编辑于2022年，星期五基本概念lG=(V,E)V是顶点集，E是顶点间二元关系的集合。l与树的区别：树有特殊的根结点；树的结点和关系能分成互不相交的若干子集第2页，共25页，编辑于2022年，星期五无向图无向图 有向图有向图 边边：二元关系是无序的。弧弧：二元关系是有序的。(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页，共2

2、5页，编辑于2022年，星期五l不予讨论的图:(总能转换为简单图)基本操作基本操作对整体的操作对整体的操作(遍历遍历)深度遍历DFSTraverse、广度遍历BFSTraverse对顶点的操作对顶点的操作InsertVex、DeleteVex、GetVex、SetVex对弧对弧/边的操作边的操作InsertArc、DeleteArc、GetArc、SetArc第4页，共25页，编辑于2022年，星期五l常见应用常见应用信息的组织：家庭照片管理运输问题：最短路径问题、最优乘车路线问题网络规划：小区设店问题、区域连通的规划问题进度组织：工程进度管理第5页，共25页，编辑于2022年，星期五图的分类

3、图的分类l存储结构的选择l图的分解无向完全图无向完全图边数：n*(n-1)/2有向完全图有向完全图弧数：n*(n-1)稀疏图稀疏图边数顶点数稠密图稠密图边数顶点数2带权图带权图边或顶点带权值子图子图V(B)V(A)，E(B)E(A)，称图B是图A的子图54613241510215203041010第6页，共25页，编辑于2022年，星期五l顶点的参数 度度无向图中，依附于某顶点的边数出度出度有向图中，以某顶点为弧尾的弧数入度入度有向图中，以某顶点为弧头的弧数度的应用：以下哪个图能够一笔画完成？为什么？一笔画问题的本质：图结构中的边遍历问题。应用领域：车间/厂房布置、行走路线的安排、交通设计 第

4、7页，共25页，编辑于2022年，星期五有关路径有关路径l着眼点：顶点间的联系 顶点间路径路径Vi,Vj顶点间连通连通若从Vi到Vj有路径，称Vi到Vj是连通的路径长度路径长度路径上边/弧的数目。简单路径简单路径路径中所有顶点各不相同。回路回路路径中，起点和终点是同一顶点。简单回路简单回路除起点和终点外，其余顶点各不相同第8页，共25页，编辑于2022年，星期五有关连通有关连通l着眼点：将不连通图简化为连通图 连通图连通图无向图中,任意二个顶点之间是连通的无向图的无向图的连通分量连通分量无向图的极大连通子图。强连通图强连通图有向图中,任意二个顶点之间存在来往路径。有向图的有向图的强连通分量强连

5、通分量有向图的极大强连通子图。V0V0 V1V1 V2V2 V3V3非强连通图非强连通图 V0V0 V1V1 V2V2 V3V3有两个强连通分量有两个强连通分量第9页，共25页，编辑于2022年，星期五生成树生成树l着眼点：将图简化为树 无向图生成树生成树连通无向图中，n个顶点和n-1条边，构成的连通子图。（原连通图的极小连通子图）生成森林生成森林不连通的无向图中，各连通分量的生成树的集合。有向图生成树生成树强连通有向图中，n个顶点和n-1条弧，构成的单向连通子图(vi、vj间存在一条路径)一个顶点入度为，其余顶点入度为。生成森林生成森林非强连通的有向图中，各强连通分量的生成树的集合。第10页

6、，共25页，编辑于2022年，星期五图的存储结构图的存储结构图的存储结构图的存储结构至少要保存两类信息：至少要保存两类信息：1)1)顶点的数据顶点的数据 2)2)顶点间的关系（边或弧）顶点间的关系（边或弧）3)3)权的信息（可以没有）权的信息（可以没有）如何表示顶点间的关系？如何表示顶点间的关系？V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3图的抽象数据类型的定义（自学）图的抽象数据类型的定义（自学）第11页，共25页，编辑于2022年，星期五图的数组表示法在数组表示法中，在数组表示法中，顶点存储在连续的存储空间（数组）顶点存储在连续的存储空间（数组）

7、中中，用，用邻接矩阵表示顶点间的关系邻接矩阵表示顶点间的关系。#define MaxVnum 50typedef VertexType VexsMaxVnum;typedef double AdjMatrixMaxVnumMaxVnum;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间无边间无边(弧

8、弧)第12页，共25页，编辑于2022年，星期五图的数组表示法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 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;

9、G2.arcs=G2.vexnum=4；G2.arcnum=4;G2.vexs=V0,V1,V2,V3;第13页，共25页，编辑于2022年，星期五1 1）无向图的邻接矩阵是）无向图的邻接矩阵是对称矩阵，对称矩阵，有向图的邻接矩阵不一定是对称有向图的邻接矩阵不一定是对称的的；2）顶点）顶点v的度：等于二维数组对应行（或列）中值为的度：等于二维数组对应行（或列）中值为1的元素个数；的元素个数；顶点顶点v的出度：等于二维数组对应行中值为的出度：等于二维数组对应行中值为1的元素个数；的元素个数；顶点顶点v的入度：等于二维数组对应列中值为的入度：等于二维数组对应列中值为1的元素个数；的元素个数；3 3

10、）判断两顶点）判断两顶点v v、u u是否为邻接点：只需判二维数组对应分量是否为是否为邻接点：只需判二维数组对应分量是否为1 14 4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1 1或清或清0 0；5 5）设图）设图G G的顶点数为的顶点数为 n,n,则则G G占用的存储空间为：占用的存储空间为：n+nn+n2 2；图的存储空间占图的存储空间占用量只与它的顶点数有关用量只与它的顶点数有关，与边数无关，与边数无关，适用于边稠密的图。适用于边稠密的图。数组表示法的特点第14页，共25页，编辑于2022年，星期五网的数组表示法

11、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与与v vj j间无边间无边(弧弧)第15页，共25页，编辑于2022年，星期五图的邻接表存储结构例例 V0V0 V4V4 V3V3 V1V1 V2V2下标下标v01v1v2v3v43 024 134 02 12 01234无向图的邻接表无向图的邻接表顶点：顺序结构顶点：顺序结构关联同一顶点的关联同一顶点的边：用线性链

12、表存储边：用线性链表存储该结点表示边（该结点表示边（V0,V1V0,V1）,其中其中1 1是是V1V1在在一维数组中的下标一维数组中的下标顶点数据顶点数据指向第一个指向第一个邻接顶点的指针邻接顶点的指针数组元素结构数组元素结构无向图的邻接表无向图的邻接表第16页，共25页，编辑于2022年，星期五下标下标v01v1v2v32 3 0 0123例例 V0V0 V1V1 V2V2 V3V3例例 V0V0 V1V1 V2V2 V3V3下标下标v0v1v2v33 0 2 01230 有向图的邻接表有向图的邻接表顶点：顺序结构顶点：顺序结构以同一顶点为以同一顶点为起点起点的的弧：用线性链表存储弧：用线性

13、链表存储（出边表出边表）有向图的逆邻接表有向图的逆邻接表以同一顶点为以同一顶点为终点终点的弧：用线性链表存储（的弧：用线性链表存储（入边表入边表）第17页，共25页，编辑于2022年，星期五网的邻接表表示8273496221V32V2V4V1V6V5(c)邻接链表邻接链表12345628546947183241225262431721336214663219425632V1V2V3V4V5V6顶点：顺序结构顶点：顺序结构关联同一顶点的关联同一顶点的边：用线性链表存储边：用线性链表存储表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶

14、点的指针(a)表结点结构表结点结构第18页，共25页，编辑于2022年，星期五图的邻接表表示typedef struct VertexType data;ArcNode *firstarc;AVexNode;typedef AVexNode AdjListMaxVnum;typedef struct ArcNode int adjvex;double weight;struct ArcNode*nextarc;ArcNode;表头顶点的表头顶点的邻接顶点编号邻接顶点编号和边相关和边相关的信息的信息指向下一个指向下一个邻接顶点的指针邻接顶点的指针(a)表结点结构表结点结构顶点数据顶点数据指向第一

15、个指向第一个邻接顶点的指针邻接顶点的指针(b)头结点结构头结点结构typedef struct int vexnum,arcnum;AdjList vertices;AGraph;第19页，共25页，编辑于2022年，星期五有向图的十字链表表示v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧及其上的信息。存储弧及其上的信息。V0V0 V1V1 V2V2 V3V3v0v1v2v30012310 22 030313223邻接链表邻接链表tailvex headv

16、exhlinktlinkinfo弧结点弧结点datafirstinfirstout顶点结点顶点结点第20页，共25页，编辑于2022年，星期五有向图的十字链表表示v0v1v2v30012310 22030313223逆邻接链表逆邻接链表 V0V0 V1V1 V2V2 V3V3v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧及其上的存储弧及其上的信息。信息。第21页，共25页，编辑于2022年，星期五有向图的十字链表表示v0v1v2v30012310 2203

17、0313223十字链表十字链表 V0V0 V1V1 V2V2 V3V3v将有向图的邻接表和逆邻接表结合起来得到的链表。将有向图的邻接表和逆邻接表结合起来得到的链表。v在十字链表中，在十字链表中，顶点结点顶点结点存储数据元素，存储数据元素，弧结点弧结点存储弧及存储弧及其上的信息。其上的信息。第22页，共25页，编辑于2022年，星期五无向图的邻接多重表表示v无向图的邻接多重表表示中，无向图的邻接多重表表示中，每条边只表示一次每条边只表示一次。v0v1v2v30123010 3（v0,v1）（v0,v3）V0V0 V4V4 V3V3 V1V1 V2V221v34234142markivexilinkjvexjlink(vi,vj)第23页，共25页，编辑于2022年，星期五无向图的邻接多重表表示v无向图的邻接多重表表示中，每条边只表示一次。无向图的邻接多重表表示中，每条边只表示一次。v0v1v2v30123010 3（v0,v1）（v0,v3）V0V0 V4V4 V3V3 V1V1 V2V221v44234142 markivexilinkjvexjlink(vi,vj)第24页，共25页，编辑于2022年，星期五根据邻接表绘制逆邻接表l已知某图的出边表如下所示，请写出该图的入边表。第25页，共25页，编辑于2022年，星期五