软件技术基础课件.ppt

1、1,非线性结构,2,非线性结构,非线性结构：至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数据结构。非线性结构主要有树(TREE)结构图(GRAPH)结构,3,树,4,树型结构,树形结构例：用于描述层次结构的关系，如：人类的族谱、各种社会关系、各类分类编码；操作系统的文件系统、编译程序的语法树；Internet中的DNS（域名系统）分等级的分类方案均可用层次结构来表示，即可由此导出树形结构。,5,树的定义,树(Tree)是n(n0)个结点的有限集合T，对于任意一棵非空树，它满足：当n0时，称为空树；当n0时，有且仅有一个特定的称为根(root)的结点。当n1时，其余结点可分

2、为m(m0)个互不相交的有限集T1，T2，.，Tm，其中每个集合本身又是一棵树，称为根的子树。树的定义是一个递归定义。,6,树的定义,由11个结点集合T组成的树，T=A,B,C,D,E,F,G,H,I,J,K，其中结点A是根结点，除结点A外，其余结点分成3个互不相交的集合T1=B,E,F,G，T2=C，T3=D,H,I,J,K，形成了以结点A为树根的3棵子树T1、T2、T3。而这三棵子树本身又是一棵树。,例如子树T3的根结点是D，其余又分成3个互不相交的集合T31=H，T32=I，T33=J,K，形成了以结点D为树根的3棵子树T31，T32，T33。而T31、T32为只有一个根结点的树。,7,

3、树的基本术语,第1层,第2层,第3层,第4层,8,树的基本术语,结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子(child)结点父(parent)结点,兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree),见书p48,9,基本术语,树中每个结点的分支数称为结点的度。树的度是树中结点的最大度数。度为零的结点为叶结点(Leaf)，称度不为的零结点为分支结点。树中结点的子树的根结点称为该结点的子结点。相反，称该结点为子结点的父结点。,10,基本术语,一个结点的

4、直接后继结点是兄弟结点，他们拥有相同的父结点。祖先结点是从根结点达到某结点所经过分支上的所有结点称为该结点的祖先。子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。,11,基本术语,树中结点的层次(Level)从根结点开始，根为一层结点，其子结点为二层结点，依次类推。叶子结点为最下层结点。这种分层的好处是树中结点的最大层数称为该树的高度（深度）。森林(Forest)是m(m0)棵互不相交的树的集合(可以看成是把一棵树的根结点去掉，所得到的子树构成森林)。如果树中每个结点的子结点规定从左到右是有次序的（不许随意改动），那么，称该树为有序树。否则称为无序树。,12,树的性质一,树中结点总数

5、等于树中所有结点的度之和加1。所谓结点的度是指结点拥有的子树个数。根据树的定义知：在一棵树中，除根结点之外，每个结点有且仅有一个父结点，即每个结点与指向它的一个分支结点一一对应。因而，除树的根结点外的结点数等于树中所有结点的分支数（度数）。由此可知：树中的结点总数应为所有结点的度之和加1。,13,树的性质二,度为k的树的第i层最多有ki-1个结点（i1)。(用数学归纳法)：所谓树的度是指树内各结点的度的最大值。当i=1时，在树中的第一层只有一个结点（根结点），结论正确。设：对于第i-1层（i1)命题也成立，即度为k的树的第i-1层最多有k(i-1)-1=ki-2个结点。由树的度的定义知：度为k

6、的树中每个结点最多有k个子结点，因此：第i层上结点总数最多为第i-1层上结点数的k倍，即第i层上最多有k*ki-2=ki-1个结点，与命题相符。故：度为k的树的第i层最多有ki-1个结点(i1)。,14,树的性质三,深度为h的k叉树最多有个结点,只有当深度为h的k叉树（即该树的度为k）上每一层都达到该层最多结点总数时，该树的结点总数将达到最大，因而有：,15,树的性质四,具有n个结点的k叉树的最小深度为不小于的最小整数。具有n个结点的k叉树的深度为h，若该树的前h-1层都是满的，即每一层的结点数都为ki-1个（1ih-1），第h层（最后一层）的结点数可能满，也可能不满，则该树具有最小的深度。由

7、性质三知：,即：kh-1n(k-1)+1kh,16,树的性质四,取以k为底的对数后得：h-1logk(n(k-1)+1)h,17,树的表示,树型表示,凹入表表示,这是最流行的表示方法,18,树的表示,嵌套集合表示,嵌套括号表示,a(b(d,e(i,j),f),c(g,h),19,树的基本操作,初始化求指定结点所在树的根结点求指定结点的父结点求指定结点的某一孩子结点求指定结点的最右边兄弟结点将一棵树插入到另一树的指定结点下作为它的子树删除指定结点的某一子树树的遍历,20,树的存储结构,通常采用链式存储结构,data部分存放结点的值；pointers是结点的指针部分，它可以由若干个指针所组成。指针

8、的个数与结点的度有关。,21,几种常见的树的存储结构,子结点表示法标准存储结构形式指针数=结点的度/树的度由于树的度不定，实现起来较困难或造成空间浪费。,22,几种常见的树的存储结构,父结点表示法除根结点没有父结点外，其余结点都有唯一的一个父结点包含一个结点信息域和一个指向该结点父结点的指针域求某一结点的子结点比较困难,23,几种常见的树的存储结构,子结点兄弟结点表示法该结点的信息域指向该结点子结点的指针域指向下一个兄弟结点的指针域,24,二叉树,二叉树是每个结点至多有两个子结点的一种树。其中两个子结点分别被称为左子结点和右子结点。而以左子结点为根的子树称为左子树，以右子结点为根的子树称为右子

9、树。定义：由n(n=0)个结点组成的有限集合，它或为空树（n=0），或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。,25,二叉树,二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分(有序树)。二叉树不是树的特殊情形，尽管树和二叉树的概念之间有许多类似，但它们是两个概念。树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。,26,二叉树的五种形态：,左右子树非空的二叉树,只有一个根结点的二叉树,只有左子树的二叉树,只有右子树的二叉树,空树,27,二叉树的性质,性质1：在

10、二叉树的第i层上至多有2i-1个结(i=1)性质2高度为k的二叉树最多有2k-1个结点。(k1)性质3：在任意一棵二叉树中，度为0,1,2的结点数为分别为n0,n1,n2，则有：n0=n2+1。,28,两个定义,满二叉树是指高度为k且有2k-1个结点的二叉树。特点：每一层上都有含有最大结点数。结点编号：从上到下，从左到右按自然数编号。,完全二叉树高度为k，有n个结点的二叉树是一棵完全二叉树，当且仅当其每个结点都与高度为k的满二叉树中层次编号1n相对应。,29,完全二叉树的特点,除最后一层外，每一层都取最大结点数，最后一层结点都有集中在该层最左边的若干位置。叶结点只可能在层次最大的两层出现。对任

11、一结点，若其右子树的深度为m，则其左子树的深度为m或m+1。,30,完全二叉树的性质,性质四：具有n个结点的完全二叉树的深度不大于log2n+1的最大整数。设深度为k，根据二叉树性质二知：2k-1-1n2k-1，即：2k-1n2k，于是有：k-1log2nkk=log2n+1,31,完全二叉树的性质,性质五：对有n个结点的完全二叉树的结点按层序编号(从上到下，自左到右)对任一结点i（1n），结点i无右子结点。若i为奇数,且i不为1，则其左兄弟为i-1，否则无左兄弟；若i为偶数,且小于n，则其右兄弟为i+1，否则无右兄弟i所在层次为log2(i)+1,32,完全二叉树之例,结点8/9的父结点、左

12、/右子结点、兄弟结点？,33,二叉树的顺序存储,顺序存储结构：将二叉树的所有结点，按一定的顺序存储在一片连续的存储单元中。例如：,34,二叉树的顺序存储,适用于：完全二叉树和满二叉树（对于一般二叉树则浪费存储空间）。一般二叉树：改造成完全二叉树。可能会浪费很多存储空间，单支树就是一个极端情况。,但若要在树中经常插入和删除结点时，由于要大量移动结点，显然在这种情况下即使对完全二叉树和满二叉树采用顺序方式也不可取。,35,二叉树的链式存储二叉链表存储,二叉树的二叉链表的结点需要设立一个数据域和两个指针域，这两个指针域分别指向左右子树。二叉链表的结点的逻辑表示：,36,二叉树的链式存储三叉链表存储,

13、如果再设立一个指针指向父结点，构成三叉链表的结点，三叉链表结点的逻辑表示：,37,二叉树的链式逻辑结构,38,二叉树的链式逻辑结构,39,二叉链表的类型描述,#defineBiTreestructbitreeBitreeelemtypedata;BiTree*LChild,*RChild;,40,二叉链表的创建(p66),statusCreateBiTree(BiTree*T)scanf(,输入序列：ABCDEGF,41,二叉树的基本操作及实现,Initiate(bt)：初始建立二叉树bt，并使bt指向头结点。intInitiate(BiTree*bt)/初始化建立二叉树*bt的头结点if(b

14、t=(BiTNode*)malloc(sizeof(BiTNode)=NULL)return0;bt-lchild=NULL;bt-rchild=NULL;return1;,42,二叉树的基本操作及实现,create(x，lbt，rbt)InsertL(bt，x，parent)DeleteL(bt，parent)见书p5657,43,二叉树的遍历,所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作D，遍历根的左子树记作L，遍历根的右子树记作R。则可能的遍历次序有DLRDRL/LDRRDL/LRDRLD当限制左右子树的访问顺序时，有三种方式：前序/先序

15、遍历：DLR中序遍历：LDR后序遍历：LRD,44,前序遍历,算法描述：若二叉树为空，遍历结束；否则访问根结点；按前序遍历左子树；按前序遍历右子树；,对于左图的二叉树，用前序便历算法得到的输出序列为：+a*bcd/ef,45,前序遍历的递归算法,voidpreorder(BiTree*T)if(T=NULL)return;elsevisit(T);if(T-Lchild!=NULL)preorder(T-LChild);if(T-Lchild!=NULL)preorder(T-LChild);,46,前序遍历的过程,访问-，访问+，/入栈，访问a，*入栈，*出栈，访问*访问b，-入栈，-出栈，

16、访问-，访问c，d入栈，d出栈访问d，/出栈，访问/，访问e，f压栈，f出栈，访问f访问输出序列：-+a*bcd/ef,根据前序遍历的算法，有些结点将被系统压栈、出栈。具体如下：,何时结束？,47,先序遍历的非递归算法,设立一数组为栈。从二叉树根结点开始，沿左子树一直走到末端(左子结点为空)并访问遇到的结点，按顺序将结点压栈。当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右子结点。如此重复，直到栈为空或指针为空。,48,先序遍历的非递归算法,voidpreorder(BiTree*root)BiTree*p,*sMaxSize+1;/s为一栈inttop=0;p=root;while(

17、p!=NULL)|(top0)while(p!=NULL)visit(p);/访问根结点s+top=p;/当前结点压栈p=p-LChild;/走向左子树尽头p=stop-;p=p-Rchild;/转向右子树,49,中序遍历,算法描述：若二叉树为空，遍历结束；否则按中序遍历左子树；访问根结点；按中序遍历右子树；,对于左图的二叉树，用中序便历算法得到的输出序列为：a+b*cde/f,50,中序遍历的递归算法,voidpreorder(BiTree*T)if(T=NULL)return;elseif(T-Lchild!=NULL)preorder(T-LChild);visit(T);if(T-Lc

18、hild!=NULL)preorder(T-LChild);,51,中序遍历的非递归算法,中序遍历的递规算法中仍然有系统压栈出现，如果我们将这个过程在程序中描述出来，就是中序遍历的非递归算法。中序遍历的非递归算法设立一数组为栈。从二叉树的根结点开始，沿左子树一直走到末端(左子结点为空)按顺序将结点压栈。若左子树为空，从栈顶退出某结点，访问退出的结点，将指针指向该结点的右子结点。如此重复，直到栈为空或指针为空。,52,中序遍历的非递归算法,voidinorder(BiTree*T)BiTree*p,*sMaxsize+1;inttop=0;p=root;while(p!=NULL)|(top0)

19、while(p!=NULL)/走到左子树尽头s+top=p;p=p-LChild;p=stop-;visit(p);/访问根结点p=p-Rchild;/指向右子树,53,后序遍历,算法描述：若二叉树为空，遍历结束；否则按后序遍历左子树；按后序遍历右子树；访问根结点；,对于左图的二叉树，用后序便历算法得到的输出序列为：abcd-*+ef/-,54,后序遍历的递归算法,voidpreorder(BiTree*T)if(T=NULL)return;elseif(T-Lchild!=NULL)preorder(T-LChild);if(T-Lchild!=NULL)preorder(T-LChild)

20、;visit(T);,55,三种遍历输出序列的特点,前序：输出的第一个结点是树的根结点。中序：根结点在输出序列中间的某个位置，在它的左边的序列全部是左子树的结点，在它右边的序列全部是右子树的结点。后序：最后一个输出的结点是根结点。推想：有了根结点再加上中序序列，就可以区分左子树和右子树。,56,二叉树的其它常见运算,在二叉树中查找具有给定值的结点BiTreefindnode(BiTree*bt,elemtypex)if(bt=NULL)return(NULL);elseif(bt-data=x)return(bt);elsereturn(findnode(bt-LChild)|findnode

21、(bt-RChild);,57,二叉树的其它常见运算,求二叉树的深度inttreehigh(BiTree*boot)inth,h1,h2;BiTree*pp=boot;if(t=NULL)h=0;elseh1=treehigh(t-lchild);h2=treehigh(t-rchild);if(h1=h2)h=h1+1;elseh=h2+1；returnh;,58,由遍历序列重构二叉树,可重构二叉树的结点序列组合：先序序列和中序序列中序序列和后序序列不可重构二叉树的结点序列组合：先序序列和后序序列,59,由结点序列恢复二叉树,由先序序列和中序序列恢复二叉树：由先序序列得到二叉树的根结点；由上

22、述(1)的根结点把中序序列分为左子树的中序序列和右子树的中序序列两个部分；根据上述左子树的中序序列个数找到对应的左子树先序序列和右子树的先序序列；按上述(1)、(2)、(3)同样的方法依次类推，直到所得左、右子树只含一个结点为止。,60,由先序序列ABCDEFGH和中序序列CBEDAGHF重构二叉树，方法如下：先序序列：ABCDEFGH（注：A是根）中序序列：CBEDAGHF,二叉树重构示例,左子树,右子树,A,BCDE,FGH,以A为根的左、右子树先序序列示意图,61,二叉树重构示例,由左子树先序序列：BCDE和左子树中序序列：CBED构造A的左子树同理，由右子树先序序列：FGH和右子树中序

23、序列GHF构造A的右子树：,A,B,F,C,DE,GH,A,B,F,C,D,E,G,H,62,二叉树重构的讨论,如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。例如：前序序列：1，2，3，4，5，6，7，8，9中序序列a：3，2，5，4，1，6，8，7，9中序序列b：4，3，5，2，1，7，6，8，9,63,二叉树重构的讨论,例如，有3个数据1,2,3，可得5种不同的二叉树。它们的前序排列均为123，中序序列可能是123，132，213，231，321。,64,二叉排序树,定义：二叉排序树或者是空树，或者是具有如下性质的二叉树：左子树上所有结点关键字均小于根结点的关键字；右子树上

24、所有结点关键字均大于根结点的关键字。二叉排序树的重要性质：二叉排序树按中序遍历所得到的中序序列是一个递增有序列。,65,二叉排序树的构建,对于给定的序列k1,k2,kn(1)读取k1作为根结点。(2)读取k2，当k2k1时，k2进入的k1右子树。(3)读取ki，不断地比较根结点/子树根结点，直到kikj且kj的右子树为空，插入到kj右子树。,66,树转换成二叉树,三步：连线：在兄弟结点之间加一连线；抹线：保留父结点和第一个子结点的连线，抹去与其它子结点的连线；旋转：以第一子结点为中心，顺时针旋转45度角。,A,B,F,C,D,E,G,A,B,F,C,D,E,G,A,B,F,C,D,E,G,A,

25、B,F,C,D,E,G,连线,抹线,旋转,67,森林转换成二叉树,步骤：将每一棵树转换成二叉树将所有二叉树的根结点之间连线，并以第一棵树的根结点为根结点，旋转。,68,二叉树转换成森林,69,图,70,图的概念和术语,图：图中结点之间的关系是任意的，图中任意两个数据元素之间都可能相关。图：G=(V，E)顶点V(G)-图中的结点/顶点的非空有穷集合边E(G)-边的有穷集合/相关顶点的偶对图中的数据元素vi称为顶点(vertex)；顶点vi和顶点vj之间有一条直接连线用P(vi,vj)表示，称为边(Edge)或者弧(Arc)。边用顶点的无序偶对(vi,vj)来表示弧用顶点的有序偶对来表示,71,图

26、的概念和术语,无向图：任意两个顶点构成的偶对(vi,vj)E是无序的，即顶点之间的连线没有方向。无向图中两个顶点之间的连线称为边边用顶点的无序偶对(vi,vj)来表示，称顶点vi和顶点vj互为邻接点有向图：图中的边是顶点的有序对弧用顶点的有序偶对来表示，称顶点Vj是Vi的邻接点有序偶对的第一个结点vi被称为始点(或弧尾)，在图中就是不带箭头的一端；Vj称为终点，就是图中的箭头部分。,72,图的概念和术语,1,2,4,3,V1,V4,V2,V3,无向图,有向图,73,图的概念和术语,图的一些约定：不考虑顶点到其自身的边，也不允许一条边在图中重复出现（即若(Vi，Vj)或是E(G)中的一条边，则要

27、求ViVj）设图G的顶点数为n，边数为e，则有如下性质：无向图：最多有n(n-1)/2条边，即：0en(n-1)/2有向图：最多有n(n-1)条边，即：0en(n-1),74,图的概念和术语,完全图：任意一对顶点间均有边相连，具有最大边数。无向完全图：有n(n-1)/2条边的无向图。有向完全图：有n(n-1)条边的有向图。邻接点有向图：当E，则称Vj是Vi邻接点，但Vi不一定是Vj邻接点。无向图：当(Vi,Vj)E，则称Vi和Vj互为邻接点。,75,图的概念和术语,顶点(V)的度：无向图：与顶点(V)相连的边的数目，记为TD(V)。有向图：出度OD(V)：在有向图中，把以顶点V为尾的弧的数目称

28、为顶点V的出度。发出弧的数目。入度ID(V)：在有向图中，把以顶点V为头的弧的数目称为顶点V的入度。接收弧的数目。顶点的度TD(V)=OD(V)+ID(V)性质：设G有n个顶点，e条边或弧，则:,76,图的概念和术语,子图：设G=(V，E)是一个图，若V是V的子集，E是E的子集，且E中的边所关联的顶点均在V中，则：G=(V，E)是G=(V，E)子图。,1,2,3,V1,V3,V2,图G,图G（图G的子图）,1,2,4,3,V1,V4,V2,V3,77,图的概念和术语,一条路径：由G中顶点Vi经过若干个顶点总可到达Vj，则称由Vi经过的顶点序列到Vj为Vi到Vj的一条路径。,1,2,4,3,V1

29、,V4,V2,V3,如上图所示：V1-V3-V4是V1到V4的一条路径，同理：V1-V2-V3-V4也是V1到V4的一条路径。,78,图的概念和术语,路径长度：路径上边的数目。简单路径：路径序列中顶点不重复出现的路径称为简单路径。回路(环)：起始顶点和终结顶点可相同的简单路径。例如：下图中的V1-V3-V4、V1-V2-V3-V4、V1-V4均为简单路径。,1,2,4,3,V1,V4,V2,V3,79,图的概念和术语,如上图所示：V1-V3-V4-V1、V1-V2-V3-V4-V1均为环。连通图：图G中任意两个顶点Vi、Vj（ViVj）之间都存在路径，即联通的。带权图(网络)：图中每一条边附加

30、一个数作为权（例如表示从一个顶点到另一个顶点的距离或化费的代价等）。,80,图的概念和术语,生成树。所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。,V1,V3,V4,V5,V2,无向图G1,V1,V3,V4,V5,V2,无向图G1的生成树,81,图的基本操作,(1)CreatGraph(G)(2)DestroyGraph(G)(3)GetVex(G,v)(4)PutVex(G,v,value

31、)(5)InsertVex(G,v)(6)DeleteVex(G,v)(7)InsertArc(G,v,w)见教材讲义P70,82,图的存储结构,分类顺序存储结构-邻接矩阵链式存储结构-邻接表邻接矩阵图有两个部分组成：顶点结合V(G)和边的集合E(G)用一个向量表示顶点集合V(G)用一个二维数组表示边的集合E(G)该二维数组反映了各顶点之间的邻接关系，因而称为邻接矩阵A,83,邻接矩阵,邻接矩阵描述如下对无向图对有向图,84,邻接矩阵示例,85,邻接矩阵的特点,无向图第i行元素之和为该顶点的度矩阵是对称的矩阵中1的个数的一半为图中边的条数有向图第i行元素之和为该顶点的出度第i列元素之和为该顶点

32、的入度矩阵不一定对称矩阵中1的个数为图中弧的条数,86,邻接矩阵的数据类型描述,Constintn=MaxVConstinte=MaxEtypedefstructgraphelemtypevn;intarcsnn;graph;,87,建立无向图的邻接矩阵,voidCreateAdj(graph*g)inti,j,k;for(k=0;kvk);for(i=0;iarcsij=0;for(k=0;karcsij=1;g-arcsji=1;,88,邻接矩阵的插入删除操作,插入无向图g-arcsij=g-arcsji=1;有向图g-arcsij=1;删除无向图g-arcsij=g-arcsji=0;有

33、向图g-arcsij=0;,89,图的链式存储结构邻接表,图的一种链式存储结构。以任何一个顶点为头结点，将它的所有邻接点用单链表来存放每个结点的组成该顶点(Vi)的邻接点权值指向Vi邻接点的指针每个单链表设一个头结点存储顶点的信息指向该顶点的第一个邻接点的指针所有的头结点组成一个一维数组,90,邻接表示例,无向图,2,3,4,1,2,1,3,3,4,1,2,4,1,3,1234,顶点序号,91,邻接表示例,1,3,2,有向图,2,3,1,2,3,3,2,123,顶点序号,92,邻接表的性质,无向图邻接表第i个链表中结点的数目为顶点i的度所有链表中结点数目的一半为图的边数占用了存储单元数为n+2

34、e有向图邻接表第i个链表中结点的数目为顶点i的出度第i个顶点的入度为该顶点在所有链表中出现的次数占用存储单元的数目为n+e,93,邻接表数据类型描述,Constintn=MaxVConstinte=MaxEstructlinkelemtypeadjvex;weighttypedata;structlink*next;StructheadnodeelemtypeV;structlink*next;,94,建立无向图的邻接表,voidCreateLink()inti,j,k;structlink*s;headnodean;for(i=0;iadjvex=j;s-next=ai.next;/头插法建

35、表ai.next=s;,95,建立无向图的邻接表(续),s=(structlink*)malloc(sizof(structlink);s-adjvex=j;s-next=ai.next;ai.next=s;讨论：(1)怎样建立有向图的邻接表？(2)用尾插法建立单链表的方法如何？,96,图的遍历,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助

36、数组visited，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即让visitedi为1，防止它被多次访问。,97,两种遍历方式,深度优先搜索(Depth_FirstSearch)广度优先搜索(Breadth_FirstSearch),98,深度优先搜索(DFS),访问某给定的顶点i,并标识visitedi=1；搜索与顶点i有边相连的下一个顶点j，若j未被访问过，访问它，并标识visitedj=1，然后从j顶点开始按照深度优先算法处理j；若j被访问过，再看与i有边相连的其它顶点；若与顶点i相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才的过程，直到图中所有的顶点都被访问过。,99,例(邻接矩阵实现的图),voiddfs(graph*g,inti)intj;printf(“%d”,g-vi);visitedi=1;for(j=1;jarcsij=1,100,输出序列：12485637过程：dfs(1)dfs(2)dfs(4)dfs(8)dfs(5)dfs(7)dfs(3)dfs(6),过程与结果,101,用邻接表实现的图的DFS算法,voiddfs_link(inti)link*p;printf(“%d”,ai.v