《数据结构》教案第六章 图.docx
《《数据结构》教案第六章 图.docx》由会员分享,可在线阅读,更多相关《《数据结构》教案第六章 图.docx(28页珍藏版)》请在三一办公上搜索。
1、数据结构教案第六章 图 程序设计算法篇 图 图的遍历算法及其应用 目 录 第6章 图.2 6.1 图的定义和基本术语.2 6.2 图的存储和创建.3 6.2.1 图的存储表示.3 6.2.2 图的创建.6 6.3 图的遍历 .6 6.3.1 深度优先搜索.6 6.3.2 广度优先搜索.7 6.4 遍历算法的应用.8 6.4.1 应用问题概述.8 6.4.2 求一条包含图中所有顶点的简单路径.9 6.4.3 求距v0最短路径长度最长的一个顶点 . 10 6.5 图的连通性问题. 11 6.5.1 无向图的连通分量和生成树. 11 6.5.2 最小生成树 . 13 6.6 有向无环图及其应用. 1
2、3 文档编号 完成时间 修改时间 成 人 张 昱 完第 1 页 程序设计算法篇 图 图的遍历算法及其应用 第6章 图 6.1 图的定义和基本术语 1、图的特征 任意两个数据元素之间都可能相关。结点之间的关系是多对多的。 G = (V,E) 2、基本术语 结点: 顶点 结点间的关系:无向图:边(v,w),v与w互为邻接点,边(v,w)依附于顶点v,w,边(v,w)和顶点v,w相关联 v的度:和v相关联的边的数目。 有向图:弧,v弧尾,w弧头,顶点v邻接到顶点w,顶点w邻接自顶点v,弧和顶点v,w相关联。 v的入度:以v为头的弧的数目;v的出度:以v为尾的弧的数目; v的度:v的入度与出度之和。
3、路径、回路(环)、简单路径、简单回路(简单环) 连通性:若从顶点v到顶点v有路径,则称v和v是连通的 图的规模:顶点数n、边(弧)数e、顶点的度(有向图:入度/出度) 子图:G= (V,E), G = (V,E),若VV且E E,则称G是G的子图。 图的分类: 1)关系的方向性、关系上是否有附加的数权(图/网) 有向图、无向图、有向网、无向网 2)边(弧)数:完全图(边数=n(n-1)/2的无向图)、有向完全图(弧数=n(n-1)的有向图) 稀疏图(enlogn) 3)连通性:无向图:连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林 有向图:强/弱连通
4、图、强连通分量、生成树(极小连通子图)、生成森林 3、抽象数据类型定义 ADT Graph 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R: R = VR VR = |v,wV且P(v,w),表示从v到w的弧,谓词P(v,w) 定义了弧的意义或信息 基本操作: CreateGraph(&G, V, VR) 初始条件:V是图的顶点集,VR是图中弧的集合 操作结果:按V和VR的定义构造图G DestroyGraph(&G) 初始条件:图G存在 操作结果:销毁图G LocateVex(G,u) 初始条件:图G已存在,u和G中顶点有相同特征 文档编号 完成时间 修改时间 成 人
5、 张 昱 完第 2 页 程序设计算法篇 图 图的遍历算法及其应用 操作结果:若G中存在顶点u,则返回该顶点在图中位置,否则返回其它信息 GetVex(G, v) 初始条件:图G存在,v是G中某个顶点 操作结果:返回v的值 PutVex(&G, v, value) 初始条件:图G存在,v是G中某个顶点 操作结果:对v赋值value FirstAdjVex(G, v) 初始条件:图G存在,v是G中某个顶点 操作结果:返回v的第一个邻接顶点。若顶点在G中没有邻接顶点,则返回“空” NextAdjVex(G, v, w) 初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点 操作结果:返回v的(相对
6、于w的)下一个邻接顶点。若w是v的最后一个邻接点,则返回“空” InsertVex(&G, v) 初始条件:图G存在,v和G中顶点有相同特征 操作结果:在图中增添新顶点v DeleteVex(&G, v) 初始条件:图G存在,v是G中某个顶点 操作结果:删除G中顶点v及其相关的弧 InsertArc(&G, v, w) 初始条件:图G存在,v和w是G中两个顶点 操作结果:在图G中增添弧,若G是无向的,则还应增添对称弧 DeleteArc(&G, v, w) 初始条件:图G存在,v和w是G中两个顶点 操作结果:删除G中的弧,若G是无向的,则还应删除对称弧 DFSTraverse(G, v, vi
7、sit) 初始条件:图G存在,v是G中某个顶点,visit是对顶点的应用函数 操作结果:从顶点v起深度优先遍历图G,并对每个顶点调用函数visit一次且至多一次。一旦visit失败,则操作失败 BFSTraverse(G, v, visit) 初始条件:图G存在,v是G中某个顶点,visit是对顶点的应用函数 操作结果:从顶点v起广度优先遍历图G,并对每个顶点调用函数visit一次且至多一次。一旦visit失败,则操作失败 ADT Graph 6.2 图的存储和创建 6.2.1 图的存储表示 1、图的存储表示分析 顶点之间的关系是多对多的(m:n),由于m和n都是不定的,无法给出一个这种多对多
8、的关系向线性关系的映射公式 图中的关系不能通过顺序映像(即通过顶点之间的存储位置反映顶点之间的逻辑关系)反映;必须另外引入存储空间反映顶点之间的邻接关系。 文档编号 完成时间 修改时间 成 人 张 昱 完第 3 页 程序设计算法篇 图 图的遍历算法及其应用 图的存储结构:1)顶点信息;2)边(弧)信息;3)整体信息:顶点数、边(弧)数、图的种类(有向图、无向图、有向网、无向网) 顶点集的存储:图的应用中,顶点集动态变化的几率十分小 顶点集可以采用顺序表存储,按预先估计的最大顶点数分配空间 #define MAX_VERTEX_NUM 20 /* 最大顶点数 */ 注意:顺序表与顺序映像之间的区
9、别 关系集的存储:在顶点确定的情况下,边或弧的数目也是不定的,且在实际应用中,可能会改变图中的顶点之间的关系。 邻接矩阵表示法:矩阵中的第i行第j列的元素反映图中第i个顶点到第j个顶点是否存在弧,若存在其附加的信息是什么。 邻接表表示法:将每一顶点的邻接点位置串成一个链,称为邻接表。对于有向图/网来说,该邻接表反映的是顶点的出边表。 typedef enumDG, DN, AG, AN GraphKind; /*有向图,有向网,无向图,无向网*/ 2、邻接矩阵表示法 无向图/网:对称矩阵 有向图/网:非对称矩阵 图:邻接关系用1/0表示 网:邻接关系需要进一步反映权值,用INFINITY表示无
10、穷大,反映顶点之间无邻接关系 #define INT_MAX 32767 /* 最大整数 */ #define INFINITY INT_MAX 1) 邻接矩阵 typedef struct ArcCell int adj; /* 顶点间关系,无权图:0-不相邻,1-相邻 有权图,权值,INFINITY-不相邻 */ InfoType *info; /* 该弧相关信息的指针 */ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; 2) 图的整体结构 typedef struct char AdjMatrix int GraphKind MGraph
11、; 3、邻接表表示法 vexsMAX_VERTEX_NUM; /* 有效的顶点下标从0开始 */ arcs; /* 关系集 */ vexnum, arcnum; /* 顶点数、边/弧数 */ kind; /* 图的种类 */ 无向图/网:边表,表结点的个数为边数的两倍 有向图/网:出边表,表结点的个数为弧数 1) 邻接表的表结点 typedef struct ArcNode int adjvex; /* 弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; ArcNode; 文档编号 完成时间 修改时间 成
12、 人 张 昱 完第 4 页 程序设计算法篇 图 图的遍历算法及其应用 2) 邻接表的头结点 typedef struct VNode char data; /* 顶点信息 */ ArcNode *firstarc; /* 邻接表指针 */ VNode, AdjListMAX_VERTEX_NUM; 3) 图的整体结构 typedef struct AdjList vertices; int vexnum, arcnum; GraphKind kind; ALGraph; 4、邻接矩阵与邻接表的对比 假设图为G,顶点数为n,边/弧数为e。 A邻接矩阵 2O(n+n) 存储空间 图的创建算法 B邻
13、接表 O(n+e) T1(n)=O(e+n2)或T2(n)=O(e*n+n2) T1(n)=O(n+e)或T2(n)=O(e*n) T1(n)是指在输入边/弧时,输入的顶点信息为顶点的编号;而T2(n)则指在输入边/弧时,输入的为顶点本身的信息,此时需要查找顶点在图中的位置 n-1无向图中求第i顶点的度 G.arcsij.adjj=0n-1(第i行之和)或 G.verticesi.firstarc所指向的邻接表包含的结点个数 j=0G.arcsji.adj(第i列之和) 无向网中求第i行/列中adj值不为INFINITY的第i顶点的度 元素个数 n-1有向图中求第i顶点的入/出度 入度:G.a
14、rcsji.adj(第i列) j=0n-1有向网中求第i顶点的入/出度 入度:扫描各顶点的邻接表,统计表结点的adjvex为i的表结点个数出度:G.arcsij.adj(第i行) T(n)=O(n+e) j=0入度:第i列中adj值不为INFINITY出度:G.verticesi.firstarc所指向的元素个数 的邻接表包含的结点个数 出度:第i行中adj值不为INFINITY的元素个数 无向图:1n-1n-1G.arcsij.adj2i=0j=0) 无向图/网:图中表结点数目的一半 有向图/网:图中表结点的数目 统计边/弧数 无向网:G.arcs中adj值不为INFINITY的元素个数的一
15、半 n-1n-1有向图:G.arcsij.adji=0j=0有向网:G.arcs中adj值不为INFINITY的元素个数 结论:邻接矩阵适于稠密图,邻接表适于稀疏图;邻接表求有向图的顶点的入度不方便,文档编号 完成时间 修改时间 成 人 张 昱 完第 5 页 程序设计算法篇 图 图的遍历算法及其应用 要遍历全部的邻接表。 6.2.2 图的创建 基本过程: 1) 输入图的类型,根据类型选择相应的创建算法 2) 输入图的顶点数,边/弧数 3) 输入并存储顶点信息 4) 输入边/弧所关联的顶点对,将边或弧的信息存储到邻接矩阵/邻接表中 图的存储结构不同、图的类型不同,都会影响创建算法的实现细节;但是
16、,图的总体创建流程是一致的。 示例:用邻接矩阵表示法构造有向网G Status CreateMDG(MGraph &G) /* 步骤2:输入图的顶点数、边/弧数 */ scanf(&G.vexnum, &G.arcnum, &IncInfo); /* IncInfo为0则各弧不含其它信息 */ /* 步骤3:输入并存储顶点信息 */ for ( i = 0; i G.vexnum ; i+) scanf ( &G.vexsi ); /* 步骤4:输入并存储边/弧信息 */ for ( i = 0; i G.vexnum ; i+) /* 邻接矩阵初始化 */ for ( j = 0; j G.
17、vexnum ; j+) G.arcsij = INFINITY, NULL; for ( k = 0; k G.arcnum ; k+) scanf(&v1, &v2, &w); i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcsij.adj = w; if ( IncInfo) Input( *G.arcsij.info); /* *G.arcsij.info要求G.arcsij.info指向的空间在调用Input前分配 */ 6.3 图的遍历 6.3.1 深度优先搜索 1、分析 类似于树的先序遍历 引入访问标志数组visit0:n-1,区
18、分顶点是否已被访问 非连通图,需引入多个深度优先搜索的起始顶点 递归算法或基于栈的非递归算法 2、基于逻辑结构的算法 Boolean visitedMAX_VERTEX_NUM; void DFSTraverse(Graph G) for ( v = 0; v G.vexnum; + v) visitedv = FALSE; for ( v = 0; v G.vexnum; + v) if ( !visitedv ) DFS(G, v); void DFS(Graph G, int v) 文档编号 完成时间 修改时间 成 人 张 昱 完第 6 页 程序设计算法篇 图 图的遍历算法及其应用 vi
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数据结构教案第六章 教案 第六
链接地址:https://www.31ppt.com/p-3180648.html