非线性数据结构优秀PPT.ppt

《非线性数据结构优秀PPT.ppt》由会员分享，可在线阅读，更多相关《非线性数据结构优秀PPT.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非线性数据结构非线性数据结构第一页，本课件共有100页3.1数数组组3.1.1引言数数组组是是大大家家已已经经很很熟熟悉悉的的一一种种数数据据类类型型，几几乎乎所所有的程序设计语言都把数组类型设定为固有类型。有的程序设计语言都把数组类型设定为固有类型。数组(array)可可看看成成是是线线性性表表的的推推广广，是是最最常常用用的的数数据据结结构构之之一一。数数组组是是有有限限个个数数组组元元素素的的集集合合；数数组组的的每每个个元元素素与与一一组组下下标标相相对对应应；和和线线性性表表一一样样，数数组组中中所所有有数组元素的数据类型必须一致。数组元素的数据类型必须一致。第二页，本课件共有100

2、页3.1.2数组的逻辑结构数组的逻辑结构逻辑关系是非线性的，实质上是多个线性关系的组合。逻辑关系是非线性的，实质上是多个线性关系的组合。Amn=a11a12.a1na21a22.a2nam1am2.amn如下所示，就是一个如下所示，就是一个m行行n列的二维数组列的二维数组(也称为矩阵也称为矩阵)，记，记作作Am,n。第三页，本课件共有100页矩矩阵阵A可可以以看看成成是是由由m个个行行向向量量组组成成的的向向量量，也也可可以以看看成是由成是由n个列向量组成的向量。个列向量组成的向量。在在矩矩阵阵A A中中，每每个个元元素素a aijij都都属属于于两两个个线线性性表表。一一个个是是第第i i行

3、行的的行表(a(ai1i1，a ai2i2，.，a aijij，.，a ainin)，另另一一个个是是第第j j列列的的列表(a(a1j1j，a a2j2j，.，a aijij，.，a amjmj)。这这种种行行表表(行行向量向量)和列表和列表(列向量列向量)都相当于线性表都相当于线性表。所所以以说说，数组可看作是线性表的推广，将将线线性性表表推推广广到到二维或高维，就是我们所说的数组。二维或高维，就是我们所说的数组。第四页，本课件共有100页3.1.3数组的存储结构数组的存储结构数数组组的的顺顺序序分分配配就就是是用用向向量量作作为为数数组组的的存存储储结结构构。但但是是二二维维以以上上的的

4、多多维维数数组组，不不像像一一维维数数组组那那样样，所所有有的的元元素素已已经经排排成成一一个个序序列列，所所以以要要把把多多维维数数组组顺顺序序地地存存储储到到一一维维顺顺序序的的存存储储器器中中，则则必必须须对对多多维维数数组组里里的的元素存放顺序做出一些规定。元素存放顺序做出一些规定。通常数组采用通常数组采用两种顺序存储方式。第五页，本课件共有100页1)行优先顺序存储行优先顺序存储行优先顺序存储就是就是数组元素按行表次序进行存储，数组元素按行表次序进行存储，即第即第i+1i+1个行表紧跟在第个行表紧跟在第i i个行表后面进行存储个行表后面进行存储。在在C、BASIC、PASCAL、CO

5、BOL等高级语言中均采用这种等高级语言中均采用这种方法。方法。以以二二维维数数组组Amn为为例例，按按行行优优先先顺顺序序存存储储的的数数组组元元素素次序为：次序为：a11，a12，a1n，a21，a22，a2n，am1，am2，amn第六页，本课件共有100页2)列优先顺序存储列优先顺序存储列优先顺序存储就是就是数组元素按列表次序进行存储，数组元素按列表次序进行存储，即第即第j+1j+1个列表紧跟在第个列表紧跟在第j j个列表后面进行存储个列表后面进行存储。在。在FORTRAN语言中，数组是按列优先顺序组织存储。语言中，数组是按列优先顺序组织存储。以以二二维维数数组组Amn为为例例，按按列列

6、优优先先顺顺序序存存储储的的数数组组元元素次序为：素次序为：a11，a21，am1，a12，a22，am2，a1n，a2n，amn第七页，本课件共有100页二维数组的两种存储方式二维数组的两种存储方式第八页，本课件共有100页同同样样，对对n维数组也也有有上上述述两两种种不不同同的的顺顺序序分分配配的的存存储储结结构构。当当把把n n维维数数组组的的元元素素这这样样顺顺序序地地存存放放在在存存储储器器里里，则则每每个个元元素素的的存存储储地地址址可可以以用用公公式式计计算算出出来来。这些计算公式称为这些计算公式称为“地址公式”。假设每个数据元素占假设每个数据元素占k个存储单元，则可得个存储单元

7、，则可得（1）一维数组的地址公式为：的地址公式为：Loc(ai)=Loc(a1)+(i-1)*k（2）若若存存储储分分配配采采用用行优先顺顺序序分分配配，则则二维数组Amn的地址公式为：的地址公式为：Loc(aij)=Loc(a11)+(i-1)*n+(j-1)*k第九页，本课件共有100页同同理理，可可写写出出三维数组、n维数组的的数数组组元元素素存储地址的计算公式。存储地址的计算公式。（3）若若存存储储分分配配采采用用列优先顺顺序序分分配配，则则二维数组Amn的地址公式为：的地址公式为：Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L同同理理，可可写写出出三维数组、n维数

8、组的的数数组组元元素存储地址的计算公式。素存储地址的计算公式。第十页，本课件共有100页3.1.4特殊矩阵的压缩存储特殊矩阵的压缩存储假假若若值值相相同同的的元元素素或或零零元元素素在在矩矩阵阵中中的的分分布布有有一一定定规规律律，则则称称此此类类矩矩阵阵为为特殊矩阵。像像三三角角矩矩阵阵，对对称称矩矩阵、三对角矩阵等阵、三对角矩阵等都属于特殊矩阵。都属于特殊矩阵。通通常常在在实实际际计计算算中中经经常常出出现现一一些些阶阶数数很很高高的的矩矩阵阵，同同时时矩矩阵阵中中有有许许多多值值相相同同的的元元素素或或者者零零元元素素。有有时时为为了了节节省省存存储储空空间间，可可以以对对这这类类矩矩阵

9、阵进进行行压压缩缩存存储储。所所谓谓压缩存储是是指指：为为多多个个值值相相同同的的元元素素只只分分配配一一个个存存储储空空间间；对零元素不分配空间对零元素不分配空间。第十一页，本课件共有100页1）三角矩阵）三角矩阵例：下三角矩阵例：下三角矩阵Ann，当，当i1，则则其双亲是结点。其双亲是结点。(2)如果如果2in，则结点，则结点i无左孩子；否则其左孩子是无左孩子；否则其左孩子是2i。(3)如如果果2i+1n，则则结结点点i无无右右孩孩子子；否否则则其其右右孩孩子子是是结点结点2i+1。证明从略。证明从略。第三十三页，本课件共有100页3、满二叉树和完全二叉树的关系、满二叉树和完全二叉树的关系

10、满二叉树满二叉树=完全二叉树完全二叉树满二叉树满二叉树完全二叉树完全二叉树4、平衡二叉树、平衡二叉树二二叉叉树树上上任任一一结结点点的的左左子子树树深深度度减减去去右右子子树树深深度度的的差差值值，称称为为此结点的平衡因子。此结点的平衡因子。若若一一棵棵二二叉叉树树中中，每每个个结结点点的的平平衡衡因因子子之之绝绝对对值值都都不不大大于于1，则则称这棵二叉树为平衡二叉树。称这棵二叉树为平衡二叉树。(a)是平衡二叉树是平衡二叉树(b)不是平衡二叉树不是平衡二叉树第三十四页，本课件共有100页 3.2.3.3 二叉树的存储结构二叉树的存储结构对对于于二二叉叉树树，我我们们既既可可采采用用顺顺序序存

11、存储储，又又可可采采用用链链式存储。式存储。1顺序存储结构顺序存储结构顺顺序序存存储储就就是是将将一一棵棵二二叉叉树树的的所所有有结结点点按按照照一一定定的的次次序序顺顺序序存存放放到到一一组组连连续续的的存存储储单单元元中中，为为此此，必必须须把把二二叉叉树树中中所所有有结结点点构构成成一一个个适适当当的的线线性性序序列列，以以使使各各个个结结点点在在这这个个序序列列中中的的相相互互位位置置能能反反映映出出结结点点之之间的逻辑关系。间的逻辑关系。第三十五页，本课件共有100页对于完全二叉树，按图的编号顺序，就能得到一对于完全二叉树，按图的编号顺序，就能得到一个足以反映整个二叉树结构的线性序列

12、。因此，可将个足以反映整个二叉树结构的线性序列。因此，可将完全二叉树中所有结点按编号顺序依次存储到一组连完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元续的存储单元(即向量即向量)中，这样既不浪费内存，又可以中，这样既不浪费内存，又可以利用地址公式确定其结点的位置。利用地址公式确定其结点的位置。1234567ABDEFCJ第三十六页，本课件共有100页但对于一般的二叉树，顺序分配常会造成内存的浪费，但对于一般的二叉树，顺序分配常会造成内存的浪费，因为一般的二叉树也必须按完全二叉树的形式来存储。因为一般的二叉树也必须按完全二叉树的形式来存储。1234567891011ABDEFCJGH

13、第三十七页，本课件共有100页 2链式存储结构链式存储结构因为树型结构是非线性的结构，所以在存储器里因为树型结构是非线性的结构，所以在存储器里表示树型结构的最自然的方法是链式存储。根据二叉表示树型结构的最自然的方法是链式存储。根据二叉树的特性，任何一个结点最多有左、右两棵子树，所树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域：数据域和左、右指针域。以每个结点至少设有三个域：数据域和左、右指针域。其结点结构为：其结点结构为：lchilddatarchild第三十八页，本课件共有100页第三十九页，本课件共有100页二叉链表结点的类型定义二叉链表结点的类型定义typedef

14、structnodedatatypedata;structnode*lchild,*rchild;bstree;第四十页，本课件共有100页3.2.3.4 二叉树的遍历二叉树的遍历遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为基础的。按照对二叉树中根结点、左子树和右子树访问的先后顺序，共有三种遍历二叉树的方法：根、左、右；左、根、右；左、右、根根据这三种方法中根结点被访问的

15、先后，分别称之为二叉树的先序(根)遍历，中序(根)遍历和后序(根)遍历。第四十一页，本课件共有100页(1)先序遍历：先序遍历：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则访问根结点；访问根结点；先序遍历左子树；先序遍历左子树；先序遍历右子树。先序遍历右子树。遍历序列：ABDEGHCF第四十二页，本课件共有100页先序遍历的算法先序遍历的算法voidpreorder(bstree*p)if(p!=NULcL)printf(“%5”,p-data);preorder(p-lchild);preorder(p-rchild);第四十三页，本课件共有100页(2)中序遍历：中序遍历：若二

16、叉树为空，则空操作；否则若二叉树为空，则空操作；否则中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。遍历序列：遍历序列：DBGEHACF第四十四页，本课件共有100页中序遍历算法中序遍历算法voidpreorder(bstree*p)if(p!=NULcL)inorder(p-lchild);printf(“%5”,p-data);inorder(p-rchild);第四十五页，本课件共有100页(3)后序遍历：后序遍历：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则后序遍历左子树；后序遍历左子树；后序遍历右子树。后序遍历右子树。访问根结点；访

17、问根结点；遍历序列：DGHEBFCA第四十六页，本课件共有100页后序遍历算法后序遍历算法voidposorder(bstree*p)if(p!=NULcL)posorder(p-lchild);posorder(p-rchild);printf(“%5”,p-data);第四十七页，本课件共有100页3.2.4 树的存储结构树的存储结构树树在在计计算算机机内内存存储储，可可以以用用顺顺序序存存储储方方式式、也也可可以以用用链链式式存存储储方方式式，这这主主要要取取决决于于要要对对树树结结构构进进行行什什么么运算。这里主要介绍链式分配的存储结构。运算。这里主要介绍链式分配的存储结构。孩子孩子-

18、兄弟表示法的链式存储结构表示如下：兄弟表示法的链式存储结构表示如下：firstdatanext链表中结点的两个指针域分别指向该结点的第一个孩子链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟结点。和下一个兄弟结点。第四十八页，本课件共有100页RADEFCBGKHR A DE C HF GBK第四十九页，本课件共有100页 3.2.5 树的遍历树的遍历树树的的遍遍历历有有两两种种次次序序：一一种种是是先先序序遍遍历树；另一种是后序遍历树。历树；另一种是后序遍历树。(1)先先序序遍遍历历树树：先先访访问问树树的的根根结结点点，然然后后从从左左到到右右依依次次先先序序遍遍历历根根的的每

19、每棵棵子子树树。如如先先序序遍遍历历右右图图所所示示的的树树，得得到到的的结结点点序序列列为为：RADEBCFGHK。(2)后序遍历树：先从左到右依次后根遍后序遍历树：先从左到右依次后根遍历每棵子树，然后访问根结点。如后序遍历右历每棵子树，然后访问根结点。如后序遍历右图所示的树，得到的结点序列为：图所示的树，得到的结点序列为：DEABGHKFCR。RADEFCBGKH第五十页，本课件共有100页3.2.6 树、森林与二叉树的转换树、森林与二叉树的转换由由于于二二叉叉树树和和树树都都可可用用二二叉叉链链表表作作为为存存储储结结构构，则则以以二二叉叉链链表表作作为为媒媒介介可可导导出出树树与与二二

20、叉叉树树之之间间的的一一个个对对应应关关系系。也也就就是是说说，给给定定一一棵棵树树，可可以以找找到到惟惟一一的的一一棵棵二二叉叉树树与与之之对对应应，从从物物理理结结构构来来看看，它它们们的的二二叉叉链链表表是是相相同同的的，只只是是解解释释不不同同而而已已。图图3-15给给出出了了树树与与二叉树之间的对应关系。二叉树之间的对应关系。第五十一页，本课件共有100页图3-15树与二叉树的对应关系第五十二页，本课件共有100页下面给出树与二叉树之间的转换规则。下面给出树与二叉树之间的转换规则。1一般树转换为二叉树一般树转换为二叉树步骤步骤：(1)加线：亲兄弟之间加一虚连线。加线：亲兄弟之间加一虚

21、连线。(2)抹抹线线：抹抹掉掉(除除最最左左一一个个孩孩子子外外)该该结结点点到到其其余余孩孩子之间的连线。子之间的连线。(3)旋转：新加上去的虚线改实线且均向右斜旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜，原有的连线均向左斜(lchild)。第五十三页，本课件共有100页图3-16一般树转换为二叉树的操作过程(a)一般树；(b)加线后；(c)抹线后；(d)旋转后第五十四页，本课件共有100页 2森林转换为二叉树森林转换为二叉树森森林林是是树树的的有有限限集集合合，利利用用树树的的转转换换思思想想，可可以以实实现森林到二叉树的转换。现森林到二叉树的转换。步骤步骤：

22、(1)将各棵树分别转换为二叉树。将各棵树分别转换为二叉树。(2)按按给给出出森森林林中中树树的的次次序序，依依次次将将后后一一棵棵二二叉叉树树作作为为前前一一棵棵二二叉叉树树根根结结点点的的右右子子树树，则则第第一一棵棵树树的的根根结结点是转换后二叉树的根。点是转换后二叉树的根。第五十五页，本课件共有100页图3-17森林转换成对应的二叉树的过程(a)森林；(b)各棵树对应的二叉树；(c)转换成的二叉树第五十六页，本课件共有100页3.2.7树的应用树的应用树结构被广泛地用于分类、检索、数据库及人工智能等方面。树结构被广泛地用于分类、检索、数据库及人工智能等方面。二叉排序树二叉排序树二叉排序树

23、是一种动态树表。二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性或者是一棵具有如下性质的二叉树：质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。二叉排序树的性质：左、右子树本身又各是一棵二叉排序树。二叉排序树的性质：按中序按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列

24、。遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。第五十七页，本课件共有100页（1）二叉排序树生成：）二叉排序树生成：从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。棵二叉排序树。插入一个结点的操作按下述方法完成：插入一个结点的操作按下述方法完成：若原二叉排序树为空，则将待插结点作为此数的根结点。若原二叉排序树为空，则将待插结点作为此数的根结点。若原二叉排序树不为空，若原二叉排序树不为空，则比较待插结点和根结点的关键字值；则比较待插结点和根结点的关键字值；若待插元素的关键字值小于根结点的的关键字值，

25、则将其插入到左子若待插元素的关键字值小于根结点的的关键字值，则将其插入到左子数中；否则，将其插入到右子树中；数中；否则，将其插入到右子树中；在二叉排序树的左右子树中的插入过程同上。在二叉排序树的左右子树中的插入过程同上。例：对于一组关键字例：对于一组关键字51，34，79，18，45，86，生成，生成对应的二叉排序树对应的二叉排序树第五十八页，本课件共有100页（2）二叉排序树的删除）二叉排序树的删除:假设被删结点是假设被删结点是*p，其双亲是，其双亲是*f，不失一般性，设，不失一般性，设*p是是*f的左孩子，下的左孩子，下面分三种情况讨论：面分三种情况讨论：若结点若结点*p是叶子结点，则只需

26、修改其双亲结点是叶子结点，则只需修改其双亲结点*f的指针即可的指针即可.若结点若结点*p只有左子树只有左子树PL或者只有右子树或者只有右子树PR，则只要使，则只要使PL或或PR成为其成为其双亲结点的左子树即可。双亲结点的左子树即可。若结点若结点*p的左、右子树均非空，先找到的左、右子树均非空，先找到*p的中序前趋结点的中序前趋结点*s（注意（注意*s是是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做的左子树中的最右下的结点，它的右链域为空），然后有两种做法：法：令令*p的左子树直接链到的左子树直接链到*p的双亲结点的双亲结点*f的左链上的左链上,而而*p的右子树链到的右子树链到*

27、p的中序前趋结点的中序前趋结点*s的右链上。的右链上。以以*p的中序前趋结点的中序前趋结点*s代替代替*p（即把（即把*s的数据复制到的数据复制到*p中），将中），将*s的左的左子树链到子树链到*s的双亲结点的双亲结点*q的左（或右）链上。的左（或右）链上。第五十九页，本课件共有100页本节结束！本节结束！第六十页，本课件共有100页3.3 图图3.3.1引言图图是是一一种种重重要要的的，比比树树更更复复杂杂的的非非线线性性数数据据结结构构。在在树树中中，每每个个结结点点只只与与上上层层的的父父结结点点有有联联系系，并并可可以以与与其其下下层层的的多多个个子子结结点点有有联联系系。但但在在图图

28、中中，结结点点之之间间的的联联系系是是任任意意的的，每每个个结结点点都都可可以以与与其其它它的的结结点点相相联联系。系。图图的的应应用用极极为为广广泛泛，特特别别是是近近年年来来发发展展迅迅速速，已已渗渗入入到到诸诸如如语语言言学学、逻逻辑辑学学、物物理理、化化学学、电电信信工工程程、计算机、数学及其它分支中。计算机、数学及其它分支中。第六十一页，本课件共有100页3.3.2图的定义及逻辑结构图的定义及逻辑结构1、图的定义、图的定义图图G由两个集合由两个集合V(G)和和E(G)所组成，记作所组成，记作G=(V,E)。其中，。其中，V(G)是图中顶点的非空有限集合，是图中顶点的非空有限集合，E(

29、G)是图中边的有限集合。是图中边的有限集合。有向图有向图。如果图中每条边都是顶点的有序对，即每条边都用。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括尖括号号括起一对顶点表示。括起一对顶点表示。无向图无向图。如果图中每条边都是顶点的无序对，则称此图。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用为无向图。无向边用圆括号圆括号括起的两个相关顶点来表示。括起的两个相关顶点来表示。第六十二页，本课件共有100页图图G1的顶点集合为：的顶点集合为：V(G1)=V1,V2,V3,

30、V4边集合为：边集合为：E(G1)=(V1,V2),(V1,V3),(V1,V4),(V2,V4),(V3,V4)第六十三页，本课件共有100页图图G2的顶点集合为：的顶点集合为：V(G2)=V1,V2,V3边集合为：边集合为：E(G2)=,第六十四页，本课件共有100页2、图的有关术语、图的有关术语邻邻接接：在在无无向向图图中中，若若边边(x,x,y)y)E E，则则x x、y y互互为为邻邻接接点点；在在有有向向图图中中，若若弧弧 y E E，则则y y是是x x的邻接点。的邻接点。度：度：VxVyx、y互为邻接点互为邻接点VxVyy是是x的邻接点的邻接点第六十五页，本课件共有100页度：

31、度：无向图中无向图中:顶顶点点的的度度是是连连接接该该顶顶点点的的边边的的条条数数。例如，例如，G1中中V2的度为的度为3，V4的度为的度为1。有向图中有向图中:入度入度:以某顶点为弧头的弧的数目以某顶点为弧头的弧的数目G2中顶点中顶点1的入度为的入度为1。出出度度:以以某某顶顶点点为为弧弧尾尾的的弧弧的的数数目目。顶点顶点1的出度为的出度为2。顶顶点点的的度度=入入度度+出出度度。顶顶点点1的的度度=2+1=3。213G24oooov1v2v3v4G1第六十六页，本课件共有100页子图子图有两个图有两个图G=(V,E)和和图图G=(V,E),若若V V且且E E,则称图则称图G为为G的子图的

32、子图。第六十七页，本课件共有100页路径路径图中从顶点图中从顶点Vx到顶点到顶点Vy的顶的顶点序列称为从点序列称为从Vx到到Vy的路径的路径,路径可能是不唯一的。路径可能是不唯一的。例如例如:G1中中V1到到V3的路径为的路径为:(V1V2V3)或或(V1V3);G2中，中，1到到4的路径为的路径为。oooov1v2v3v4G1213G24第六十八页，本课件共有100页路径的长度路径的长度路径上边或弧的数目。路径上边或弧的数目。例例如如，G1中中V1到到V3的的长度为长度为1或或2；G2中中1到到4的长度为的长度为2。oooov1v2v3v4G1213G24第六十九页，本课件共有100页连通图

33、连通图在无向图在无向图G中，若从顶中，若从顶点点V到顶点到顶点V有路径，则称有路径，则称V和和V是连通的。是连通的。无向图中任意两个顶点无向图中任意两个顶点都连通，则称都连通，则称G是连通图。是连通图。第七十页，本课件共有100页强连通图强连通图有向图每对顶点之间都存在路径有向图每对顶点之间都存在路径第七十一页，本课件共有100页完全无向图完全无向图若一个具有若一个具有n个顶个顶点的无向图共有点的无向图共有n(n-1)/2条边，即每一对顶条边，即每一对顶点之间都有边相连，点之间都有边相连，则称其为完全无向图则称其为完全无向图完全有向图完全有向图若一个具有若一个具有n个顶个顶点的无向图共有点的无

34、向图共有n(n-1)条边，即每一对顶点条边，即每一对顶点之间都有两条方向不之间都有两条方向不同的边相连，则称其同的边相连，则称其为完全有向图为完全有向图第七十二页，本课件共有100页网：网：边或弧上带有权值的图边或弧上带有权值的图权值是与边或弧有关的书，可以表示从一个顶点权值是与边或弧有关的书，可以表示从一个顶点到另一定点的距离或耗费等。到另一定点的距离或耗费等。第七十三页，本课件共有100页3.3.3 图的存储结构图的存储结构图图的的结结构构比比较较复复杂杂，存存储储的的方方法法也也很很多多，需需要要根根据据具具体体的的图图形形和和将将来来所所要要做做的的运运算算选选取取适适当当的的存存储储

35、结结构构。这这里里只只讨讨论论两两种种最最常常用用的的表表示示方方法法：邻邻接接矩矩阵阵表表示示法法和和邻接表邻接表表示法。表示法。第七十四页，本课件共有100页 1、顺序存序存储结构构 邻接矩阵：邻接矩阵：可用一个一维数组存放图中所有顶点的信息；可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集即边或弧的集合合E)。这个二维数组称之为邻接矩阵。这个二维数组称之为邻接矩阵。邻邻接接矩矩阵阵是是表表示示顶顶点点之之间间的的邻邻接接关关系系的的矩矩阵阵。设设G=(V，E)是是有有n(n1)个个顶顶点点的的图

36、图，则则G的的邻邻接接矩矩阵阵A是是一一个个具具有有下下列列性性质的质的nn阶矩阵阶矩阵第七十五页，本课件共有100页无向图邻接矩阵无向图邻接矩阵定义定义:设图设图G=(V,E)是有是有n(n 1)个顶点的图，则个顶点的图，则G的的邻接矩阵是具有下述性质的对称阵：邻接矩阵是具有下述性质的对称阵：1(Vi，Vj）EAij=Aji=0(Vi，Vj）EG1的邻接矩阵为：的邻接矩阵为：oooov1v3v4G1A=G.edge=01101011110001004x4G.nodes=1234第七十六页，本课件共有100页有向图邻接矩阵有向图邻接矩阵定义定义:设图设图G=（V，E）是有）是有n（n 1）个顶

37、点的图，则）个顶点的图，则G的的邻接矩阵是具有下述性质的邻接矩阵是具有下述性质的nxn的方阵：的方阵：1Vi，Vj EAij=0Vi，Vj E例如，例如，G2的邻接矩阵为：的邻接矩阵为：G.nodes=1234A=G.Arc=01100000000110004x41324G2第七十七页，本课件共有100页借助于邻接矩阵，可以很容易地求出图中顶点的度。借助于邻接矩阵，可以很容易地求出图中顶点的度。从上例可以很容易看出，邻接矩阵有如下结论：从上例可以很容易看出，邻接矩阵有如下结论：(1)无无向向图图的的邻邻接接矩矩阵阵是是对对称称的的，而而有有向向图图的的邻邻接接矩矩阵阵不不一一定定对对称称。对对

38、无无向向图图可可考考虑虑只只存存下下三三角角(或或上上三三角角)元素。元素。(2)对对于于无无向向图图，邻邻接接矩矩阵阵第第i行行(或或第第i列列)的的元元素素之之和和是顶点是顶点Vi的度。的度。(3)对对于于有有向向图图，邻邻接接矩矩阵阵第第i行行元元素素之之和和为为顶顶点点Vi的的出度；第出度；第i列的元素之和为顶点列的元素之和为顶点Vi的入度。的入度。第七十八页，本课件共有100页 2、链式存式存储结构构图图的的链链式式存存储储结结构构是是通通过过为为每每一一个个顶顶点点建建立立一一个个相相应应的的单单链链表表来来实实现现的的，这这种种存存储储结结构构被被称称为为邻邻接链表接链表。邻邻接

39、接链链表表是是一一种种顺顺序序分分配配和和链链式式分分配配相相结结合合的的存存储储结结构构。它它包包括括两两个个部部分分：一一部部分分是是链链表表；另另一一部分是向量。部分是向量。第七十九页，本课件共有100页在邻接表中，对图中每个顶点建立一个单链表，第在邻接表中，对图中每个顶点建立一个单链表，第i个个单链表中的结点包含了顶点单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个的所有邻接顶点。每个结点由三个域组成：域组成：adjvex、data和和nextarc，如下图所示。，如下图所示。第八十页，本课件共有100页为为便便于于邻邻接接表表操操作作，在在每每个个单单链链表表上上附附设设一

40、一个个头头结结点点，在在头头结结点点中中有有两两个个域域：vexdata和和firstarc。如如下下图图所示。所示。第八十一页，本课件共有100页第八十二页，本课件共有100页图的邻接链表数据类型定义如下：图的邻接链表数据类型定义如下：structadjnodeintadjv;structadjnode*next;structvernodecharver;structadjnode*first;adjlistN+1;第八十三页，本课件共有100页有向图建立邻接链表的算法有向图建立邻接链表的算法structvernodegN+1voidcreatadjlist()inti,j,k;adjnod

41、e*s;for(i=1;i=N;i+)gi.ver=getchar();gi.first=NULL;for(k=1;kadjv=j;s-next=gi.first;gi.first=s;第八十四页，本课件共有100页对对一一个个图图来来说说，邻邻接接链链表表不不是是惟惟一一的的，它它取取决决于于建建立立邻邻接接链链表表时时，结结点点在在每每个个单单链链表表中中的的插插入入策策略略。另另外外，对对于于有有向向图图，其其邻邻接接链链表表中中第第i个个单单链链表表的的结结点点个个数数就就是是此此结结点点的的出出度度；对对于于无无向向图图，其其邻邻接接表表中中第第i个个单链表的结点个数就是此结点的度。

42、单链表的结点个数就是此结点的度。第八十五页，本课件共有100页3.3.4 图图 的的 遍遍 历历图图的的遍遍历历(traversinggraph)是是指指从从图图中中某某一一顶顶点点出出发发，沿沿着着一一定定的的搜搜索索路路径径，对对图图中中各各个个顶顶点点进进行行访访问问，使使每每个个顶顶点点都都被被访访问问且且仅仅被被访访问问一一次次。图图的的遍遍历历算算法法是是求求解解图图的的连连通通性性问问题题、拓拓扑扑排排序序和和求求关关键键路路径径等等算算法的基础。法的基础。第八十六页，本课件共有100页然然而而，图图的的遍遍历历要要比比树树的的遍遍历历复复杂杂得得多多，因因为为图图中中任任一一顶

43、顶点点都都可可能能和和其其余余的的顶顶点点相相邻邻接接，所所以以在在访访问问了了某某个个顶顶点点之之后后，可可能能沿沿着着某某条条路路径径搜搜索索之之后后，又又回回到到该该顶顶点点上上。为为避避免免同同一一顶顶点点被被访访问问多多次次，在在遍遍历历图图的的过过程程中中，必必须须记记下下每每个个已已访访问问过过的的顶顶点点。为为此此，设设一一个个辅辅助助数数组组visitedn，它它的的初初值值为为“假假”或或者者零零，一一旦旦访访问问了了顶顶点点Vi，便便置置visitedi为为“真真”或或者者为为被被访访问问时的次序号。时的次序号。通常有两种遍历图的方法，通常有两种遍历图的方法，深度优先搜索

44、深度优先搜索和和广度广度优先搜索优先搜索。第八十七页，本课件共有100页 1深度优先搜索深度优先搜索图图的的深深度度优优先先搜搜索索遍遍历历(depth-firstsearch)类类似似于于树树的先序遍历，是树的先序遍历的推广。的先序遍历，是树的先序遍历的推广。特点：遍历时尽可能向纵深的方向搜索。特点：遍历时尽可能向纵深的方向搜索。步骤（从步骤（从Vi出发）出发）1)访访问问Vi，并并将将其其对对应应的的访访问问标标志志为为visitedi置置为为1；2)搜索出搜索出Vi的一个未访问过的邻接点的一个未访问过的邻接点Vj。3)从从Vj出出发发，按按以以上上步步骤骤继继续续进进行行深深度度优优先先

45、搜搜索索，直到所有顶点均访问完毕。直到所有顶点均访问完毕。第八十八页，本课件共有100页显显然然，这这个个遍遍历历过过程程是是个个递递归归过过程程。在在设设计计具具体体算算法法时时，首首先先要要确确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。例例连连通通图图G6的的邻邻接接表表表表示示如如下下图图所所示示，以以顶顶点点V1为为始始点点，按按深深度度优先搜索遍历图中所有顶点，写出顶点的遍历序列。优先搜索遍历图中所有顶点，写出顶点的遍历序列。第八十九页，本课件共有100页解：解：先访问先访问V1，再访问与，再访问与V1邻接的邻接的V2

46、，再访问，再访问V2的的第一个邻接点，因第一个邻接点，因V1已被访问过，则访问已被访问过，则访问V2的下一个的下一个邻接点邻接点V4，然后依次访问，然后依次访问V8，V5。这时，与。这时，与V5相邻接相邻接的顶点均已被访问，于是反向回到的顶点均已被访问，于是反向回到V8去访问与去访问与V8相邻相邻接且尚未被访问的接且尚未被访问的V6，接着访问，接着访问V3，V7，至此，全部，至此，全部顶点均被访问。相应的访问序列为：顶点均被访问。相应的访问序列为：V1V2V4V8V5V6V3V7。第九十页，本课件共有100页深度优先搜索的递归算法（邻接矩阵存储结构）#defineNULL0intgN+1N+1

47、;charverN+1;intvisitedN+1;voiddfsm(i)inti;intj;printf(“%c”,veri);visitedi=1;for(j=1;jadjv)dfsa(p-adjv);p=p-next;深度优先搜索的递归算法（邻接链表存储结构）深度优先搜索的递归算法（邻接链表存储结构）第九十二页，本课件共有100页 2广度优先搜索广度优先搜索广广度度优优先先搜搜索索(breadth-firstsearch)类类似似于于树树的的按按层层次遍历的过程。次遍历的过程。假假设设从从图图中中某某顶顶点点V0出出发发，在在访访问问了了V0之之后后依依次次访访问问V0的的各各个个未未曾

48、曾被被访访问问过过的的邻邻接接点点，然然后后分分别别从从这这些些邻邻接接点点出出发发广广度度优优先先搜搜索索遍遍历历图图，直直至至图图中中所所有有已已被被访访问问的的顶顶点点的的邻邻接接点点都都被被访访问问到到。若若此此时时图图中中尚尚有有顶顶点点未未被被访访问问，则则另另选选图图中中一一个个未未曾曾被被访访问问的的顶顶点点作作起起始始点点，重重复复上上述述过过程程，直直至至图图中中所所有有顶顶点点都都被被访访问问到到为止。为止。第九十三页，本课件共有100页具体遍历步骤如下：具体遍历步骤如下：(1)访问访问V0。(2)从从V0出出发发，依依次次访访问问V0的的未未被被访访问问过过的的邻邻接接

49、点点W1，W2，Wt。然然后后依依次次从从W1，W2，Wt出出发发，访问各自未被访问过的邻接点。访问各自未被访问过的邻接点。(3)重重复复步步骤骤(2)，直直到到所所有有顶顶点点的的邻邻接接点点均均被被访访问问过过为止。为止。第九十四页，本课件共有100页例例对连通图对连通图G6，从顶点，从顶点V1出发，写出顶点的广度优先遍历序列。出发，写出顶点的广度优先遍历序列。解解：按按广广度度优优先先搜搜索索法法从从V1开开始始遍遍历历，访访问问V1，然然后后访访问问V1的的邻邻接接点点V2，V3，再再依依次次访访问问V2和和V3的的未未曾曾被被访访问问的的邻邻接接点点V4，V5及及V6，V7，最后访问

50、，最后访问V4的邻接点的邻接点V8。遍历序列如下：。遍历序列如下：V1V2V3V4V5V6V7V8第九十五页，本课件共有100页intgN+1N+1;charverN+1;intvisitedN+1;voidbfsm(i)inti;intj;intqN+1,front,rear;setnull(q,front,rear);printf(“%c”,veri);visitedi=1;enqueue(q,i,front,rear);while(!empty(q,front,rear)i=dequeue(q,front,rear)for(j=1;jadjv)print(“%c”,gp-adjv.ver