《数据结构》-图

第7章 图,本章要点：图的概念、图的术语。图的存储结构的基本形式。图的遍历操作。图的应用。,图作为一种非线性数据结构，被广泛应用于多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决问题的数学手段之一。在离散数学中侧重于对图的理论进行系统的研究。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。,7.1 图的定义与基本术语,7.1.1 图的定义 图是一种较线性表和树更为繁杂的数据结构，图结构与他们的不同表现在结点之间的关系上，在图结构中顶点之间的关系可以是多对多，即某一顶点与其它顶点间的关系是任意的，即：可以有关也可以无关。图由两个集合V和VR组成，其中V是有限顶点的集合，VR是顶点关系的有限集合。习惯上将图中的数据元素称为顶点(vertex)。图的抽象数据类型定义如下：ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R=VRVR=|v，wV且P(v，w)，表示从v到w的弧，P(v，w)定义了弧的意义,7.1 图的定义与基本术语（续）,基本操作：1.CreateGraph(*G，V，VR)：V是图的顶点集，VR是图中顶点关系的集合。按V和VR的定义构造图G。 2.DestroyGraph(*G)：已知图G存在，销毁图G，并释放空间。3.LocateVex(G，u)：图G存在，u和G中顶点有相同特征，若存在顶点u，则返回该顶点在图中位置；否则返回零。4.GetVex(G，v)：图G存在，v是G中某个顶点，返回v的值。5. PutVex(*G，v，value)：图G存在，v是G中某个顶点，将value值赋给v。,7.1 图的定义与基本术语（续）,6. FirstAdjVex(G，V)：图G存在，v是G中某个顶点,返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。 7. NextAdjVex(G，V，w)：图G存在，v是G中某个顶点，w是V的邻接顶点,返回v的(相对于w的)下一个邻接顶点。若w是V的最后一个邻接点，则返回“空”。8. InsertVex(*G，v)：图G存在，v和图中顶点有相同特征,在图G中增添新顶点v。 9. DeleteVex(*G，v)：图G存在，v是G中某个顶点,删除G中顶点v及其相应的关系。10. InsertArc(*G，v，w)：图G存在，v和w是G中两个顶点,在G中增添弧，若G是无向的，则还增添对称弧。,11. DeleteArc(*G，v，w)：图G存在，v和w是G中两个顶点,在G中删除弧，若G是无向的，则还删除对称弧。DFSTraverse(G，Visit( )：图G存在，Visit是顶点的应用函数,对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit（），一次且仅一次。一旦visit( )失败，则操作失败。13. BFSTraverse(G，Visit( )：图G存在，Visit（）是顶点的应用函数,对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit（），一次且仅一次。一旦visit( )失败，则操作失败。ADTGraph,7.1 图的定义与基本术语（续）,7.1.2 图的基本术语,1. 有向图和无向图 图的数据结构为：Graph =（V，VR），其中：V是顶点的有穷集合；VR是两个顶点之间的关系集合。若VR，则表示从x到y的一条弧(arc)，且称x为弧尾或初始点，称y为弧头(head)或终端点，此时的图称为有向图(digraph)，如图7.1(a)所示。 若 VR必有 VR，即VR是对称的。则以无序对(x，y)代替有序对，表示x和y之间的一条边(edge)， 此时的图称为无向图(undigraph)，如图7.1(b)所示其中 G1 =(V 1 ，R1)： V1 =v1，v2，v3，v4，R1=， , 。 G2 =(V2 ，R2)：V2=v1，v2，v3，v4，v5， R2=(v1，v2)，(v2，v3)，(v2，v4)，(v3，v4)，(v3，v5),7.1.2 图的基本术语（续）,在图的讨论中不考虑顶点到自身的边，即若是G的弧则v1 v2并且也不允许一条边在图中重复出现。,7.1.2 图的基本术语（续）,2. 顶点的位置 顶点在图中的位置如何确定？从图的逻辑结构定义来看，图中的顶点是非线性序列，不能像线性序列排列有唯一的序列。在图中可以将任一个顶点看成是图的第一个顶点，同理，对于任一顶点而言，它的邻接点之间也不一定存在顺序关系。为了对图的操作方便，需要将图中的顶点按排列起来。所谓的“顶点在图中的位置”是指该顶点在存储中形成的位置序号，（如果是顺序存储可能是数组下标，如果是链式存储可能是存储的地址指针）。 3. 邻接点 对于无向图G(V，E)，如果边（v1，v2）E，则称顶点v1，v2互为邻接点，即v1，v2相邻接。边（v1，v2）依附于顶点v1和v2 ，或者说边（v1，v2）与顶点v1和v2相关联。,7.1.2 图的基本术语（续）,对于有向图G(V，A)而言，若弧A，则称顶点v1邻接到顶点v2 ，顶点v2邻接自顶点v1 ，或者说弧与顶点v1和v2相关联。图中某个顶点的邻接点有若干，当存储相邻的关系时，自然形成了顺序，即：第1个到第k个邻接点，称第k+1个邻接点是第k个邻接点的下一个邻接点，而最后一个邻接点的下一个邻接点为“空”。 4. 完全图 一个具有n个结点的无向图，其边数小于等于 ，如果边数恰好等于的n个顶点的无向图称为完全图。如图7.2中的G 3是个完全图。 对于有向图而言，在一个n个顶点的有向图中，其边数的取值范围是0n(n-1)。,7.1.2 图的基本术语（续）,称有n(n-1)条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完全图。如图7.3中的G 4 是个有向完全图。对于有很少条边的 图称为稀疏图，反之称为稠密图。,V1,V2,V3,V4,G3,图7.2 完全图示例,V1,V2,V3,V4,G4,图7.3 有向完全图示例,7.1.2 图的基本术语（续）,5. 度 顶点V的度(degree)是与V相关联的边（弧）的数目，记作TD(V)。若G是一个有向图，则把以结点V为终端的弧的数目称作V的入度ID(V)；把以V为起始的弧数目称为V的出度OD(V)，则有以下关系： TD(V)=ID(V)+OD(V) 在图7.1（a）的G1中ID(v3)=2，OD(v3)=1， TD(v3)=3。 设图中有n个结点，e条边，则： 在有向图中，出度为的结点称为终端结点（或叶子）。 6. 子图 图G(V，E)，G=(V，E)中，VV，EE，并且中的边所关联的结点都在V中，则称图G是图G的子图。,7.1.2 图的基本术语（续）,下面给出图7.2中无向图G 3的几个子图，如图7.4所示。,V1,V1,V2,V3,V2,V3,V4,V1,V2,V3,V4,(a) (b) (c) (d)图7.4 G 3的子图示例,7.1.2 图的基本术语（续）,7. 路径与回路 在图G(V，E)中，如果有结点序列： Vp，Vi1，Vi2，Vin，Vq ，使得 (Vp ，Vi1)，(Vi1 ， Vi2)，(Vin，Vg) E（若对有向图，则存在一系列弧）则称从结点Vp到结点Vq存在一条路径，路径长度就为这条路径上的边数。如果一条路径上的结点除Vp和Vq可以相同外，其它结点都不相同，则称此路径为一简单路径。 把路径(V1，V2)，(V2，V3)，(V3，V4)缩写成V1V2V3V4。在图G3中V1，V2，V3 和V1V3V4V1V3是两条路径，前者是一条简单路径，我们只研究简单路径。当Vp=Vq时简单路径Vp，Vi1，Vi2，Vin，Vp ，称为回路(也称环)。,7.1.2 图的基本术语（续）,8. 连通图与连通分量 对无向图G=(V，E)而言，如果从V1到V2有一条路径，称V1和V2是连通的，若图G中任意两个结点都是连通的则称无向图G是连通图。无向图中的极大连通子图称为该无向图的连通分量。例如：图7.1(b)中的G2是连通图。图7.5中无向图G5是非连通图，它有两个连通分量。 对有向图G(V，A)中，若对于每对顶点Vi ，Vj且ViVj ，从Vi到Vj和Vi到Vj都有路径，则称该有向图为强连通图。有向图的极大强连通子图称作有向图的强连通分量，例如：图7.3中的G4是强连通图。图7.6中有向图G6有两个强连通分量。,7.1.2 图的基本术语（续）,图7.5 无向图G 5及连通分量,V1,V2,V3,V4,V5,V6,V7,G5,7.1.2 图的基本术语（续）,V1,V2,V3,V4,G6,图7.6 有向图G6及强连通分量,V5,V6,V1,V2,V3,V4,图7.7 有向网与权,V5,V6,6,8,5,4,3,2,7.1.2 图的基本术语（续）,9. 权与网 在实际应用中，有时图的边或弧上往往与具有定意义的数值有关，与边（弧）相关的数，称为权。例如权可以表示从一个顶点到另一个顶点的距离或耗费等信息。将这种带权的图称为网。网有无向网、有向网。图7.7所示的为有向网。 10. 生成树 生成树是无向连通图的一个极小连通子图，它含有图中的全部顶点和使任意顶点都连通的最少的边。如图7.8所示。如果在一棵生成树上添加一条边，则必定形成一个环（因为添加的这条边使得它依附的两个顶点之间有了第二条路径）。在无向图中，一棵有n个顶点的生成树有且仅有n-1条边。如果图中多于n-1条边，则一定有回路。,7.1.2 图的基本术语（续）,但是有n个顶点和n-1条边的图并非一定连通，不一定存在生成树。如果一个图具有n个顶点且边数小于n-1条，则该图一定是非连通图，非连通图可以生成多个生成树。,V1,V2,V3,V4,(a) 无向图G (b) G的生成树图7.8 无向网与生成树,V5,V6,V1,V2,V3,V4,V5,V6,7.2 图的存储,图是一种用途非常广的数据结构，存储方法是多种多样，对于不同的应用问题有不同的表示方法。不论哪种数据结构，在存储时主要有两方面：第一.如何存储数据；第二.如何存储数据间的关系。当数据和关系都存储在存储器中，就可以按数据间的关系，实现对数据的各种操作。 图有四种比较常用的存储方法： 邻接矩阵表示法； 邻接表； 邻接多重表； 十字链表。,7.2.1 邻接矩阵表示法,用邻接矩阵存储图是将数据间的关系，用一个矩阵来表示，矩阵中的数据元素表示为：0、1（两点间有关系为1，没有关系为0）。表示结点之间关系的矩阵称为邻接矩阵。若G是有n个结点的图。 则G的邻矩阵是如下定义的nn矩阵。 Ai, j= 如图7.9所示的两个图G7和G8的邻接矩阵如下：,7.2.1 邻接矩阵表示法(续),G7的邻接矩阵为：,G8的邻接矩阵为：,7.2.1 邻接矩阵表示法(续),借助于邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。对于无向图，顶点vi的度是邻接矩阵中第i行(或第i列)的元素之和，即,对于有向图，第i行的元素之和为顶点vi的出度OD(vi)，第j列的元素之和为顶点Vj的人度ID(vj)。 无向图G 7、的邻接矩阵是对称的，而有向图的邻接矩阵不对称。 网的邻接矩阵可定义为：,7.2.1 邻接矩阵表示法(续),例如，图7.10是一个无向网。,V5,V1,V2,V3,V4,11,8,6,4,5,3,2,10,图7.10 无向网及邻接矩阵, 3 5 8 3 6 4 115 6 2 8 4 2 10 11 10 ,7.2.1 邻接矩阵表示法(续),在定义几种数据类型前，有两个常量说明，他们可以用于下面数据类型定义。#define INFINITY #define MAX_V_N /*最大顶点个数*/图的邻接矩阵存储表示如下：typedef enumDG，DN，UDG，UDN GraphKind;/*图的种类*/typedef Struct ArcCell /*定义图的邻接矩阵*/ VRType adj; /*VRType是顶点关系类型*/ InfoType *info; /*弧相关信息的指针*/ArcCell， AdjMatrixMAX_V_NMAX_V_N;,7.2.1 邻接矩阵表示法(续),typedef struct /*图的邻接矩阵表示法的数据类型*/ VertexType vexsMAX_V_N /*顶点数据*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum，arcnum; /*图的当前顶点数和弧数*/ GraphKind kind; /*图的种类标志*/ MGraph; 邻接矩阵表示法的特点如下： 对于无向图而言，它的邻接矩阵是对称矩阵(因为若(vi，vj)E，则(vj，vi)E)，因此可以采用特殊矩阵的压缩存储法。但对于有向图而言，其中的弧是有方问的，即若E，不一定有E，因此有向图的邻接矩阵不一定是对称矩阵，对于有向图的邻接矩阵的存储则需要nn个存储空间。,7.2.1 邻接矩阵表示法(续), 采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据邻接矩阵中的信息来判断。另外还便于求得各个顶点的度。对于无向图而言，其邻接矩阵第i行元素之和就是图中第i个顶点的度：,对于有向图因而言，其邻接矩阵第i行元素之和就是图中第i个顶点的出度：,7.2.1 邻接矩阵表示法(续),对于有向图而言，其邻接矩阵第i列元素之和就是图中第i个顶点的入度：,用邻接矩阵为存储结构的图的相关算法如下：/*给定图G求顶点v的位置*/int LocateVertex(MGraph G,VertexType v) i=0; while (ivexnum ,int Create_UDN(MGraph *G) /*采用邻接矩阵表示法，构造无向网G*/ scanf( ,7.2.1 邻接矩阵表示法(续),int Create_DN(MGraph *G) /*采用邻接矩阵表示法，构造有向网G*/ scanf( ,7.2.2 邻接表表示法,用邻接矩阵表示图，占用的存储单元个数只与图的结点个数有关，而与边的数目无关。一个n个结点的图，若其边数比nn少很多，那么它的邻接矩阵中就会有很多零元素，占用许多空间存储零元素当然浪费。用邻接表表示图，占用的存储单元不但与图中结点个数有关，而且与边数也有关，表示n个顶点的图，如果边数少，则占有的存储单元也少。 邻接表表示图是由两部分构成，即顶点数据表和表示数据关系的边（弧）构成的表： 顶点数据表：由所有顶点数据信息以顺序结构的向量表形式存储，一个表目对应于图的一个结点，每个表目包括两个部分，其一是表示数据的，可以是数据或指向结点数据的指针（data）；另一个是表示边（弧）的指针，,7.2.2 邻接表表示法（续）,该指针（firstarc）指向相邻的第一条边（弧），通过这个指针便可以随机访问相邻的任一顶点。表头结点的结构如图7.11(a)所示。 表示边的表：图中有n个顶点，就有n个表示边的链表，其中第i条链是由与第i个顶点相邻的边构成的链表。图的每个结点都有一个边链表，这个链表的表头是顶点数据表中第i个表目的指针域。边链表中结点的结构如图7.11(b)所示。它由三部分组成，邻接点域(adjvex)：用于存放与顶点vi相邻接的顶点在顶点表中的位置；链指针域(nextarc)用于指向与顶点vi相关联的下一条边或弧的结点；数据域(info)用于存放与边或弧相关的信息。,7.2.2 邻接表表示法（续）,如图7.12中的两个图的邻接表表示法如图7.13和图7.14所示。,V1,V2,V3,V4,V5,V1,V2,V3,V4,G7,G8,图7.12图G7和G8,nextarc,info,adjvex,(a)表示顶点数据的表目 (b) 表示边的表目图7.11 邻接表结点的结构,firstarc,data,7.2.2 邻接表表示法（续）,7.2.2 邻接表表示法（续）,一个图的邻接表存储结构说明如下：typedef struct ArcNode int adjvex; /*该边（弧）所邻接的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边（弧）的指针*/ InfoType *info; /*该边（弧）相关信息的指针*/ ArcNode;typedef struct Vnode VertexType data; /*顶点数据信息*/ ArcNode firstarc; /*指向第一条依附该顶点的边（弧）的指针*/ AdjListMAX_V_N;,7.2.2 邻接表表示法（续）,typedef struct AdjList vertices; int vexnum，arcnum; /*图的当前顶点数和弧数*/ int kind; /*图的种类标志*/ ALGraph; 采取邻接表作为存储结构的特点如下： n个顶点e条边的无向图，若采取邻接表作为存储结构，需要n个顶点数据Vnode和2e个表示边的结点ArcNode。显然在边很稀疏(即e远小于n(n-1)2时)的情况下，用邻接表存储所需的空间比邻接矩阵所需的空间(n(n-1)2)少。 无向图的度：在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。 有向图的度,7.2.2 邻接表表示法（续）,在有向图中，第i个边链表上结点的个数是顶点vi的出度，只需通过表头向量表中找到第i个顶点的边链表的头指针，实现顺链查找计数即可。 但是如果判定任意两个顶点之间是否有边或弧相连，需要搜索所有的边链表，这样比较麻烦。要想求第i个顶点的入度，也必须遍历整个邻按表，在所有边链表中查找邻接点域的值为i的结点并计数求和。由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，它需要通过扫描整个邻接表才能得到结果。 一种解决的方法是逆邻接表法，可以对每顶点vi再建立一个逆邻接表，即对每个顶点vi建立个所有以顶点vi为弧头的弧的表，如图7.15所示。这样求顶点vi的入度即是计算逆邻接表中第i个顶点的边链表中结点个数。,7.2.2 邻接表表示法（续）,在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度为O(n+e)，否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(ne)。,在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点(vi和vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此，不及邻接矩阵方便。,7.2.3 十字链表,十字链表(Orthogonal List)是表示有向图的一种存储结构。也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种存储形式。有向图中的每一条弧对应十字链表中的一个弧结点，有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。这两类结点构成十字链表的存储结构，如图7.16所示,其中： tailvex：表示弧尾顶点的位置。 headvex：表示弧头顶点的位置。 info：弧的相关信息。 hlink：指向以headvex为弧头结点的下条弧。 tlink：指向以tailvex为弧尾结点的下条弧。 data：用于存储与顶点有关的信息，如顶点的名字等。 firstin：用于指向以data数据项点作为弧头的第一条弧。 firstout：用于指向以data数据项点作为弧尾的第一条弧。,7.2.3 十字链表（续）,有向图的十字链表存储结构如下：typedef struct ArcBox /*图中弧结点定义见图7.16(a)结构*/ int tailvex，headvex; /*该弧的尾和头顶点的位置(数组元素的下标序号)*/ struct ArcBox *hlink，*tlink; /*分别为弧头相同和弧尾相同的弧的链域*/ InfoType *info; /*该弧相关信息的指针*/ ArcBox;typedef struct VexNode /*图中每一个顶点定义见图7.16(b)结构*/ VertexType data; ArcBox *firstin，*firstout; /*表示入度、出度的弧指针*/ VexNode;typedef struct VexNode xlistMAX_V_N; /*表头向量*/ int vexnum，arcnum; /*有向图的当前顶点数和弧数*/ OrGraph;,7.2.3 十字链表（续）,图7.17表示的有向图十字链表如图7.18所示。,建立有向图的十字链表，算法如下：int Create_DG(OrGraph *G) /*采用十字链表存储表示，构造有向图G */ scanf( /*输入弧相关信息*/ ,7.2.3 十字链表（续）,在十字链表中既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度(可在建立十字链表的同时求出)。创建十字链表的时间复杂度与创建邻接表的时间复杂度是相同的。在有向图的应用中，十字链表是很有用的。,7.2.4 邻接多重表,邻接多重表(Adjacency Multi_list)是无向图的一种存储结构，邻接多重表这种存储结构能够提供更方便的处理。在无向图的邻接表表示法中，每一条边(vi，vj)在邻接表中都对应着两个结点，它们分别在第i个边链表和第j个边的两条链表中。这给图的操作带来不便，如检测某条边是否被访问过，则需要同时找到表示该条边的两个结点，而这两个结点又分别在两个边链表中。邻接多重表解决了这个问题，将图中一条边用一个结点来表示，结点结构如图7.19(a)所示，图中的每一个顶点也对应一个顶点结点，结构如图7.19(b)所示。,7.2.4 邻接多重表(续),其中：mark：用以标记该边是否被访问过。ivex：该边依附的一个顶点在图中的位置。ilink：指向下一条依附于顶点ivex的边。jvex：该边依附的另一个顶点在图中的位置。jlink：指向下一条依附于顶点jvex的边。,7.2.4 邻接多重表(续),info：该边信息指针。data：存储与顶点有关的信息。firstedge：指向第一条依附于该顶点的边。 在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。可见，对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。因此，除了在边结点中增加一个标志域外，邻接多重表所需的存储的信息与邻接表相同。在邻接多重表上，各种基本操作的实现亦和邻接表相似。无向图的邻接多重表的存储结构如下：,7.2.4 邻接多重表(续),#define MAX_VERTEX_NUM /*最大顶点个数*/typedef emnu unvisited,visited VisitIf;typedef struct Ebox /*图中边表示的顶点的定义见图7.19(a)所示*/ VisitIf mark; /*访问标记*/ int ivex,jvex; /*该边依附的两个顶点的位置*/ struct EBox *ilink,*jlink; /*分别指向依附这两个顶点的下一条边*/ InfoType *info; /*该边信息指针*/ EBox;typedef struct VexBox /*图中每一个顶点定义见图7.19(b)所示*/ VertexType data; EBox *firstedge; /*指向第一条依附该顶点的边*/ VexBox;typedef struct VexBox adjmulistMAX_V_N; int vexnum，edgenum； /*无向图的当前顶点数和边数*/ANLGraph;,7.2.4 邻接多重表(续),例如图7.20所示无向图的邻接多重表如图7.21所示。,V1,V2,V3,V4,图7.20无向图,邻接多重表为存储结构的创建操作与十字链表相似，不再复述。 上面介绍了四种存储方法，其中：十字链表是针对有向图的，邻接多重表是针对无向图的，邻接矩阵和邻接表即可以存储有向图，也可以存储无向图。针对不同的算法，四种存储各有利弊，可以根据实际应用问题来选择合适的存储结构。,7.3 图的遍历,与树的遍历类似，图的遍历(traversing graph)是从某一顶点出发按序访问图中所有结点，且使每个结点仅被访问一次。 遍历图比遍历树要繁杂，因为图中的某一个顶点可能与图中其余顶点相邻接，即图中允许有回路。所以当从某一顶点访问了其他顶点后有可能顺着某一些边又回到了该顶点。因此在遍历图时，为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，设置一个数组，用于标示图中每个顶点是否被访问过，它的初始值全部为0(“假”)，表示顶点均未被访问过；某一个顶点被访问后，置相应访问标志数组中的值为1(“真”)，以表示该顶点已被访问过。按图中结点的访问顺序，图的遍历分两种：一种深度优先遍历，另一种是广度优先遍历。,7.3.1 深度优先搜索,深度优先搜索(Depth_First Search)是指按照深度方向搜索，它类似于树的先根遍历。深度优先搜索的基本思想是： 从图中某个顶点vi出发，首先访问vi 。 找出顶点vi的第一个未被访问的邻接点v j，然后访问顶点v j。找出顶点v j的第一个未被访问的邻接点vj1，,重复本步骤，直到顶点v j1的所有的邻接点都被访问为止。 返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个末被访问的邻接点，然后执行步骤。否则行步骤。 若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述搜索过程，直至图中所有顶点均被访问过为止。,7.3.1 深度优先搜索(续),图的遍历算法如下： void Traver(Graph G ) /*Graph表示图G的存储结构,深度优先遍历图G */ for (vi=0;vi0) /*当存在邻接点*/ if (!visitedw) DFS(G，w); w=Nextadj(G，v0，w); /*找下一邻接点*/ ,7.3.1 深度优先搜索(续),算法中对于Firstadj(G，v0)以及Nextadj(G，v0，w)并没有具体实现。因为对于图的不同存储方法，两个操作的实现方法不同，时间复杂度也不同。 用邻接矩阵方式实现void DFS(MGraph G,int v0) /*图G为邻接矩阵类型*/ visit(v0);visitedv0TRUE; for (vj0;vjadjvex) DFS(G，p-adjvex); p=p-nextarc; ,7.3.1 深度优先搜索(续),以邻接表作为存储结构，查找每个顶点的邻接点的时间复杂度为O(e)，其中e是无向图中的边数或有向图中弧数，则深度优先搜索图的时间复杂度为O(n+e)。递归算法进行深度遍历时，有两个过程，即：Traver()和DFS()。如果图是连图的，在Traver（）中就可以省去循环，只调用一次DFS（）过程；如果是不连通的，有几个连通分量Traver（）就调用几次DFS（）过程。,7.3.1 深度优先搜索(续),(1) 用非递归过程实现深度优先遍历。void DFS(Graph G，int v0) /*从v0出发深度优先搜索图G*/ InitStack(s); /*初始化空栈*/ Push(s，v0); while(!Empty(s) v=Pop(s); if (!visited(v) /*栈中可能有重复顶点*/ visit(v); visitedvTRUE; w=Firstadj(G,v); /*求v的第一个邻接点*/ while(w0) if (!visited(w) Push(s，w); w=Nextadj(G，v，w); /*求v相对于w的下一个邻接点*/ ,7.3.1 深度优先搜索(续),下面通过图7.22所示图G，及其邻接表表示，描述对图G的深度遍历非递归过程。,7.3.1 深度优先搜索(续),操作如下： 初始化栈S，将v1入栈(设v1为起点)。 栈顶出栈（v1），访问v1并将其未被访问的邻接顶点压入S栈中（v3和v2入栈）。 栈非空，栈顶v2 出栈，访问v2 ，然后将与v2邻接未访问顶点v5和v4压栈。 栈非空，栈顶v4出栈，访问v4 ，然后将与v4邻接未访问顶点v8压栈。 栈非空，再弹出v8 ，访问v8 ，将与v8邻接未访问顶点v5 ，v6 ，v7压栈。从这一步能看出，栈中可能有重复点（v5），所以访问顶点前要先判断标志位。 栈非空，故再弹出v5 ，由于v5未被访问过，访问v5 ，将v5没被访问的邻接点压栈。因为v5的邻接点都被访问过，所以没有顶点进栈。 栈非空，弹出v6 ，v6未被访问，访问v6 ，再将v6没被访问的邻接点v3压栈。 栈非空，v3出栈 ，v3未被访问，访问v3 ，将v3没被访问的邻接点v7压栈。,7.3.1 深度优先搜索(续), 栈非空，v7出栈，访问v7 ，将v7没被访问的邻接点压栈，无进栈顶点。 栈非空，分别出栈v7 、v5、v3因都被访问过，且邻接顶点都被访问，出栈。此时栈空，搜索结束。栈中的变化情况如图7.23所示。,7.3.2 广度优先搜索,广度优先搜索(Breadth First Search) 是指照广度方向搜索，和深度优先搜索不同的是：广度优先搜索先访问完所有的邻接点，再去寻找与邻接点相邻的下一层的其他顶点，它类似于树的层次遍历。 广度优先搜索的基本思想是： 从图中某个顶点v0出发，首先访问v0 。 依次访问v0的各个末被访问的邻接点。 分别从这些邻接点(端结点)出发，依次访问它们的各个末被访问的邻接点(新的端结点)。访问时应保证：如果vi和vk为当前结点，且vi在vk之前被访问，则vi的所有末被访问的邻接点应在vk的所有未被访问的邻接点之前访问。重复步骤，直到所有结点均没有末被访问的邻接点为止。 若此时还有顶点末被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。,7.3.2 广度优先搜索(续),深度优先搜索以栈来操作，而广度优先搜索以队列来操作。按图7.22所示的无向图，广度优先遍历过程如下： 初始化队列q，先访问起始点v1，将v1入队； 队不空，队头v1出队，由于v1的邻接顶点v2和v3未被访问过，访问v2和v3并将v2和v3入队； 队不空，队头v2出队，由于v2的邻接顶点v1被访问过，而邻接顶点v4和v5未被访问过，访问v4和v5并将v4和v5入队； 队不空，队头v3出队，由于v3的邻接顶点v1被访问过，而邻接顶点v6和v7未被访问过，访问v6和v7并将v6和v7入队； 队不空，队头v4出队，由于v4的邻接顶点v2被访问过，而邻接顶点v8未被访问过，访问v8并将v8入队；,7.3.2 广度优先搜索(续), 最后v5 ，v6 ，v7 ，v8出队，由于它们的邻接顶点都被访问过，此时队空，表示搜索已结束。队中的变化情况如图7.24所示。,7.3.2 广度优先搜索(续),从上面的图中我们得到，广度优先搜索顺序为：V1 V2 V3 V4 V5 V6 V7 V8 。图的广度优先遍历的算法如下：void Traver(Graph G ) /*对图G按广度优先进行遍 历，Graph表示图的一种存储结构*/ for (vi=0;vivexnum;vi+) /*初始化*/ visitedvi=flase; for (vi=0;vi0) if (!visitedw) visit(w); visitedw=TRUE; Enqueue(q，w); w=Nextadj(G，v，w); /*找到下一邻接点*/ ,7.3.2 广度优先搜索(续),如果G是无向图，若要判断G是否连通(connected)；只要调用一次DFS或BFS，判断其是否还有没被访问的结点；如果全部顶点都被访问过，则此图是连通的，否则不连通。 分析上述算法，图中每个顶点至多入队一次，因此外循环次数为n。当图G采用邻接表方式存储，则当结点v出队后，内循环次数等于结点v的度d i 。由于访问所有顶点的邻接点的总的时间复杂度为O(d0+d1+d2+dn-i)O(e)，因此图采用邻接表方式存储，广度优先搜索算法的时间复杂度为O(n+e)；当图G采用邻接矩阵方式存储，由于找每个顶点的邻接点时，内循环次数等于n，因此广度优先搜索算法的时间复杂度为O(n2)。,7.4 图的连通性,前面已经介绍了连通图和连通分量的概念。本节将讨论：如何判断一个图是否为连通图；如何求一个连通图的连通分量；连通图在实际中的应用等。利用遍历算法求图的连通性问题，并讨论求解最小代价生成树的算法。7.4.1 无向图的连通分量与生成树 在对图进行遍历时，对于连通图，无论是广度优先搜索还是深度优先搜索，仅需要调用一次搜索过程，即从任一个顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连通分量中的顶点集。,7.4 图的连通性(续),例如，图7.25是一个非连通图，图7.26为其邻接表，按照它的邻接表进行深度优先搜索，需要三次调用DFS（）过程，得到的访问顶点序列为：V1 V2 V4 V5 V6 V3 V7 V8 V9 V10 V11 ，得到三个顶点集合，这三个顶点集分别加上依附于这些顶点的边，构成了非连通图的三个连通分量。,7.4 图的连通性(续),设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经的边的集合；B(G)是剩余的没有经历的边集合。显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图，它是连通图的一棵生成树，并且称由深度优先搜索得到的生成树为深度搜索生成树；由广度优先搜索得到的生成树为广度搜索生成树。 图7.22所示的无向连通图的深度搜索生成树和广度优先生成树如图7.27(a)和7.27(b)所示，图中虚线为集合B(G)中的边。,7.4 图的连通性(续),对于非连通图每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。例如，图7.28为图7.25所示图的深度搜索生成森