数据结构（自考） 课件 第5、6章 树与二叉树、图结构

全国高等教育自学考试指定教材

计算机及应用专业（专科段）数据结构第五章树与二叉树学习目标理解树及二叉树的基本概念，掌握二叉树的基本性质掌握树及二叉树的存储方式能够实现树及二叉树的基本操作及遍历算法理解递归的概念，能够实现递归程序掌握树、森林与二叉树之间的相互转换掌握哈夫曼树及哈夫曼编码的概念，能够构造哈夫曼树并设计哈夫曼编码本章主要内容树的基本概念12二叉树的操作3二叉树树和森林4哈夫曼树及哈夫曼编码5第一节树的基本概念树是一种层次结构，所以是一种非线性结构日常生活中，经常会遇到具有层次关系的示例家族中部分成员的辈份关系树的定义定义5.1一棵树（tree）T是由一个或一个以上的结点组成的有限集，其中有一个特定的结点R称为树T的根结点。在集合中除根结点R外，其余的结点可划分为k(k≥0)个不相交的子集T1,T2,…,Tk，其中每个子集都是树，并且其相应的根结点R1,R2,…,Rk是R的孩子结点，R称为Ri(1≤i≤k)的双亲结点，Ri(1≤i≤k)互称为兄弟结点。子集Ti(1≤i≤k)称为根R的子树（subtree）树的结点集合至少包含一个结点只含有一个结点的树是只有根结点的树，也就是单结点树对于多结点的树，必须有一个结点是根结点之间通过边来连接，边也称为分支。含n个结点的树有且仅有n-1条边，这是树的重要特性之一根结点的各子树之间不会有重叠树是一种层次结构，也是递归形式的含有A,B,C,D,E,F,G,H,I,J共10个结点的树TA为根结点，{B,E,F}，{C,G}和{D,H,I,J}构成根结点A的三棵子树，B,C,D分别是这三棵子树的根树中每个结点拥有的子树的个数称为结点的度结点的度即为其子结点的个数树中结点的度的最大值称为树的度度为0的结点称为叶结点，或终端结点度不为0的结点称为分支结点如果树中每个结点的孩子结点之间规定了次序，则树称为有序树具有同一双亲结点的结点是兄弟结点从任一结点到根结点之间所经过的所有结点称为该结点的祖先结点以任一结点为根的子树中的所有结点称为该结点的后代将线性结构中的前驱和后继概念引申至树中，将某结点的双亲结点看作是它的前驱，它的孩子结点看作是它的后继除根结点外，每个结点均只有一个前驱结点根的前驱结点个数为0，除叶结点外，每个结点都有若干个后继结点叶结点的后继结点个数为0树中每个元素的前驱的个数不会多于1个，后继的个数可以是任意个树是一种层次结构，设根为0层，根的孩子结点为1层，依此类推一般地，若某个结点位于i（i≥0）层，则它的孩子结点位于i+1层树中结点的最大层数定义为树的深度最大层数加1为树的高度树中从某一结点出发，到达另一个结点之间所经过的边组成一条路径路径中所含的边数为路径长度虽然树的路径定义中并没有限制路径的方向，但路径通常是沿一个方向延伸的，即从某一结点向根的方向延伸，或是从某一结点向叶结点方向延伸通常，以组成路径的结点序列来表示该条路径m（m≥0）棵互不相交的树构成森林对树中每个结点来说，其子树的集合即为森林第二节二叉树定义5.2二叉树（binarytree）是结点（node）的一个有限集合，这个集合或者为空，或者是由一个根结点以及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。左子树和右子树的根分别称为此二叉树根结点的左孩子结点和右孩子结点二叉树的左子树和右子树都可以存在或者为空，不同的存在状态可以组合出5种基本形态一棵高度为k的二叉树若有2k-1个结点，则二叉树称为满二叉树从形式上来看，满二叉树中除叶结点外，每个结点都有两个孩子结点，即除最后一层外，每一层的结点都是“满”的满二叉树中的n个结点进行连续编号，从编号为0的结点开始，由连续编号的任意多个结点组成的二叉树称为完全二叉树特殊二叉树满二叉树和完全二叉树完全二叉树的特性

二叉树的性质性质1在二叉树的i层上最多有2i个结点(i≥0)证明：使用数学归纳法证明

归纳基础：

对于非空的二叉树T，根在0层，本层只有20=1个结点，结论成立

归纳假设：

设二叉树T中i-1层最多有2i-1个结点，考虑i层，由于i层的结点均为i-1层结点的孩子结点，而二叉树中每个结点最多有两个孩子结点，故i层最多有2

2i-1=2i个结点

根据归纳法原理，性质1得证

性质3对任何非空二叉树T，设n0是叶结点的个数，n2是度为2的结点的个数，则有n0=n2+1证明：设二叉树T中度为1的结点个数为n1，则T中结点总数n为 n=n0+n1+n2 n-1=2

n2+1

n1+0

n0

将上两式联立求解，得到 n0=n2+1

二叉树的存储——顺序存储结构对于完全二叉树，各层自上至下，同层间自左至右，将结点依次存入数组从前至后的各个元素中。按照前面使用过的编号方法，一般来讲，编号为i的结点存放在数组中下标为i的位置使用这样的存储规则可以很方便地找到二叉树中的相关结点，即若知道二叉树某一结点保存在数组中下标i的位置，则可以很方便地求出它的双亲结点（若存在）和左、右孩子结点（若存在）在数组中的位置对于一般的二叉树，顺序存储的思想是，针对二叉树中的每个位置，不论这个位置有没有结点，都在数组中预留保存空间。采用这种存储方式保存完全二叉树时，既不浪费空间，又便于有关操作的实现链式存储结构定义一个结点结构：它含有两个指针域，一个指针用来指向该结点左孩子所在的结点，称为左孩子指针，简称为左指针；另一个指针用来指向该结点右孩子所在的结点，称为右孩子指针，简称为右指针。此外，还定义一个用来保存结点中数据的数据域二叉链表表示二叉树结点类的定义及二叉树的定义二叉链表中结点类的定义及二叉树的定义typedefintELEMType;typedefstructBNode //二叉树结点{ ELEMTypedata; //数据域 structBNode*left,*right; //指向左孩子、右孩子的指针}BinTNode;typedefBinTNode*BTree; //二叉树二叉链表中到底有多少空指针域呢设二叉树中有n个结点，每个结点都含有两个指针域，则二叉链表中共有2

n个指针域已知含n个结点的树中仅含有n-1个分支，即只有n-1个指针域不为空，则其余的n+1个指针域均为空可以看出，二叉链表中有超过一半的指针域都是空的，这些都是结构性开销第三节二叉树的操作二叉树的生成按照二叉树的顺序存储方式，将二叉树各结点值保存在一维数组中，然后建立二叉链表如要建立如下的二叉链表输入的数组是inta[]={0,1,2,3,4,NA,5,NA,NA,NA,NA,NA,NA,6};函数CreateBinaryTree递归处理二叉链表的生成调用它的主程序中先创建一个根结点，其中保存数组首元素的值，该结点作为参数传递给函数CreateBinaryTree。这个结点的位置是下标0，将这个位置值也作为参数传给函数CreateBinaryTree主程序中BTreeroot;root=(BTree)malloc(sizeof(BinTNode));root->data=a[0];root->left=NULL;root->right=NULL;调用函数CreateBinaryTree。参数0是起始位置CreateBinaryTree(0,n,a,root);生成二叉链表如果下标i处的结点有左孩子，则其应该保存在下标2

i+1处如果有右孩子，则应该保存在下标2

i+2处故在函数内，判断数组中位置2

i+1及位置2

i+2处是否保存了元素值如果确实有值，则分配空间创建结点且保存数组中相应位置的元素值，并让下标i处结点的相应指针指向新创建的结点然后再以2

i+1或2

i+2为参数值，递归调用函数，去处理2

i+1或2

i+2位置处结点的左孩子和右孩子如果数组中数据的存储是正确的，则能正确建立二叉链表。如果位置2

i+1或位置2

i+2处没有保存元素值，则递归结束二叉树的遍历对非空的二叉树的遍历可以相应地分解为三项“子任务”访问根结点遍历左子树（即依相应的规律访问左子树中的全部结点）遍历右子树（即依相应的规律访问右子树中的全部结点）常规的3种遍历算法分别是先序遍历、中序遍历和后序遍历。这3种遍历也分别称为先根遍历、中根遍历和后根遍历先序遍历算法若二叉树为空，则返回；否则依次执行以下操作（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树中序遍历算法若二叉树为空，则返回；否则依次执行以下操作（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树后序遍历算法若二叉树为空，则返回；否则依次执行以下操作（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点先序遍历过程中序遍历过程后序遍历过程示例写出其先序、中序及后序遍历序列先序遍历序列为A,B,D,G,H,J,K,E中序遍历序列为G,D,J,H,K,B,E,A后序遍历序列为G,J,K,H,D,E,B,A先序遍历算法先序遍历算法中序遍历算法中序遍历算法后序遍历算法后序遍历算法给出二叉树的先序遍历序列和中序遍历序列，能唯一确定该二叉树给出二叉树的后序遍历序列和中序遍历序列，能唯一确定该二叉树示例设二叉树T的先序遍历序列是A,B,D,G,H,J,K,E，中序遍历序列是G,D,J,H,K,B,E,A，画出二叉树T由先序遍历序列可知，T的根是A在中序遍历序列中查找A的位置，位于A前面的是其左子树的中序遍历序列，位于A后面的是其右子树的中序遍历序列从而将原问题的求解（对整棵树的还原）分解为两个更小问题的求解（对两棵子树的还原）示例统计以二叉链表表示的二叉树T中叶结点的个数T中叶结点的个数等于根左子树中叶结点的个数加上根右子树中叶结点的个数。所以如果递归调用已经得到了两棵子树中叶结点的个数，那么将结果相加即求解示例编写程序，返回二叉树T的高度仍是使用递归的思想去编写程序。如果左子树的高度和右子树的高度都已经知道，则二叉树T的高度就可求得，树的高度是两棵子树中较高者的高度再加1层序遍历所谓按层遍历，即是从根结点开始逐层向下遍历，直到最后一层对于同一层的结点，由左到右遍历各结点同一层中的结点相继被访问，同时，它们之间的相对次序也决定着它们孩子结点的相对次序。即同一层中的结点u和结点v，若先遍历u再遍历v，则u的孩子结点的遍历也早于v的孩子结点的遍历按层进行遍历先访问最上面一层即0层中的元素，输出1然后依次访问1的子结点2和3再继续访问2的子结点和3的子结点依此类推，得到的层序遍历结果是：1,2,3,4,5,6,7层序遍历算法二叉树层序遍历的算法二叉树的应用可以使用二叉树来表示一个表达式，这样的二叉树称为表达式树2*y*(a+3*y)-b画出表达式树先根据运算符的优先级对表达式加括号去掉最外层括号。中间的运算符为根，前后两部分分别对应于左子树和右子树对左子树递归执行步骤②对右子树递归执行步骤②当遇到空串时，递归结束第四节树和森林树的存储结构父结点表示法孩子结点表示法孩子-兄弟表示法父结点表示法树中每个结点至少含两个域，一个域用来保存结点本身的值，另一个域用来保存结点之父结点的相关信息孩子结点表示法父结点-孩子结点表示法孩子-兄弟表示法为树中的每个结点定义一个存储结点，其中有左、右两个指针域，左指针域指向这个结点的第一个孩子结点，右指针域指向这个结点的下一个兄弟结点树、森林与二叉树的转换树和二叉树都可以用二叉链表作为存储结构同一个二叉链表，若按树的存储含义来解释，可以还原为树。若按二叉树的存储含义来解释，可以还原为二叉树正是因为这一点，可以在树与二叉树之间建立一种对应关系转换规则规则1：将森林转换成二叉树设F={T1,T2,…,Tm}是森林，则可按如下规则将森林F转换为一棵二叉树B=(root,LB,RB)（1）若F为空（m=0），则B为空树（2）若F非空（m>0），则森林中T1的根作为二叉树B的根root；T1中各子树组成的森林F1={T11,T12,…,T1s}转换成的二叉树作为B的左子树BL；森林F’={T2,T3,…,Tm}转换成的二叉树作为B的右子树BR森林转换为二叉树转换规则规则2：将二叉树还原为森林设B=(root,BL,BR)是一棵二叉树，则可按如下规则转换成森林F={T1,T2,…,Tm}（1）若B为空，则F为空（2）若B非空，则B的根root作为F中第一棵树T1的根；B的左子树BL还原得到的森林作为T1的各子树；B的右子树BR还原得到的森林作为F中的T2,T3,…,Tm树和森林的遍历树的两种遍历策略先序（根）遍历先访问树的根结点，再依次先序遍历根结点的各棵子树后序（根）遍历若树的根结点有子树，则首先后序遍历各棵子树，然后再访问根结点；否则（根结点无子树），只访问根结点森林的两种遍历策略先序遍历森林森林的先序遍历过程，是按照树的排列次序，先序遍历各棵树后序遍历森林森林的后序遍历过程，是按照树的排列次序，后序遍历各棵树可以看出，森林的遍历序列中，各棵树中的结点不会混杂在一起森林与对应的二叉树的遍历序列的关系二叉树的先序遍历序列和中序遍历序列，与森林的先序遍历序列和后序遍历序列分别相同第五节哈夫曼树及哈夫曼编码编码ASCII编码、Unicode码、电报码定长编码算法简单，效率高在编码长度确定之后，译文的长度完成取决于原文的长度变长编码变长编码前缀特性：一个编码方案中，任何一个字符的编码都不是该方案中任何其他字符编码的前缀，这样的编码称为具有前缀特性正是因为编码方案具有前缀特性，才能够保证译码过程的正确性和唯一性。可以使用二叉树来表示一个编码方案在二叉树的分支上标注0或1，从根到某结点的路径上，各分支标注的0或1组成一个编码哈夫曼树二叉树中，叶结点的带权路径长度定义为叶结点的权值乘上其到根结点的路径长度二叉树的带权路径长度，就是树中所有叶结点的带权路径长度之和二叉树的外部带权路径长度记为WPL其中n为叶结点个数，wk为第k个叶结点的权值，lk为第k个叶结点的路径长度各字符出现的频度分别是6、12、25、30，构造4棵二叉树，分别计算其WPL值4棵二叉树的带权路径长度WPL分别为134、195、139和146我们的任务是构造具有最小WPL且满足前缀特性的编码树设有n个权值{w1,w2,…,wn}，构造具有n个叶结点的二叉树，每个叶结点带有一个权值wi。在所有这样的二叉树中，带权路径长度WPL最小的一棵二叉树称为哈夫曼树构造哈夫曼树的算法根据给定的n个权值{w1,w2,…,wn}(n≥2)，构造含n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti(1≤i≤n)只有一个根结点，它带有权值wi(i=1,2,…,n)在F中选出两棵根结点权值最小（如果有相等的权值，则任意选）的二叉树分别作为左、右子树，新增加一个根结点，从而构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点的权值之和。然后从F中删去选出的这两棵树，加入这棵新构造的树重复步骤②，直到F中只有一棵树时为止，这棵树就是哈夫曼树示例已知字符集S={a,b,c,d,e}，对应的权值为{17,25,12,6,14}，试构造哈夫曼树，并计算其WPL初始时，5个权值分别对应一棵单结点的树，并按权值从小到大排序选择权值最小的两棵树进行合并，新增加的根结点表示为圆形结点。新树的根结点的权值是18，选择权值小的树作为左子树，权值大的树作为右子树继续选择权值最小的两棵树进行合并。新树的根结点的权值是31。将选中的两棵树删除，增加新合并的树继续这个过程最后得到的结果WPL=14

2+17

2+6

3+12

3+25

2=166哈夫曼算法得到的哈夫曼树中没有度为1的结点，因为每次合并时都选择了两棵树分别作为左子树和右子树初始时如果给定的权值个数为n，则哈夫曼树的构建过程需要n-1步。得到的哈夫曼树中，叶结点个数为n，分支结点个数为n-1，结点总数为2n-1哈夫曼编码在哈夫曼树中，对于所有的分支结点，其左分支标以0，右分支标以1。这样标记以后，将从根到叶结点的路径上标记的0和1依次收集起来，可以得到叶结点对应字符的具体编码，这就是哈夫曼编码哈夫曼树及编码编码的带权平均码长=译文总位数/原文字符总数=166/74

2.24已知译文是110010101111000011，其原文是什么？从哈夫曼树根开始，根据编码的各位决定选择的分支，前2位是11，故得到字符b。接下来，00对应于字符e。依此类推。最终得到的原文是becabdebThankYou!全国高等教育自学考试指定教材

计算机及应用专业（专科段）数据结构第六章图结构学习目标理解图的定义和相关的基本概念掌握图的邻接矩阵和邻接表存储结构掌握图基本操作的实现掌握并实现图的深度优先和广度优先搜索算法，理解图的连通性及连通分量概念理解图的生成树概念，掌握求图最小代价生成树的两个算法理解有向无环图的概念，掌握图的拓扑排序算法理解最短路径概念，掌握迪杰斯特拉算法的求解过程了解各算法的时间复杂度本章主要内容图的基本概念12图基本操作的实现3图的存储结构图的遍历4图的生成树56单源最短路径7DAG图及拓扑排序第一节图的基本概念图（graph）由顶点和边组成一般地，用G=(V,E)来表示，其中V表示顶点（vertex）集，是一个有穷非空集合；E表示边（edge）集，E中的每条边都是V中某一对顶点的连接当顶点分别是u和v时，连接这两个顶点的边可以表示为一个二元组(u,v)，有时也将边称为顶点的偶对图中任意两个不同顶点之间允许有边，但不能超过一条基本概念图G=(V,E)中，顶点总数记为|V|，边的总数记为|E|如果图中边的数目较少（相对于顶点数来说），则图称为稀疏图边数较多的图称为密集图或是稠密图至于边数多到多少是密集图或少到多少是稀疏图，并没有严格的界定当图中边数的数量级不高于顶点数的数量级时，就可以认为图是稀疏图基本概念当图中的边限定为从一个顶点指向另一个顶点时，称为有向边，或称为弧（arc）不限定方向的边称为无向边一条无向边可以看成是两条方向相反的有向边组成有向边的偶对看作是有序的组成无向边的偶对是无序的基本概念有向边(u,v)表示从顶点u指向顶点v的边，弧的方向是从u指向v，u称为弧尾（tail），v称为弧头（head）对于有向边，(u,v)与(v,u)不同无向边(u,v)既可以表示从顶点u指向顶点v，也可以表示从顶点v指向顶点u对于无向边，(u,v)与(v,u)是等价的基本概念含有向边的图称为有向图（directedgraph或简写为digraph）如果图中的边都是无向边，则图称为无向图（undirectedgraph或简写为undigraph）如果一个图中既含有有向边，又含有无向边，则可以将其中所有的无向边表示为一对方向相反的有向边提到有向图时，表明其中所含的边全部都是有向边基本概念若无向图G中含有边(u,v)，则u和v互为邻接点（adjacent）边(u,v)称为与顶点u和v相关联（incident），也可以说边(u,v)依附于顶点u和v对于有向图中的有向边(u,v)，称顶点v是顶点u的邻接点顶点u邻接到顶点v，或顶点v邻接自顶点u可以给边赋予一个非负的数值，这个非负数值称为边的权（weight），相应的图称为带权图（weightedgraph）或是加权图可以让各顶点带有标号，这样的图称为标号图（labedledgraph）本章讨论的图大多是标号图，标号可以作为顶点的名称示例图中两个顶点之间的边不能有重复无向图中两个顶点之间最多只能有一条边有向图中两个顶点之间最多有两条方向相反的弧图中不包含(i,i)形式的边，即没有顶点自身到自身的边在无向图中，与顶点v相关联的边的数目称为顶点的度（degree）在有向图中，顶点的度分为出度和入度以某顶点为弧头的弧称为该顶点的入边，入边的数目称为该顶点的入度以某顶点为弧尾的弧称为该顶点的出边，出边的数目称为该顶点的出度一个顶点的出度和入度之和称为该顶点的度有n个顶点的无向图中，其边数最多可达n(n-1)/2有向图中由于边具有方向性，所以可能的最大边数比无向图多了一倍，含n个顶点的有向图中最大边数为n(n-1)

包含了所有可能边的图称为完全图（completegraph）假设无向图G=(V,E)中含有n个顶点，e条边，每个顶点的度为di(0≤i≤n-1)，则下列关系式成立：若两个图G=(V,E)和G'=(V',E')，满足条件：V’V，E’E且E'中边依附的顶点均属于V'，则称G'为G的子图（subgraph）一个图G的子图是指由图G中选出其顶点集的一个子集Vs以及仅与Vs中顶点相关联的一些边所构成的图示例对于图G，图G1、G2、G3和G4都是它的子图；特别地，图G1与图G完全一样，它也是图G的子图，即图本身也是它自身的子图；同时，图G2也是图G4的子图。而图G5不是图G的子图在图G=(V,E)中，如果(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)都是E中的边，则顶点序列(vi0,vi1,…,vim-1)称为从顶点vi0到顶点vim-1的路径（path）若图G是有向图，则路径也要求是有向的，且有向边必须是方向一致的，即有向路径(vi0,vi1,…,vim-1)是由E中的弧(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)组成的路径(vi0,vi1,…,vim-1)中包含的边或弧的数目m称为路径长度如果路径上各顶点均不同，则称此路径为简单路径（simplepath）第一个顶点和最后一个顶点相同的路径称为回路（cycle），也称为环如果一个回路中除第一个顶点和最后一个顶点之外，其余顶点均不相同，则称为简单回路（simplecycle）或简单环不带回路的图称为无环图。不带回路的有向图称为有向无环图从顶点0到顶点3到顶点4再到顶点1构成一条有向简单路径(0,3,4,1)，路径长度为3从顶点2到顶点3到顶点4再回到顶点2构成一个简单有向回路(2,3,4,2)从顶点2到顶点0再到顶点3，虽然其中均有边相连，但由于边的方向不一致，所以不能构成有向路径对于无向图G，如果顶点u和顶点v之间有路径，则称这两个顶点是连通的如果无向图G中任意一个顶点到其他任意顶点都至少存在一条路径，也就是说，图中任意两个顶点都是连通的，则称图G为连通图（connectedgraph）无向图中的极大连通子图称为连通分量（connectedcomponent）有向图G中，如果每对顶点u与v之间均有从u到v的有向路径，则称G为强连通图（stronglyconnectedgraph）有向图的最大强连通子图称为强连通分量如果对于每对顶点u和v，存在顶点序列vi0,vi1,…,vim-1，这里u=vi0，v=vim-1，并且(vij,vij+1)∈E或(vij+1,vij)∈E(0≤j≤m-2)，则称图G为弱连通图（weaklyconnectedgraph）示例图的基本操作VType表示顶点类型MEdge表示边的类型图的基本操作定义顶点使用单字符表示，保存在顶点表verticesList[MaxVtxNum]中，使用两个辅助方法，在顶点字符与顶点表下标之间进行转换intVerToNum(MGraphg,VTypeu) //返回顶点u在顶点表verticesList中的下标值VType

NumToVer(MGraphg,inti) //返回顶点表verticesList中下标i对应的顶点第二节图的存储结构图也有两类基本的存储方式，即顺序存储结构及链式存储结构顺序存储结构以邻接矩阵（adjacencymatrix）为代表链式存储结构以邻接表（adjacencylist）为代表邻接矩阵设图G=(V,E)，|V|=n，图的邻接矩阵是一个n

n矩阵，矩阵元素表示图中各顶点之间的邻接关系，邻接矩阵也称为相邻矩阵设各顶点为v0,v1,…,vn-1，如果从vi到vj存在一条边，则邻接矩阵中位于i行j列的元素值为1，否则值为0这样的一个矩阵可以表示图中所有顶点之间的邻接关系邻接矩阵的存储空间与顶点个数有关，为O(|V|2)邻接矩阵是一个二维数组对于带权图邻接矩阵是对称矩阵有向图的邻接矩阵不能保证对称性用邻接矩阵表示图时，可以很容易地判定图中任意两顶点之间是否存在边（或弧）若矩阵元素A[i][j]为1或wij，就表示从vi到vj有一条边（或弧），否则从vi到vj没有边（或弧）存在借助于邻接矩阵，很容易得到图中各顶点的度对于无向图G，邻接矩阵i行或i列中非零元素的个数即为顶点vi的度对于有向图G，邻接矩阵i行中非零（也不等于∞）元素的个数为顶点vi的出度而i列中非零（也不等于∞）元素的个数为顶点vi的入度i行非零（也不等于∞）元素的个数加上i列非零（也不等于∞）元素的个数为顶点vi的度设用邻接矩阵表示有n个顶点的图G，计算G中有多少条边时，需要检查矩阵中的所有元素，因此时间复杂度为O(n2)存储空间仅与图G中的顶点数有关，与边数无关，即为O(n2)设图G=(V,E)，则G的邻接表由一个一维数组和n=|V|个链表组成一维数组包含n个元素，每个元素包含表示顶点信息的域和一个指针域与顶点vi(0≤i≤n-1)相邻接的所有顶点组成一个单链表，其表头指针保存在一维数组下标为i的元素的指针域中邻接表邻接表表结点的结构对于带权图，可以扩展邻接表的结构，在单链表的每个表结点中增加一个域，用来存储两个顶点间这条边的权表结点结构用邻接表表示有n个顶点和e条边的无向图时，需要一个由n个元素组成的顺序表（表头结点表）和由总共2e个结点组成的n个单链表表示有n个顶点e条弧的有向图时，需要一个由n个元素组成的顺序表和由总共e个结点组成的n个单链表邻接表的空间复杂度为O(n+e)当图中顶点个数经常变化时，为便于顶点的插入和删除，也可以将图的全部顶点保存在一个单链表中，而不是一维数组中。单链表中的结点结构如下所示指向下一顶点的指针指向邻接点表的指针顶点信息第三节图基本操作的实现采用邻接矩阵存储的图的定义顶点表的相应查询查询边的权值创建图创建无向图创建有向带权图验证图构建函数的正确性找到某顶点的第一个邻接点查找下一个邻接点获取顶点个数及边数intgetNumVertices(MGraphg){ returng.numVertices;}intgetNumEdges(MGraphg){ returng.numEdges;}第四节图的遍历定义6.1给定一个连通图G=(V,E)，从图中的某个顶点出发，经过一定的路线访问图中的所有顶点，使每个顶点被访问且只访问一次，这一过程称为图的遍历深度优先搜索（depthfirstsearch,DFS）遍历广度优先搜索（breadthfirstsearch,BFS）遍历深度优先搜索选择图中任意指定顶点为起始顶点，将其设为当前顶；访问当前顶点v，输出关于v的相关信息将v的访问标志置为VISITED如果v的邻接点中存在未被访问的顶点w，则将w设为当前顶点，转②继续；否则转⑤回退到最近被访问过的且仍有未被访问邻接点的顶点u，转④继续；不能回退时，转⑥如果所有顶点均已访问，则遍历结束，否则，选择未被访问的另一个顶点作为起始顶点，继续上述过程v0,v1,v3,v7,v4,v5,v2,v6DFS算法当图是连通图时，使用DFS算法从某个顶点出发，可以访问到图中的所有顶点。如果图不连通，则一次调用DFS不能访问图中的全部顶点，只能访问初始顶点所在的连通分量中的所有顶点广度优先搜索选择图中指定的顶点v为起始顶点，将其入队列，且其访问标志置为VISITED队列为空时，转⑤；队列不为空时，出队列，设出队列的顶点为w输出关于w的相关信息找到与顶点w相邻接的且访问标志不是VISITED的顶点序列w1,w2,…,wk，依次入队列，转②如果所有顶点均已访问，则遍历结束，否则，选择未被访问的一个顶点作为起始顶点，继续上述过程广度优先搜索过程中，使用了一个队列作为辅助存储结构，顶点是一批批加入队列的如果图是不连通的，则这个过程也不能访问图中的全部顶点，而只能遍历图中某个连通分量中的所有顶点BFS算法第五节图的生成树设G=(V,E)是一个连通的无向图，包含图中全部顶点的极小连通子图称为图的生成树极小连通子图是指含有图中所有顶点并使图仍保持连通性的最小子图从图中任一顶点出发，按照深度优先搜索策略或是广度优先搜索策略，可以访问到图中的全部顶点。在遍历的过程中，所经过的边集设为T(G)，没有经过的边集设为B(G)。T(G)即构成G的一棵生成树生成树中所含的边数必定是n-1进行深度优先搜索时得到的生成树称为深度优先生成树进行广度优先搜索时得到的生成树称为广度优先生成树进行遍历时可能会得到不同的顶点序列，实际上，图的生成树也可能是不唯一的同一个图的深度优先生成树，也可能不是唯一的广度优先生成树，也可能不是唯一的示例两棵深度优先生成树图的最小代价生成树带权图的每条边上都有一个非负的权值，称边权值之和最小的生成树为最小代价生成树（minimum_costspanningtree，MST）。简称为最小生成树给定一个无向连通图G，则MST是一个包括G的所有顶点及其边子集的图，边的子集满足下列条件这个子集中所有边的权之和为所有满足条件的子集中最小的子集中的边能够保证图是连通的最小生成树性质它含有图G中的所有n个顶点它没有回路。因为从构成回路的各边中去掉一条边，仍能保证其连通性，而所得的权值总和可以进一步地减少它含有的边数为n-1去掉最小生成树中的一条边，换上不在最小生成树中的另外一条边，在仍要求连通的前提下，所得的权值总和都不会小于原最小生成树的权值总和普里姆算法设连通的带权图G=(V,E)，V是顶点集合，E是边的集合设T是图G的最小生成树的边集合，U是最小生成树的顶点集合，设由顶点v1开始，初始时T=Ф，U={v1}在所有u∈U，v∈V-U的边(u,v)∈E中选择一条权最小的边(ui,vj)，将vj并入U中，将边(ui,vj)并入T中重复②，直到U=V时结束示例普里姆算法是贪心算法的一个实例，每次选出一条连接U中顶点及V-U中顶点的具有最小权值的边，逐步生成最小生成树普里姆算法共进行n-1轮的选边操作，每轮选边时，最多从n-1条边中选中权最小的边。故对于含|V|个顶点的图，算法的时间复杂度为O(|V|2)当图是一个边稠密的图时，适合使用普里姆算法求图的最小生成树克鲁斯卡尔算法设E1的初值：E1=Φ，T中只含有图中的所有顶点，顶点个数为n=|V|当E1中边数小于n-1时，重复执行下面的步骤在图G的边集E中选择权值最小的边(u,v)，并从E中删除它如果u和v分别属于T中不同的连通分量，则将边(u,v)加入到E1中去，否则丢掉该边，选择E中的下一条权值最小的边边权值(6,8)2(7,8)2(5,8)3(1,3)4(3,4)5(4,7)5(1,4)6(1,2)6(3,7)6(2,5)7(2,6)7(5,6)10(4,5)14克鲁斯卡尔算法中，从|E|条边中选出权值最小的边(u,v)，并检测u和v是不是在同一连通分量上，时间花费为O(|E|log|E|)。所以，克鲁斯卡尔算法适宜求稀疏图的最小生成树第六节有向无环图及拓扑排序图中不存在回路的有向图称为有向无环图（directedacyclinegraph），简称为DAG图比如，表达式树可表示为DAG图拓扑排序有向无环图G=(V,E)的拓扑序列是G中顶点的一个线性序列，并且满足以下关系：对于图G中的所有顶点v和w，如果(v,w)∈E，则在线性序列中v排在w之前求有向无环图拓扑序列的过程称为拓扑排序在有向图中，以顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为顶点表示活动的网络（activityonvertexnetwork），简称为AOV网在AOV网中，若从顶点vi到vj有一条有向路径，则称vi是vj的前驱，vj是vi的后继若(vi,vj)是AOV网中的一条弧，则称vi是vj的直接前驱，vj是vi的直接后继如果vi是vj的前驱或直接前驱，则vi活动必须在vj活动开始之前结束，即vj活动必须在vi活动结束之后才能开始在AOV网中不允许出现回路，因此AOV网必是有向无环图拓扑排序可以将AOV网中的各个活动排序，它把AOV网中各顶点按照它们之间的先后关系排成一个线性序列在AOV网中，如果从顶点vi到顶点vj存在有向路径，则在拓扑序列中，vi必定排在vj的前面；如果从顶点vi到顶点vj没有有向路径，则在拓扑序列中，vi与vj的先后次序可以任意五门课程排成的拓扑序列为 C1,C2,C3,C4,C5还可以排列成 C1,C2,C5,C3,C4课程代号课程名称先导课C1高等数学无C2程序设计基础无C