《数据结构域算法设计级第章图A》由会员分享，可在线阅读，更多相关《数据结构域算法设计级第章图A（32页珍藏版）》请在金锄头文库上搜索。
1、下周三交作业：下周三交作业：6.29 6.42 6.43 6.47 6.49 6.65 6.29 6.42 6.43 6.47 6.49 6.65 （算法设计题一定要写出思路）方案一：二叉树的建立和遍历方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉排序树，再用中序遍历方式打印每个结 点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫曼编码 。方案三：哈夫曼编方案三：哈夫曼编/ /译码器的设计与实现译码器的设计与实现 具体内容：参见严题集P149 实习5.2要求，或参见自测卷实实 验
2、验 二二上机地点：南一楼204、208，中202 今晚 18:3021:301Status InOrderTrav( BiTree T, Status(*Visit)(TElemType e) ) /此处Visit意思是对元素e的一种操作InitStack（S）；p=T; /初始化栈while( p | !StackEmpty(S) ) /树不空或栈不空则开始遍历 if( p )Push(S,p);p=p-lchild;/根指针进栈，遍历左子树else Pop(S,p)； /根指针退栈if(! Visit(p-data)return ERROR; /访问根结点p=p-rchild; /遍历右子
3、树 /else /whilereturn OK; /InOrderTrav附附4 4：中序遍历的非递归算法：中序遍历的非递归算法( (或称迭代算法或称迭代算法) )见教见教 材材P131P13122内 容 安 排略外部排序114数组和广义表 5略文件128树和二叉树 664略6学时 内部排序查找动态存储管理图内 容 104串494栈和队列386线性表272绪 论1章 学时 内 容 章3数据结构课程的内 容多对多 （m:n)47.17.1 基本术语基本术语7.27.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 图的应用图的应用第第7 7章
4、章 图图5图的知识学了有什么用？典型用途1：建网或交通问题。如：城市A到城市B有多条线路 ，但每条线路的交通费（或所需时间）不同，那么，如何选择 一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多 条路径中，寻找一条各边权值之和最小的路径，即最短路径。典型用途2： 在施工中，完成整个工程至少需要多少时间? 为缩短工期, 应当加快哪些活动？或者说，哪些活动是影响 工程进度的关键？ 问题抽象： 有向图的拓扑排序、求关键路径67.1 7.1 图的基本图的基本 术语术语其中：V 是G 的顶点集合，是有穷非空集；E 是G 的边集合，是有穷集。问：当E(G)为空时
5、，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。有向图 ： 无向图 ： 完全图 ：图G中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任意两个顶点都有一条边相连接；V=vertex E=edge图：记为 G( V, E )v1v2v3v5v4v4v1v2v3v47例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n n( (n n-1)/2 -1)/2 条边条边n n( (n n-1) -1) 条边条边G1的顶点集合为V(G1)=0,1,2,3 边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全图完全图v若 n 个顶点的
6、无向图有 n(n-1)/2 条边, 称为无向完全图 v若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图8证 明 ：证明：若是完全有向图，则n个顶点中 的每个顶点都有一条弧指向其它n-1个 顶点, 因此总边数=n(n-1)证明：从可以直接推论出无向完全图的 边数因为无方向，两弧合并为一边， 所以边数减半，总边数为n(n-1)/2。 完全无向图有完全无向图有n n( (n n-1)/2 -1)/2 条边条边。 完全有向图有完全有向图有n n( (n n-1)-1)条边条边。123412349稀疏图：稠密图：设有两个图 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称
7、图G 是 图G 的子图。子 图：边较少的图。通常边数远少于nlognnlogn边很多的图。无向图中，边数接近n n( (n n-1)/2-1)/2 有向图中，边数接近n n( (n n-1)-1)10带 权 图 ：即边上带权的图。其中权是指每条边 可以标上具有某种含义的数值（即与 边相关的数）。连通图 ：在无向图中, 若从顶点v1到顶点v2 有路径, 则称顶点v1与v2是连通的 。如果图中任意一对顶点都是连通 的, 则称此图是连通图。 非连通图的极大连通子图叫做连通 分量。带权图在有向图中, 若对于每一对顶点vi和 vj, 都存在一条从vi到vj和从vj到vi的路 径, 则称此图是强连通图。强
8、连通图：网 络：DEABCFJLMGHIK非强连通图的极大强连通子图叫做强连通分量。11生成树 ：是一个是一个极小连通子图极小连通子图，它含有图，它含有图 中全部中全部n n个顶点，但只有个顶点，但只有n n-1-1条边条边 。若干棵若干棵生成树的集生成树的集 合合，含全部顶点，含全部顶点， 但构成这些树的边但构成这些树的边 或或弧弧是最少的。是最少的。有两类图形不在 本章讨论之列：图的基本术语图的基本术语( (续续) )v1v2v3v4 v如果在生成树上添加1条边，必定构成一个环。 v若图中有n个顶点，却少于n-1条边，必为非连通图。生成 森林 ：12邻 接 点 ： 有向边(u, v)称为弧
9、，边的始点u 叫弧尾 ，终点v 叫弧头。顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v) 。若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。弧头和 弧尾：入度和 出度：问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1， 此时是何形状？uv度 ：顶点v 的度是与它相关联的边的条数。记作TD(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。U U 的入度的入度=?=? U U 的出度的出度=?=?答：是树！而且是一 棵有向树！13简单 路径 ：路径上各顶点 v1,v2
10、,.,vm 均不互相重复。回路 ：若路径上第一个顶点 v1 与最后一个顶点vm 重合 ，则称这样的路径为回路或环。路径：在图在图 GG( (V V, , E E) ) 中中, , 若从顶点若从顶点 v vi i 出发出发, , 沿一些边经过一些顶沿一些边经过一些顶 点点 v vp p1 1, , v vp p2 2, , , , v vpmpm，到达顶点到达顶点v vj j。则称顶点序列则称顶点序列 ( ( v vi i v vp p1 1 v vp p2 2 . . v vpmpm v vj j ) ) 为从顶点为从顶点v vi i 到顶点到顶点 v vj j 的的路径路径。它经过的。它经过
11、的边边( (v vi i, , v vp p1 1) )、( (v vp p1 1, , v vp p2 2) )、. .、( (v vpmpm, , v vj j) )应当是属于应当是属于E E的的边边。路径 长度 ：非带权图非带权图的的路径长度路径长度是指此路径上是指此路径上边的条数边的条数； 带权图带权图的的路径长度路径长度是指路径上是指路径上各边的权之和各边的权之和。图的术语（续 ）14ADT Graph 数据对象V： 数据关系 R：基本操作P：ADT Graph 图的抽象数据图的抽象数据 类型类型V是具有相同特性的数据元素的集合，称为顶点集。 R=VR；VR=|v,wV 且 P(v,
12、w), 表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息CreatGraph ( 初始条件：V是图的顶点集，VR是图中弧的集合 。操作结果：按V和VR的定义构造图G。注意：V 的大小写含 义不同！InsertVex ( 初始条件：图G存在，v 和图中顶点有相同特征。操作结果：在图G中添加新顶点。（参见教材P156-257）157.2 7.2 图的存储图的存储 结构结构图的特点 ：链式存储结构 ：顺序存储结构 ：可用链表描述1.1.邻接矩阵邻接矩阵( (数组数组) )表示法表示法2.2.邻接表邻接表( (链式链式) )表示法表示法3. 3. 十字链表十字链表表示法表示法4. 4. 邻接多重
13、表邻接多重表表示法表示法用数组描述行否？非线性结构（m : n）邻接矩阵邻接表 十字链表 邻接多重表各种表示法成立的原则 ：存入电脑后能惟一复 原多个顶点，而且无序，仅用顶点坐标无法表达相互关系16 建立一个建立一个顶点表顶点表和一个和一个邻接矩阵邻接矩阵 。1. 1. 邻接矩阵（数组）表示邻接矩阵（数组）表示 法法例例1 1 ：邻接矩阵： A.Edge =（ v1 v2 v3 v4 v5 ）v1 v2 v3 v4 v50 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的； 分析分析
14、2 2：顶点顶点i i 的的度度第第 i i 行行 ( (列列) ) 中中1 1 的个数的个数； 特别：特别：完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余全，其余全1 1。顶点表：下面无向图的邻接矩阵如何表示？ v1v2v3v5v4v4A A记录各个顶点信息表示各个顶点之间关系 设图设图 A = (A = (V V, , E E) ) 有有 n n 个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数 组组 A A.Edge.Edge n n n n ，定义为：定义为：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15、 0 0 0 00 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 017例2 ：下面有向图的邻接矩阵如何表示 ？分析分析1 1：有向图的邻接矩阵可能是不对称的。 分析分析2 2：顶点vi的出度=第i行元素之和，OD(vi )= A.Edge i j 顶点vi的入度=第i列元素之和。ID(vi )= A.Edge j i 顶点的度=第i行元素之和+第i列元素之和,即：TD( vi ) = OD( vi ) + ID( vi )v1v2v3v4A A邻接矩阵： A.Edge =( v1 v2 v3 v4 ) v1 v2 v3 v40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶
