数据结构-第四部分ppt课件

1、第第12章章 图的根本概念图的根本概念 图的定义图的定义 图的术语图的术语 图的运算图的运算 图的存储图的存储 图的遍历图的遍历 图遍历的运用图遍历的运用图的定义图的定义 图可以用图可以用G=(V, E)G=(V, E)表示。其中，表示。其中，V V是顶点的集合，是顶点的集合，E E是衔接顶是衔接顶点的边弧的集合。点的边弧的集合。 假设边是有方向的，称为有向图。有向图的边用假设边是有方向的，称为有向图。有向图的边用表示。表示。表示从表示从A A出发到出发到B B的一条边。在有向图中，的一条边。在有向图中，和和是不一样的。是不一样的。 假设边是无方向的，称为无向图。无向图的边通常用圆括号假设边是

2、无方向的，称为无向图。无向图的边通常用圆括号表示。表示。A A，B B表示顶点表示顶点A A和和B B之间有一条边。无向图也称为之间有一条边。无向图也称为双向图。双向图。 加权图：边被赋予一个权值的图称为加权图。假设图是有向加权图：边被赋予一个权值的图称为加权图。假设图是有向的，称为加权有向图，假设是无向的，称为加权无向图。的，称为加权有向图，假设是无向的，称为加权无向图。 如如G1G1：V = AV = A，B B，C C，DD， E = , , , , E = , , , , , , 表示的图如下所示表示的图如下所示ABCDABCDEV = A，B，C，D，E ，E = A，B， A，C，

3、 B，D， B, E) , D，E， C，E无向图无向图12435661655563421243566165556342加权图中边的表示：加权图中边的表示：或或(Vi, Vj, W)加权图加权图第第12章章 图的根本概念图的根本概念 图的定义图的定义 图的术语图的术语 图的运算图的运算 图的存储图的存储 图的遍历图的遍历 图遍历的运用图遍历的运用图的根本术语图的根本术语 邻接：如邻接：如ViVi，VjVj是图中的一条边，那么称是图中的一条边，那么称ViVi和和VjVj是邻接的。如是邻接的。如ViVj是图中的一条边，是图中的一条边，那么称那么称ViVi邻接到邻接到VjVj，或，或VjVj和和Vi

4、Vi邻接。邻接。 度：无向图中邻接于某一结点的边的总数。度：无向图中邻接于某一结点的边的总数。 入度：有向图中进入某一结点的边数，称为该入度：有向图中进入某一结点的边数，称为该结点的入度结点的入度 出度：有向图中分开某一结点的边数，称为该出度：有向图中分开某一结点的边数，称为该结点的出度结点的出度子图子图AACDACABCD有向图有向图G1的子图的子图ABCD有向图有向图 G1设有两个图设有两个图G=G=V V，E E和和G G= =V V，E E，假设，假设EEVV,那么称那么称G G是是G G的子图的子图无向图无向图 G2ABCDEABDEAABCDABCDE无向图无向图G2的子图的子图途

5、径和途径长度途径和途径长度 对对1iN1iN，结点序列，结点序列w1,w2,wN w1,w2,wN 中的结点对中的结点对wi, wi, wi+1wi+1都有都有wi, wi+1wi, wi+1 E E或或 E E，那么，那么，w1,w2,wNw1,w2,wN是图中的一条途径。是图中的一条途径。 非加权的途径长度就是组成途径的边数，对于途径非加权的途径长度就是组成途径的边数，对于途径w1,w2,wNw1,w2,wN，非加权途径长度为，非加权途径长度为N-1N-1。 加权途径长度是指途径上一切边的权值之和。加权途径长度是指途径上一切边的权值之和。 简单途径和环：假设一条途径上的一切结点，除了简单途

6、径和环：假设一条途径上的一切结点，除了起始结点和终止结点能够一样外，其他的结点都不起始结点和终止结点能够一样外，其他的结点都不一样，那么称其为简单途径。一个回路或环是一条一样，那么称其为简单途径。一个回路或环是一条简单途径，其起始结点和终止结点一样，且途径长简单途径，其起始结点和终止结点一样，且途径长度至少为度至少为1 1。无向图的连通性无向图的连通性 连通：顶点连通：顶点v v至至v v 之间有途径存在之间有途径存在 连通图：无向图连通图：无向图 G G 的恣意两点之间都是的恣意两点之间都是连通的，那么称连通的，那么称 G G 是连通图。是连通图。 连通分量：非连通图中的极大连通子图连通分量

7、：非连通图中的极大连通子图ABCDEFGIJLHMKABCDEHMFGJILK无向图无向图G无向图无向图G的三个连通分量的三个连通分量有向图的连通性有向图的连通性 强连通图：有向图强连通图：有向图 G G 的恣意两点之间都是的恣意两点之间都是连通的，那么称连通的，那么称 G G 是强连通图。是强连通图。 强连通分量：极大连通子图强连通分量：极大连通子图 弱连通图：如有向图弱连通图：如有向图G G不是强连通的，但假不是强连通的，但假设把它看成是无向图时是连通的，那么称设把它看成是无向图时是连通的，那么称该图是弱连通的该图是弱连通的有向图有向图G有向图有向图G G的两个强连通分量的两个强连通分量A

8、BCDABCD不是强连通图。由于不是强连通图。由于B B到其他结点都没有途到其他结点都没有途径。但此图是弱连通径。但此图是弱连通的。的。完全图完全图 完全图：每两个节点之间都有边的无完全图：每两个节点之间都有边的无向图称为完全图。完全图有向图称为完全图。完全图有 n(n-1)/2 n(n-1)/2 条边的无向图。其中条边的无向图。其中 n n 是结点个数。是结点个数。即即 有向完全图：每两个节点之间都有两有向完全图：每两个节点之间都有两条弧的有向图称为有向完全图。有向条弧的有向图称为有向完全图。有向完全图有完全图有 n(n-1) n(n-1) 条边。其中条边。其中 n n 是结是结点个数。即点

9、个数。即 假设一个有向图中没有环，那么称为假设一个有向图中没有环，那么称为有向无环图，简写为有向无环图，简写为DAGDAG2nC22nCABCD无向完全图无向完全图生成树生成树ABCDEHMABCDEHM无向图无向图G 无向图无向图G的生成树的生成树 生成树是连通图的极小连通子图。包含图的一生成树是连通图的极小连通子图。包含图的一切切 n n 个结点，但只含图的个结点，但只含图的 n-1 n-1 条边。在生成条边。在生成树中添加一条边之后，必定会构成回路或环。树中添加一条边之后，必定会构成回路或环。第第12章章 图的根本概念图的根本概念 图的定义图的定义 图的术语图的术语 图的运算图的运算 图

10、的存储图的存储 图的遍历图的遍历 图遍历的运用图遍历的运用图的运算图的运算 常规操作：常规操作： 构造一个由假设干个结点、假设干条边组构造一个由假设干个结点、假设干条边组成的图；成的图； 判别两个结点之间能否有边存在；判别两个结点之间能否有边存在； 在图中添加或删除一条边；在图中添加或删除一条边； 前往图中的结点数或边数；前往图中的结点数或边数； 按某种规那么遍历图中的一切结点。按某种规那么遍历图中的一切结点。 和运用严密结合的运算：和运用严密结合的运算： 拓扑排序拓扑排序 找最小生成树找最小生成树 找最短途径等。找最短途径等。图的笼统类图的笼统类 template class graph p

11、ublic:virtual bool insert(int u, int v, TypeOfEdge w) = 0;virtual bool remove(int u, int v) = 0;virtual bool exist(int u, int v) const = 0;virtual numOfVer() const return Vers;virtual numOfEdge() const return Edges;protected:int Vers, Edges; 第第12章章 图的根本概念图的根本概念 图的定义图的定义 图的术语图的术语 图的运算图的运算 图的存储图的存储 图的

12、遍历图的遍历 图遍历的运用图遍历的运用图的存储图的存储 邻接矩阵和加权邻接矩阵邻接矩阵和加权邻接矩阵 邻接表邻接表邻接矩阵邻接矩阵有向图有向图设有向图具有设有向图具有 n n 个结点，那么用个结点，那么用 n n 行行 n n 列的布尔矩列的布尔矩阵阵 A A 表示该有向图假设表示该有向图假设i i 至至 j j 有一条有向边有一条有向边, , Ai,j = 1 ,Ai,j = 1 ,假设假设 i i 至至 j j 没有一条有向边没有一条有向边,Ai,j ,Ai,j = 0 = 0 ABCD表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0留意：留意： 出度出

13、度: i: i行之和。入度行之和。入度: j: j列之和。列之和。邻接矩阵邻接矩阵有向图有向图ABCD表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0在物理实现时的思索：分别用在物理实现时的思索：分别用 0 0、1 1、2 2、3 3 分别标识结分别标识结点点A A、B B、C C、D D。而将真正的数据字段之值放入一个一维数。而将真正的数据字段之值放入一个一维数组之中。组之中。 0 1 2 30123DABC 0 1 2 3邻接矩阵邻接矩阵无向图无向图设无向图具有设无向图具有 n n 个结点，那么用个结点，那么用 n n 行行 n n 列的布尔矩阵列的布尔

14、矩阵 A A 表示该无向图；并且表示该无向图；并且 Ai,j = 1 , Ai,j = 1 , 假设假设i i 至至 j j 有一条无有一条无向边；向边；Ai,j = 0Ai,j = 0假设假设 i i 至至 j j 没有一条无向边没有一条无向边 表示成右图矩阵表示成右图矩阵0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE在物理实现时的思索，和前一页的无向图类似。在物理实现时的思索，和前一页的无向图类似。留意：留意： 无向图的邻接矩阵是一个对称矩阵无向图的邻接矩阵是一个对称矩阵 i i 结点的度结点的度: i : i 行或行或 i i 列之和

15、。列之和。加权的邻接矩阵加权的邻接矩阵有向图有向图设有向图具有设有向图具有 n n 个结点，那么用个结点，那么用 n n 行行 n n 列的矩阵列的矩阵 A A 表表示该有向图；示该有向图； 假设假设i i 至至 j j 有一条有向边且它的权值为有一条有向边且它的权值为a a ，那么，那么Ai,j = a Ai,j = a 。假设。假设 i i 至至 j j 没有一条有向边。没有一条有向边。那么那么Ai,j = Ai,j = 空空 或其它标志或其它标志表示成右图矩阵表示成右图矩阵 a b b ba a ABCDaaabbb邻接矩阵的特点邻接矩阵的特点 优点：判别恣意两点之间能否有边方便，优点：

16、判别恣意两点之间能否有边方便，仅耗费仅耗费 O(1) O(1) 时间。时间。 缺陷：即使缺陷：即使 n2 n2 条边，也需内存条边，也需内存 n2 n2 单元，太多单元，太多; ; 仅读入数据耗费仅读入数据耗费 O( n2 ) O( n2 ) 时间，太长。而大多数的图的边数远远时间，太长。而大多数的图的边数远远小于小于n2n2。邻接矩阵类的定义邻接矩阵类的定义template class adjMatrixGraph:public graph public: adjMatrixGraph(int vSize, const TypeOfVer d, TypeOfEdge noEdgeFlag);

17、bool insert(int u, int v, TypeOfEdge w);bool remove(int u, int v);bool exist(int u, int v) const;adjMatrixGraph() ；private:TypeOfEdge *edge; /存放邻接矩阵存放邻接矩阵TypeOfVer *ver; /存放结点值存放结点值TypeOfEdge noEdge; /邻接矩阵中的邻接矩阵中的的表示值的表示值;构造函数构造函数template adjMatrixGraph:adjMatrixGraph (int vSize, const TypeOfVer d,

18、TypeOfEdge noEdgeFlag) int i, j; Vers = vSize; Edges = 0; noEdge = noEdgeFlag; /存放结点的数组的初始化存放结点的数组的初始化 ver = new TypeOfVervSize; for (i=0; ivSize;+ i) veri = di; /邻接矩阵的初始化邻接矩阵的初始化 edge = new TypeOfEdge*vSize; for (i=0; ivSize; + i) edgei = new TypeOfEdgevSize; for (j=0; jvSize; +j) edgeij = noEdge;

19、析构函数析构函数template adjMatrixGraph: adjMatrixGraph()delete ver;for (int i=0; iVers; +i) delete edgeidelete edge;Insert函数函数template bool adjMatrixGraph: insert(int u, int v, TypeOfEdge w) if (u Vers - 1 | v Vers -1) return false; if (edgeuv != noEdge) return false; edgeuv = w; +Edges; return true; Remov

20、e函数函数template bool adjMatrixGraph: remove(int u, int v) if (u Vers -1 | v Vers -1) return false; if (edgeuv = noEdge) return false; edgeuv = noEdge; -Edges; return true; Exist函数函数template bool adjMatrixGraph: exist(int u, int v) const if (u Vers -1 | v Vers -1) return false; if (edgeuv = noEdge) ret

21、urn false; else return true; 图的存储图的存储 邻接矩阵和加权邻接矩阵邻接矩阵和加权邻接矩阵 邻接表邻接表邻接表邻接表 设有向图或无向图具有设有向图或无向图具有 n n 个结点，那么用结点表、个结点，那么用结点表、边表表示该有向图或无向图。边表表示该有向图或无向图。 结点表：用数组或单链表的方式存放一切的结点值。结点表：用数组或单链表的方式存放一切的结点值。假设结点数假设结点数n n知，那么采用数组方式，否那么应采知，那么采用数组方式，否那么应采用单链表的方式。用单链表的方式。 边表边结点表：每条边用一个结点进展表示。边表边结点表：每条边用一个结点进展表示。同一个结

22、点出发的一切的边构成它的边结点单链表。同一个结点出发的一切的边构成它的边结点单链表。ABCD无向图无向图 G2ABCDE有向图有向图 G10123 dest linkABCD1203 data adj12 data adj03041423AB01234CDE41 dest link邻接表的特点邻接表的特点 邻接表是图的规范存储方式邻接表是图的规范存储方式 优点：内存优点：内存 结点数结点数 边数，处置时间也是边数，处置时间也是结点数结点数 边数，即为边数，即为O(|V|+|E|)O(|V|+|E|)。 当我们谈及图的线性算法时，普通指的是当我们谈及图的线性算法时，普通指的是O(|V|+|E|)

23、O(|V|+|E|) 缺陷：缺陷： 确定确定 i - j i - j 能否有边，最坏需耗费能否有边，最坏需耗费 O(n) O(n) 时间。时间。 无向图同一条边表示两次。边表空间浪费一倍。无向图同一条边表示两次。边表空间浪费一倍。 有向图中寻觅进入某结点的边，非常困难。有向图中寻觅进入某结点的边，非常困难。邻接表类的定义邻接表类的定义template class adjListGraph:public graph public: adjListGraph(int vSize, const TypeOfVer d);bool insert(int u, int v, TypeOfEdge w);

24、bool remove(int u, int v);bool exist(int u, int v) const;adjListGraph() ;private: struct edgeNode /邻接表中存储边的结点类邻接表中存储边的结点类int end; /终点编号终点编号TypeOfEdge weight; /边的权值边的权值edgeNode *next;edgeNode(int e, TypeOfEdge w, edgeNode *n = NULL) end = e; weight = w; next = n;struct verNode /保管顶点的数据元素类型保管顶点的数据元素类型

25、TypeOfVer ver; /顶点值顶点值edgeNode *head; /对应的单链表的头指针对应的单链表的头指针verNode( edgeNode *h = NULL) head = h ;verNode *verList; 构造函数构造函数template adjListGraph: adjListGraph(int vSize, const TypeOfVer d) Vers = vSize; Edges = 0; verList = new verNodevSize; for (int i = 0; i Vers; +i) verListi.ver = di;析构函数析构函数tem

26、plate adjListGraph:adjListGraph() int i; edgeNode *p; for (i = 0; i next; delete p; delete verList; Insert函数函数template bool adjListGraph: insert(int u, int v, TypeOfEdge w) verListu.head = new edgeNode(v, w, verListu.head ); +Edges; return true;Remove函数函数template bool adjListGraph:remove(int u, int

27、v)edgeNode *p = verListu.head, *q; if (p = NULL) return false; /结点结点u没有相连的边没有相连的边 if (p-end = v) /单链表中的第一个结点就是被删除的边单链表中的第一个结点就是被删除的边 verListu.head = p-next; delete p; -Edges; return true; while (p-next !=NULL & p-next-end != v) p = p-next if (p-next = NULL) return false; /没有找到被删除的边没有找到被删除的边 q =

28、p-next; p-next = q-next; delete q; -Edges; return true;Exist函数函数template bool adjListGraph: exist(int u, int v) const edgeNode *p = verListu.head; while (p !=NULL & p-end != v) p = p-next; if (p = NULL) return false; else return true; 第第12章章 图的根本概念图的根本概念 图的定义图的定义 图的术语图的术语 图的运算图的运算 图的存储图的存储 图的遍历图

29、的遍历 图遍历的运用图遍历的运用邻接矩阵邻接矩阵有向图有向图设有向图具有设有向图具有 n n 个结点，那么用个结点，那么用 n n 行行 n n 列的布尔矩列的布尔矩阵阵 A A 表示该有向图假设表示该有向图假设i i 至至 j j 有一条有向边有一条有向边, , Ai,j = 1 ,Ai,j = 1 ,假设假设 i i 至至 j j 没有一条有向边没有一条有向边,Ai,j ,Ai,j = 0 = 0 ABCD表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0留意：留意： 出度出度: i: i行之和。入度行之和。入度: j: j列之和。列之和。ABCD有向图有

30、向图 G10123 dest linkABCD2103 data adj邻接表邻接表有向图有向图设有向图或无向图具有设有向图或无向图具有 n 个结点，那么用结点表、个结点，那么用结点表、边表表示该有向图或无向图。边表表示该有向图或无向图。5672413邻接表邻接表有向图有向图编号0图的遍历图的遍历 深度优先搜索深度优先搜索 广度优先搜索广度优先搜索对有向图和无向图进展遍历是按照某种次序系统地对有向图和无向图进展遍历是按照某种次序系统地访问图中的一切顶点，并且使得每个顶点只能被访访问图中的一切顶点，并且使得每个顶点只能被访问一次。在图中某个顶点能够和图中的多个顶点邻问一次。在图中某个顶点能够和图

31、中的多个顶点邻接并且存在回路，因此在图中访问一个顶点接并且存在回路，因此在图中访问一个顶点u u之后，之后，在以后的访问过程中，又能够再次前往到顶点在以后的访问过程中，又能够再次前往到顶点u u，所，所以图的遍历要比树的遍历更复杂以图的遍历要比树的遍历更复杂深度优先搜索深度优先搜索1 1、选中第一个被访问的顶点；、选中第一个被访问的顶点；2 2、对顶点作已访问过的标志；、对顶点作已访问过的标志；3 3、依次从顶点的未被访问过的第一个、第、依次从顶点的未被访问过的第一个、第二个、第三个二个、第三个 邻接顶点出发，进展深邻接顶点出发，进展深度优先搜索；度优先搜索；4 4、假设还有顶点未被访问，那么

32、选中一个、假设还有顶点未被访问，那么选中一个起始顶点，转向起始顶点，转向2 2；5 5、一切的顶点都被访问到，那么终了。、一切的顶点都被访问到，那么终了。5672413从结点从结点5开场进展深度优先的开场进展深度优先的搜索，那么遍历序列可以为：搜索，那么遍历序列可以为：5，7，6，2，4，3，1，也可以为：也可以为：5，6，2，3，1，4，7。 深度优先生成树深度优先生成树56723145672314深度优先生成森林深度优先生成森林 在进展深度优先搜索在进展深度优先搜索 DFS DFS 时，有时并不一时，有时并不一定可以保证从某一个结点出发能访问到一切定可以保证从某一个结点出发能访问到一切的顶

33、点的顶点 在这种情况下，必需再选中一个未访问过的在这种情况下，必需再选中一个未访问过的顶点，继续进展深度优先搜索。直至一切的顶点，继续进展深度优先搜索。直至一切的顶点都被访问到为止。顶点都被访问到为止。 这时，得到的是一组树而不是一棵树，这一这时，得到的是一组树而不是一棵树，这一组树被称为深度优先生成森林。组树被称为深度优先生成森林。5672413从结点从结点1开场深度开场深度优先搜索优先搜索 1243567深度优先搜索的实现深度优先搜索的实现 深度优先搜索深度优先搜索DFSDFS的实现方法和树的前序的实现方法和树的前序遍历算法类似，但必需对访问过的顶点加遍历算法类似，但必需对访问过的顶点加以

34、标志以标志 dfsdfs函数不需求参数，也没有前往值。它函数不需求参数，也没有前往值。它从编号最小的结点出发开场搜索，并将对从编号最小的结点出发开场搜索，并将对当前对象的深度优先搜索的序列显示在显当前对象的深度优先搜索的序列显示在显示器上。示器上。深度优先搜索的实现深度优先搜索的实现 以邻接表为例以邻接表为例 设置一个数组设置一个数组visitedvisited，记录节点能否被访问过，记录节点能否被访问过 设计一个私有的深度优先搜索的函数，从某一节设计一个私有的深度优先搜索的函数，从某一节点出发访问一切可达节点点出发访问一切可达节点 假设是无向非连通图的或有向非强连通，那么对假设是无向非连通图

35、的或有向非强连通，那么对图中尚未访问的节点反复调用深度优先搜索，构图中尚未访问的节点反复调用深度优先搜索，构成深度优先搜索的森林。成深度优先搜索的森林。公有的公有的dfs函数函数void dfs( ) 对每个节点对每个节点 v visited v = false; while (v = 尚未访问的节点尚未访问的节点 dfs(v，visited); template void adjListGraph:dfs() constbool *visited = new boolVers; for (int i=0; i Vers; +i) visitedi = false; cout 当前图的深度优先

36、遍历序列为：当前图的深度优先遍历序列为： endl; for (i = 0; i Vers; +i) if (visitedi = true) continue; dfs(i, visited); cout endl; 私有的私有的dfsvoid dfs( v，visited ) visitedv = true; for 每个每个 v的邻接点的邻接点w if( ! Visitedw ) dfs( w,visited );访问从结点访问从结点v出发可以访问到的一切结点出发可以访问到的一切结点 template void adjListGraph:dfs (int start, bool visi

37、ted) const edgeNode *p = verListstart.head; cout verListstart.ver end = false) dfs(p-end, visited); p = p-next; 5672413对图调用对图调用dfs结果为：结果为：当前图的深度优先搜索序列为：当前图的深度优先搜索序列为：1 2 4 37 6即对应于左图的即对应于左图的深度优先生成森林深度优先生成森林1243567时间性能分析时间性能分析 dfsdfs函数将对一切的顶点和边进展访问，函数将对一切的顶点和边进展访问，因此它的时间代价和顶点数因此它的时间代价和顶点数 |V| |V| 及边数

38、及边数 |E| |E| 是相关的，即是是相关的，即是O(|V|+|E|)O(|V|+|E|)。 假设图是用邻接矩阵来表示，那么所需假设图是用邻接矩阵来表示，那么所需求的时间是求的时间是O O|V|2|V|2。图的遍历图的遍历 深度优先搜索深度优先搜索 广度优先搜索广度优先搜索对有向图和无向图进展遍历是按照某种次序系统地对有向图和无向图进展遍历是按照某种次序系统地访问图中的一切顶点，并且使得每个顶点只能被访访问图中的一切顶点，并且使得每个顶点只能被访问一次。在图中某个顶点能够和图中的多个顶点邻问一次。在图中某个顶点能够和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点接并且存在回路，因此在

39、图中访问一个顶点u u之后，之后，在以后的访问过程中，又能够再次前往到顶点在以后的访问过程中，又能够再次前往到顶点u u，所，所以图的遍历要比树的遍历更复杂以图的遍历要比树的遍历更复杂广度优先搜索广度优先搜索 BFS 1 1、选中第一个被访问的顶点；、选中第一个被访问的顶点；2 2、对顶点作已访问过的标志；、对顶点作已访问过的标志；3 3、依次访问已访问顶点的未被访问过的第一个、第、依次访问已访问顶点的未被访问过的第一个、第二个、第三个二个、第三个第第 m m 个邻接顶点个邻接顶点 W1 W1 、W2W2、W3 Wm W3 Wm ，进展访问且进展标志，转向，进展访问且进展标志，转向3 3；4

40、4、假设还有顶点未被访问，那么选中一个起始顶点，、假设还有顶点未被访问，那么选中一个起始顶点，转向转向2 2；5 5、一切的顶点都被访问到，那么终了。、一切的顶点都被访问到，那么终了。 广度优先搜索类似于树的从树根出发的按照层次的遍广度优先搜索类似于树的从树根出发的按照层次的遍历。它的访问方式如下：历。它的访问方式如下：5672413按照顶点序号小的先按照顶点序号小的先访问，序号大的后访访问，序号大的后访问的原那么，那么它问的原那么，那么它的广度优先访问序列的广度优先访问序列为：为：1，2，4，3，5，6，7 。对应的广度优。对应的广度优先生成森林为先生成森林为1243567从不同的结点开场可

41、以得到不同的搜索序列。例如，从不同的结点开场可以得到不同的搜索序列。例如，从从5开场广度优先搜索这个图，得到的遍历序列为：开场广度优先搜索这个图，得到的遍历序列为：5，6，7，2，4，3，1。 56724131243567广度优先搜索的实现广度优先搜索的实现 需求记录每个结点能否已被访问需求记录每个结点能否已被访问 需求记住每个已被访问的结点的后继结点，然后依需求记住每个已被访问的结点的后继结点，然后依次访问这些后继结点。这可以用一个队列来实现次访问这些后继结点。这可以用一个队列来实现 过程：过程： 将序号最小的顶点放入队列将序号最小的顶点放入队列 反复取队列的队头元素进展处置，直到队列为空。

42、反复取队列的队头元素进展处置，直到队列为空。对出队的每个元素，首先检查该元素能否已被访问。对出队的每个元素，首先检查该元素能否已被访问。假设没有被访问过，那么访问该元素，并将它的一假设没有被访问过，那么访问该元素，并将它的一切的没有被访问过的后继入队切的没有被访问过的后继入队 检查能否还有结点未被访问。假设有，反复上述两检查能否还有结点未被访问。假设有，反复上述两个步骤个步骤template void adjListGraph:bfs() const bool *visited = new boolVers; int currentNode; linkQueue q; edgeNode *p;

43、 for (int i=0; i Vers; +i) visitedi = false; cout 当前图的广度优先遍历序列为：当前图的广度优先遍历序列为： endl; for (i = 0; i Vers; +i) if (visitedi = true) continue; q.enQueue(i); while (!q.isEmpty() currentNode = q.deQueue(); if (visitedcurrentNode = true) continue; cout verListcurrentNode.ver end = false) q.enQueue(p-end);

44、 p = p-next; cout 4-3-5，那么此，那么此时，就无法访问其他结点了时，就无法访问其他结点了,由于由于5没有其他的没有其他的尚未被访问的边了。尚未被访问的边了。处理方法处理方法 找出途径上的另外一个尚有未访问的边找出途径上的另外一个尚有未访问的边的顶点，开场另一次深度优先的搜索，的顶点，开场另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，将得到的遍历序列拼接到原来的序列中，直到一切的边都已被访问。直到一切的边都已被访问。012345先找到先找到 5-4-3-5在途径上找一个尚有边未在途径上找一个尚有边未被访问的结点，如：被访问的结点，如：4，开场另一次深度优先遍历。

45、开场另一次深度优先遍历。得到途径得到途径4-2-1-4将第二条途径拼接到第一条途径上，得到：将第二条途径拼接到第一条途径上，得到：5-4-2-1-4-3-53号结点还有未访问的边，从号结点还有未访问的边，从3号结点再开场一次深号结点再开场一次深度优先遍历，得到途径度优先遍历，得到途径3-1-0-2-3将第三条途径拼接到第一条途径上，得到：将第三条途径拼接到第一条途径上，得到：5-4-2-1-4-3-1-0-2-3-5寻觅欧拉回路寻觅欧拉回路 检查存在性检查存在性 找出回路：找出回路： 执行一次深度优先的搜索。从起始结点开执行一次深度优先的搜索。从起始结点开场，沿着这条路不断往下走，直到无路可场

46、，沿着这条路不断往下走，直到无路可走。而且在此过程中不允许回溯。走。而且在此过程中不允许回溯。 途径上能否有一个尚有未访问的边的顶点。途径上能否有一个尚有未访问的边的顶点。假设有，开场另一次深度优先的搜索，将假设有，开场另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直得到的遍历序列拼接到原来的序列中，直到一切的边都已被访问。到一切的边都已被访问。欧拉回路的实现欧拉回路的实现 欧拉回路是由一段一段的途径拼接起来的。为此，欧拉回路是由一段一段的途径拼接起来的。为此，设计了一个私有的成员函数设计了一个私有的成员函数EulerCircuitEulerCircuit来获得一来获得一段途径。公

47、有的段途径。公有的EulerCircuitEulerCircuit函数调用私有的函数调用私有的EulerCircuitEulerCircuit函数获得一段段的途径，并将它们拼函数获得一段段的途径，并将它们拼接起来，构成一条完好的欧拉回路。接起来，构成一条完好的欧拉回路。 为了拼接方便起见，找到的欧拉回路被保管在一个为了拼接方便起见，找到的欧拉回路被保管在一个单链表中，单链表的结点类型为单链表中，单链表的结点类型为EulerNodeEulerNode。 EulerNodeEulerNode保管两个内容：结点的编号和下一结点保管两个内容：结点的编号和下一结点的指针。它被定义为邻接表类的私有的内嵌类

48、。的指针。它被定义为邻接表类的私有的内嵌类。欧拉回路的实现欧拉回路的实现 续续 欧拉回路中，一条边不能走两遍。为此，欧拉回路中，一条边不能走两遍。为此，当一条边被访问以后，就将这条边删除当一条边被访问以后，就将这条边删除 CloneClone函数创建一份邻接表的拷贝，以便函数创建一份邻接表的拷贝，以便在找完途径后能恢复这个图的邻接表在找完途径后能恢复这个图的邻接表公有的公有的EulerCircuitEulerCircuit函数函数template void adjListGraph:EulerCircuit (TypeOfVer start) EulerNode *beg, *end, *p,

49、 *q, *tb, *te; int numOfDegree; edgeNode *r; verNode *tmp; /检查能否存在欧拉回路检查能否存在欧拉回路 for (int i=0; inext; if (numOfDegree =0 | numOfDegree % 2) cout 不存在欧拉回路不存在欧拉回路 endl; return; /寻觅起始结点的编号寻觅起始结点的编号for (i = 0; iVers; +i) if (verListi.ver = start) break;if (i = Vers) cout 起始结点不存在起始结点不存在 next != NULL) if (

50、verListp-next-NodeNum.head != NULL) break; else p = p-next; if (p-next = NULL) break; q = p-next; tb = EulerCircuit(q-NodeNum, te); te-next =q-next; p-next = tb; delete q;/恢复原图恢复原图 delete verList; verList = tmp; /显示得到的欧拉回路显示得到的欧拉回路 cout 欧拉回路是：欧拉回路是： endl; while (beg !=NULL) cout NodeNum.ver next;del

51、ete p; cout endl;欧拉途径中的结点类欧拉途径中的结点类 struct EulerNodeint NodeNum;EulerNode *next;EulerNode(int ver) NodeNum = ver; next =NULL; clone函数的实现函数的实现 template adjListGraph:verNode * adjListGraph:clone( ) const verNode *tmp = new verNodeVers; edgeNode *p; for (int i = 0; i end, p-weight, tmpi.head);p = p-nex

52、t; return tmp; 私有的私有的EulerCircuitEulerCircuit函数函数template adjListGraph:EulerNode *adjListGraph :EulerCircuit(int start, EulerNode *&end)EulerNode *beg; int nextNode; beg = end = new EulerNode(start); while(verListstart.head != NULL) nextNode = verListstart.head-end; remove( start, nextNode); rem

53、ove(nextNode, start); start = nextNode; end-next = new EulerNode(start); end = end-next; return beg;哈密尔顿回路问题哈密尔顿回路问题 该回路经过图的每一个结点一次，且仅该回路经过图的每一个结点一次，且仅经过一次。经过一次。 一个图能否存在哈密尔顿回路至今仍未一个图能否存在哈密尔顿回路至今仍未找到满足该问题的充要条件。找到满足该问题的充要条件。 图遍历的运用图遍历的运用 无向图的连通性无向图的连通性 欧拉回路欧拉回路 有向图的连通性有向图的连通性 拓扑排序拓扑排序 对有向图，深度优先搜索可以测试能

54、否强连通，并对有向图，深度优先搜索可以测试能否强连通，并找出一切强连通分量找出一切强连通分量 找强连通分量的方法找强连通分量的方法 从恣意节点开场深度优先遍历从恣意节点开场深度优先遍历G G。对森林中的每棵树。对森林中的每棵树进展深度优先遍历，并按遍历的顺序给每个节点编进展深度优先遍历，并按遍历的顺序给每个节点编号号 将将G G的每条边逆向，构成的每条边逆向，构成GrGr。从编号最大的节点开场。从编号最大的节点开场深度优先遍历深度优先遍历GrGr。得到的深度优先遍历森林的每棵。得到的深度优先遍历森林的每棵树就是树就是G G的强连通分量。的强连通分量。有向图的连通性有向图的连通性ABDGHCJE

55、IF从从B开场深度优先搜索开场深度优先搜索BEDAFCIHG10J978654321ABDGHCJEIFGrGIHJBACFDE因此，图因此，图G有有5个个强连通分量强连通分量图遍历的运用图遍历的运用 无向图的连通性无向图的连通性 欧拉回路欧拉回路 有向图的连通性有向图的连通性 拓扑排序拓扑排序拓扑排序拓扑排序设设G=G=V V，E E是一个具有是一个具有n n个顶点的有向无个顶点的有向无环图。环图。V V中的顶点序列中的顶点序列V1V1，V2V2，VnVn称为称为一个拓扑序列，当且仅当该序列满足以下一个拓扑序列，当且仅当该序列满足以下条件：假设在条件：假设在G G中，从中，从ViVi到到Vj

56、Vj有一条途径，有一条途径，那么序列中那么序列中ViVi必需排在必需排在VjVj的前面。的前面。下述集合下述集合 M M 代表课程的集合代表课程的集合1 1 代表数学，代表数学， 2 2 代表程序设计，代表程序设计，3 3 代表离散数学，代表离散数学，4 4 代表汇编程序设计，代表汇编程序设计，5 5 代表数据构造，代表数据构造，6 6 代表构造化程序设计代表构造化程序设计, ,7 7 代表编译原理代表编译原理关系关系R R表示课程学习的先后关系，如数学必需在离表示课程学习的先后关系，如数学必需在离散数学之前学习。要求排一张学习的先后次序表。散数学之前学习。要求排一张学习的先后次序表。拓扑排序

57、的运用拓扑排序的运用1327564数学数学程序设计程序设计离散数学离散数学汇编程汇编程序设计序设计数据构造数据构造构造化程序设计构造化程序设计编译原理编译原理用有向图表示关系用有向图表示关系R R。节点集为课程。节点集为课程集合。假设课程集合。假设课程i i和和j j有关系有关系R R，那么，那么有一条边。有一条边。可行的排课：可行的排课：方案方案1： 1，2，3，4，5，6，7方案方案2： 1，2，3，5，6，4，7方案方案3： 1，2，3，5，6，7，4。1327564数学数学程序设计程序设计离散数学离散数学汇编程序汇编程序设计设计数据构造数据构造构造化程序设计构造化程序设计编译原理编译原

58、理找出拓扑排序的过程找出拓扑排序的过程 第一个输出的结点序列中的第一个元素：第一个输出的结点序列中的第一个元素： 必需无前驱，即入度为必需无前驱，即入度为0 0 后驱：必需等到它的前驱输出之后才输出。后驱：必需等到它的前驱输出之后才输出。 无前驱及后件的结点：任何时候都可输出。无前驱及后件的结点：任何时候都可输出。 逻辑删除法：当某个节点被输出后，就作为逻辑删除法：当某个节点被输出后，就作为该节点被删除。一切以该节点作为前驱的一该节点被删除。一切以该节点作为前驱的一切节点的入度减切节点的入度减1 1。1327564数学数学0程序设计程序设计1离散数学离散数学1汇编程序汇编程序设计设计1数据构造

59、数据构造2构造化程序设计构造化程序设计1编译原理编译原理30 00 00 01 11 11 1汇编程序汇编程序设计设计0 00 01 11 11 1构造化程构造化程序设计序设计0 01 12 22 2数据构造数据构造0 01 12 22 23 33 3编译原理编译原理0 00 01 1程序设计程序设计0 01 1离散数学离散数学0 0数学数学输出：输出：数学，数学， 离散数学，离散数学，程序设计，程序设计，数据构造，数据构造，构造化程序设计，构造化程序设计，编译原理，编译原理，汇编程序设计汇编程序设计拓扑排序的实现拓扑排序的实现 计算每个结点的入度，保管在数组计算每个结点的入度，保管在数组in

60、DegreeinDegree中；中； 检查检查inDegreeinDegree中的每个元素，将入度为中的每个元素，将入度为0 0的结的结点入队；点入队； 不断从队列中将入度为不断从队列中将入度为0 0的结点出队，输出此的结点出队，输出此结点，并将该结点的后继结点的入度减结点，并将该结点的后继结点的入度减1 1；假；假设某个邻接点的入度为设某个邻接点的入度为0 0，那么将其入队。，那么将其入队。 template void adjListGraph:topSort( ) const linkQueue q; edgeNode *p; int current, *inDegree = new intVers; for