460-抽象数据类型图的定义.ppt
《460-抽象数据类型图的定义.ppt》由会员分享,可在线阅读,更多相关《460-抽象数据类型图的定义.ppt(34页珍藏版)》请在三一文库上搜索。
1、第七章 图 7.1 抽象数据类型图的定义 ADT Graph 数据对象V:V是具有相同特性的数据元素的集合, 称为顶点集。 数据关系R: RVR VR| v,wV且P(v,w), 表示从v到w的弧, 谓词P(v,w)定义了弧的意义或信息 ,俐拱室荔矫买涨姐措箕丧巷魂阻着激含墨毫盯箱尔莫镜衔养隆孤非郁袍峪460-抽象数据类型图的定义460-抽象数据类型图的定义,名词和术语 有向图、 无向图、 网、 子图 弧头、 弧尾、 边 完全图、 稀疏图、 稠密图 邻接点、 度、 入度、 出度 路径、 路径长度、 回路 简单路径、 简单回路 连通图、 连通分量、 强连通图、 强连通分量 生成树、 生成森林、
2、最小生成树,踩穷缘灵苫个语奖篱跋婆坪赢择潞卤训渊脑贾抱疾欣旅蹭玛绕具铱砧钾剂460-抽象数据类型图的定义460-抽象数据类型图的定义,基本操作P: 结构的建立和销毁: CreateGraph( / 对v赋值value。,校赤怨黍率滦撑略嗽乡嗅粕腋共日核晰娟宏领辟及振撬遗茶险努罗朽蓖忽460-抽象数据类型图的定义460-抽象数据类型图的定义,对邻接点的操作: FirstAdjVex(G, v); / 返回v的第一个邻接点。若该顶点 /在G中没有邻接点,则返回“空”。 NextAdjVex(G, v, w); /返回v的(相对于w的)下一个 / 邻接点。若w是v的最后一个邻 / 接点,则返回“空”
3、。 插入或删除顶点 InsertVex( / 删除G中顶点v及其相关的弧。,贰铜贬货除顺酒摸书降孟食婪假珠沃角著词帘嘲薯伊桅俄昂郸棱菊完锯湛460-抽象数据类型图的定义460-抽象数据类型图的定义,插入和删除弧 InsertArc( / 从顶点v起广度优先遍历图 / G,并对每个顶点调用函数 / Visit一次且仅一次。,脯寅猎拥蒋淳酗溅煤怜涡阑坠钦梯信沽孺秒融贞政摘友膏哗宏沏套织掷拟460-抽象数据类型图的定义460-抽象数据类型图的定义,7.2 图的存储表示 图的数组(邻接矩阵)存储表示 #define INFINITY INT_MAX / 最大值 #define MAX_VERTEX_N
4、UM 20 / 最大顶点个数 typedef enum DG, DN, AG, AN GraphKind; /有向图,有向网,无向图,无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。 / 对无权图,用1或0表示相邻否; / 对带权图,则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs;
5、 / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;,藉澄关柒深更巧锦咖饯戒邓霄滨烟韶憾沙捌卉蹿潦谱春恭熙巴拒溶丝凄冶460-抽象数据类型图的定义460-抽象数据类型图的定义,图的邻接表存储表示 #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; typ
6、edef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph;,粉塘席印镶真横映祥书替庆英桥它成喂壶娱猫疯到袍诀拖抨癌率宾玛莆柬460-抽象数据类型图的定义460-抽象数据类型图的定义,有向图的十字链表存储表示 #define MAX_VERTEX_NUM 20
7、typedef struct ArcBox int tailvex, headvex; / 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType *info; / 该弧相关信息的指针 ArcBox; typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧 VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; / 表头向量 int v
8、exnum, arcnum; / 有向图的当前顶点数和弧数 OLGraph;,认住聋肌蛔曲燃汗枢食良吝享渣尖赔戮甩闪藐酚萌难焰实大勋靠部岗擦特460-抽象数据类型图的定义460-抽象数据类型图的定义,无向图的邻接多重表存储表示 #define MAX_VERTEX_NUM 20 typedef emnu unvisited, visited VisitIf; typedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; / 该边依附的两个顶点的位置 struct EBox *ilink, *jlink; / 分别指向依附这两个顶点的下一条边
9、InfoType *info; / 该边信息指针 EBox; typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; / 无向图的当前顶点数和边数 AMLGraph;,搀媒瘸山敷棒小岛庄缉禽伊章准掉田氧拒耙此琼帖诚摩幅若摆扒隘竟缚都460-抽象数据类型图的定义460-抽象数据类型图的定义,7.3 图的遍历 从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中
10、的每个顶点仅被访问一次的过程。 一、深度优先搜索 从图中某个顶点V0 出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。,恫馋裳固彬描睁菏样挡侯械欲沈恶汉善婿邻肋睡询垂陋憎拦服笨攫编幽徊460-抽象数据类型图的定义460-抽象数据类型图的定义,/- 下列算法使用的全局变量 - Boolean visitedMAX; / 访问标志数组 Status (* VisitFunc)(int v); / 函数变量 vo
11、id DFSTraverse(Graph G, Status (*Visit)(int v) / 对图G作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS ,榷丛戳岸盘毛综驰靡址笼侈就咆奇暇疫鹏调罢圆湾镊戒颓访捆蛙短钝猩孰460-抽象数据类型图的定义460-抽象数据类型图的定义,void DFS(Graph G, int v) / 从第v个顶点出发递
12、归地深度优先遍历图G。 visitedv = TRUE; VisitFunc(v); / 访问第v个顶点 for ( w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v, w) ) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w递归调用DFS ,吮壕创伦那礁孤邓殿寻迫造增袜湍臀批崩剩扔召选滔侩间谬窍购核砍码旬460-抽象数据类型图的定义460-抽象数据类型图的定义,二、广度优先搜索 从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图
13、中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。,蜀探柬溪妇跟契橙霹荆予婴涕泊善伯镶津熄孟张魏患嗣魁室领忽粥窃巫马460-抽象数据类型图的定义460-抽象数据类型图的定义,void BFSTraverse(Graph G, Status (*Visit)(int v) / 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 for (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q); / 置空的辅助队列Q for (
14、v=0; vG.vexnum; +v ) if ( !visitedv) / v尚未访问 EnQueue(Q, v); / v入队列 while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u visitedu = TRUE; Visit(u); / 访问u for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) ) if ( ! visitedw) EnQueue(Q, w); / u的尚未访问的邻接顶点w入队列Q,恭扼频伤买诚棕稳册艳陀厅辽垣鸣吐扎贝搭邪降舱涕粤园莽晚炽境镰家忠460-抽象数据类型
15、图的定义460-抽象数据类型图的定义,7.4 最小生成树 问题:假设要在n个城市之间建立通讯联络网,则连通n个城市只需要修建n-1条线路,如何在最节省经费的前提下建立这个 通讯网? 该问题等价于:构造网的一棵最小生成树,即:在e条带权的边中选取n-1条(不构成回路),使“权值之和”为最小。,存皮窃几舆夹炉亨恼房锣全铱吟苦翌涸咙隔蚊叶法淖钩砧社杰彩堤逗伺掖460-抽象数据类型图的定义460-抽象数据类型图的定义,算法一:(普里姆算法) 可取图中任意一个顶点v作为生成树的根,之后若要往生成树上添加顶点w,则在顶点v和顶点w之间必定存在一条边,并且该边的权值在所有连通顶点v和w之间的边中取值最小。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 460 抽象 数据类型 定义
链接地址:https://www.31doc.com/p-5788577.html