1、第第6章章 图图 6.1 6.1 图的基本概念图的基本概念 6.2 6.2 图的存储结构图的存储结构 6.3 6.3 图的遍历及求图的连通分量图的遍历及求图的连通分量 6.4 6.4 生成树和最小（代价）生成树生成树和最小（代价）生成树 6.5 6.5 最短路径最短路径6.6 6.6 有向无环图及其应用有向无环图及其应用 6.1.1 图的基本概念图的基本概念图（图（graph）图（图（graph）包含两部分，一部分是）包含两部分，一部分是顶点顶点，一，一部分是部分是边边。一般地，图用。一般地，图用G=(V,E)来表示，其中来表示，其中V是顶点（是顶点（vertex）集，一般为一个有穷非空集合；
2、）集，一般为一个有穷非空集合；E是边（是边（edge）集，）集，E中的每条边都是中的每条边都是V中某一对中某一对顶点的连接。顶点的连接。图图G=(V,E)中，顶点总数记为中，顶点总数记为|V|，边的总数，边的总数记为记为|E|。如果图中边的数目较少（相对于顶点数。如果图中边的数目较少（相对于顶点数来说），这样的图称为来说），这样的图称为稀疏图稀疏图（sparse graph）；）；反之，边数较多的图称为反之，边数较多的图称为密集图密集图（dense graph）或是或是稠密图稠密图。示例示例图图6.1 图的示例图的示例02341(a)0213123415(b)(c)术语术语 图中的边除了有数量
3、之分外，还有方向性。图中的边除了有数量之分外，还有方向性。当图中的边限定为从一个顶点指向另一个顶点时，当图中的边限定为从一个顶点指向另一个顶点时，这样的边称为这样的边称为有向边有向边，否则称为，否则称为无向边无向边。组成有。组成有向边的偶对可以看作是有序的，而组成无向边的向边的偶对可以看作是有序的，而组成无向边的偶对是无序的。含有有向边的图称为偶对是无序的。含有有向边的图称为有向图有向图（directed graph或简写为或简写为digraph）。有向图中）。有向图中的边也称为的边也称为弧弧（arc），若（），若（u,v）E是有向图是有向图G中的一条弧，则中的一条弧，则u称为称为弧尾弧尾（t
4、ail），），v称为称为弧头弧头（head）弧的方向是从）弧的方向是从u指向指向v。如果图中的所有边都是无向边时，这样的图如果图中的所有边都是无向边时，这样的图称为称为无向图无向图（undirected graph或或undigraph）。）。图图G=(V,E)中，一条边所连接的两个顶点互称中，一条边所连接的两个顶点互称为为邻接点邻接点（adjacent）。连接一对邻接点）。连接一对邻接点u、v的边的边称为与顶点称为与顶点u、v相关联（相关联（incident）的边，也可以）的边，也可以说边（说边（u,v）依附于顶点）依附于顶点u和和v。有些应用中，为了表明图中边的某些特性，往有些应用中，为了
5、表明图中边的某些特性，往往给边赋予一个非负值，这个非负值称为往给边赋予一个非负值，这个非负值称为权权（weight），相应的图称为），相应的图称为加权图加权图（weighted graph）或是）或是带权图带权图，也有的称之为，也有的称之为网网（network）。）。为了能明确表示图中的所有顶点，可以让各顶为了能明确表示图中的所有顶点，可以让各顶点带有标号，这样的图称为点带有标号，这样的图称为标号图标号图（labedled graph）。）。有有n个顶点的无向图中，可以证明其边数最多可达个顶点的无向图中，可以证明其边数最多可达n(n-1)/2；有向图中由于边具有方向性，所以可能的最大；有向图中
6、由于边具有方向性，所以可能的最大边数比无向图多了一倍，边数比无向图多了一倍，n个顶点的有向图中最大边数为。个顶点的有向图中最大边数为。包含了所有可能边的图称为包含了所有可能边的图称为完全图完全图（complete graph）。）。图图6.2 完全图示例完全图示例1342(a)4个顶点的无向完全图个顶点的无向完全图132(b)3个顶点的有向完全图个顶点的有向完全图在无向图中，与顶点在无向图中，与顶点v相关联的边的数目称为顶点相关联的边的数目称为顶点的的度度（degree）。例如，图）。例如，图6.1(a)中，顶点中，顶点0的度的度为为2；顶点；顶点1的度为的度为1；在有向图中，顶点的度分为出度
7、和入度。以某顶在有向图中，顶点的度分为出度和入度。以某顶点为弧头的弧的数目，称为该顶点的点为弧头的弧的数目，称为该顶点的入度入度（indegree），以某顶点为弧尾的弧的数目，称），以某顶点为弧尾的弧的数目，称为该顶点的为该顶点的出度出度（outdegree）。一个顶点的出度）。一个顶点的出度和入度之和入度之和和称为该顶点的称为该顶点的度度。例如，图。例如，图6.1(b)中，中，顶点顶点0的出度为的出度为2，入度为，入度为0，度为，度为2 假设图假设图G=(V,E)中含有中含有n个顶点，个顶点，e条边，每个条边，每个顶点的度为顶点的度为di(0i2(n-1)，则三者之间的关系为：，则三者之间的
8、关系为：(6.1)若两个图若两个图G=(V,E)和和G=(V,E)，满足下列条件：，满足下列条件：且且E中边依附的顶点均属于中边依附的顶点均属于V，则称，则称G为为G的的子图子图（subgraph）。）。1021niideEE V,V 图图6.3 子图示例子图示例023410234103410234023410341(a)图图G(b)(c)(d)(e)(f)在图在图G=(V,E)中，如果中，如果(v0,v1),(v1,v2),(vn-2,vn-1)都是都是E中的边，则顶点序列（中的边，则顶点序列（v0,v1,vn-1）称为从顶点）称为从顶点v0到顶到顶点点vn-1的的路径路径（path）。若图
9、）。若图G是有向图，则路径也是有向是有向图，则路径也是有向的，它由的，它由E中的弧中的弧(v0,v1),(v1,v2),(vn-2,vn-1)组成。有组成。有向路径要求所有弧的方向都一致。一条路径上包含的边或向路径要求所有弧的方向都一致。一条路径上包含的边或弧的数目称为弧的数目称为路径长度路径长度（length）。如果路径上各顶点均）。如果路径上各顶点均不同，则称此路径为不同，则称此路径为简单路径简单路径（simple path）。第一个顶）。第一个顶点和最后一个顶点相同的路径称为点和最后一个顶点相同的路径称为回路回路（cycle），回路也），回路也称为称为环环。如果一个回路中除第一个顶点和最
10、后一个顶点之。如果一个回路中除第一个顶点和最后一个顶点之外，其余顶点均不相同，则称为外，其余顶点均不相同，则称为简单回路简单回路（simple cycle）或或简单环简单环。不带回路的图称为不带回路的图称为无环图无环图。不带回路的有向图则。不带回路的有向图则称为称为有向无环图有向无环图。图图6.4 路径示例路径示例02341对于无向图对于无向图G，如果顶点，如果顶点u和顶点和顶点v之间有路径，之间有路径，则称这两个顶点是则称这两个顶点是连通连通的；如果无向图的；如果无向图G中任中任意一个顶点到其他任意顶点都至少存在一条路意一个顶点到其他任意顶点都至少存在一条路径，也就是说，图中任意两个顶点都是
11、连通的，径，也就是说，图中任意两个顶点都是连通的，则称图则称图G为为连通图连通图（connected graph）。无向）。无向图中的极大连通子图称为图中的极大连通子图称为连通分量连通分量（connected component）。）。有向图有向图G中，如果每对顶点中，如果每对顶点u与与v之间均有一条从之间均有一条从u到到v的有向路的有向路径，则称径，则称G为为强连通图强连通图（strongly connected graph），有向图），有向图的最大强连通子图称为的最大强连通子图称为强连通分量强连通分量；如果对于每对顶点；如果对于每对顶点u和和v，存在顶点序列存在顶点序列v0,v1,vn-1
12、，这里，这里u=v0，v=vn-1，并且，并且(vi,vi+1)E或或(vi+1,vi)E（0in-2），则称图），则称图G为为弱连通图弱连通图（weakly connected graph）。）。图图6.5 有向连通图有向连通图(a)强连通图强连通图(b)弱连通图弱连通图6.1.2 图的抽象数据类型图的抽象数据类型/图，顶点，边的抽象数据类型定义图，顶点，边的抽象数据类型定义/class Graph/图类的抽象数据类型图类的抽象数据类型public:Graph();/构造函数构造函数Graph();/析构函数析构函数int countVtx();/返回图中的顶点数返回图中的顶点数int co
13、untEdge();/返回图中的边数返回图中的边数int first_adj(int v);/得到顶点得到顶点v的第一个邻接顶点的第一个邻接顶点int next_adj(int v1,int v2);/得到顶点得到顶点v1在邻接点在邻接点v2之后的下一个之后的下一个邻接点邻接点EdgeweightType weight(Edge e);/返回边返回边e的权值的权值EdgeweightType weight(int v1,int v2);/返回边返回边的权值的权值;class Vertex/顶点类的抽象数据类型顶点类的抽象数据类型public:Vertex();/构造函数构造函数Vertex()
14、;/析构函数析构函数VtxdataType VtxData;/顶点数据顶点数据;class Edge/边类的抽象数据类型边类的抽象数据类型public:Edge();/构造函数构造函数Edge();/析构函数析构函数int adj1;/与边关联的第一个顶点与边关联的第一个顶点int adj2;/与边关联的第二个顶点与边关联的第二个顶点EdgeweightType weight;/该边的权值该边的权值;6.2 图的存储结构图的存储结构 图的结构较复杂，每个图中的顶点数、边数，以图的结构较复杂，每个图中的顶点数、边数，以及每个顶点的度数都可能相差许多。与其他数据及每个顶点的度数都可能相差许多。与其
15、他数据类型类似，图也有两类基本的存储方式，即类型类似，图也有两类基本的存储方式，即顺序顺序存储结构存储结构（或称静态存储结构）及（或称静态存储结构）及动态存储结构动态存储结构。实际应用中可以根据具体的图的特点和对图进行实际应用中可以根据具体的图的特点和对图进行的操作，在这两类基本存储结构之上选取适当的的操作，在这两类基本存储结构之上选取适当的存储结构。存储结构。顺序存储结构以顺序存储结构以邻接矩阵邻接矩阵（adjacency matrix）为）为代表，动态存储结构以代表，动态存储结构以邻接表邻接表（adjacency list）为代表，另外在邻接表基础上，还有逆邻接表及为代表，另外在邻接表基础
16、上，还有逆邻接表及邻接多重表等存储方式。邻接多重表等存储方式。6.2.1 邻接矩阵邻接矩阵设图设图G=(V,E)，|V|=n，则图的，则图的邻接矩阵邻接矩阵是一个是一个n*n 矩阵，矩阵元素表示图中各顶点之间的邻接关矩阵，矩阵元素表示图中各顶点之间的邻接关系。邻接矩阵也称为系。邻接矩阵也称为相邻矩阵相邻矩阵。设各顶点依次记为。设各顶点依次记为v0,v1,vn-1，如果从，如果从vi到到vj存在一条边，则邻接矩存在一条边，则邻接矩阵的第阵的第i行第行第j列的元素值为列的元素值为1，否则值为，否则值为0。邻接矩。邻接矩阵的存储空间与顶点个数有关，为阵的存储空间与顶点个数有关，为 O(|V|2)。定
17、义邻接矩阵如下，它是一个二维数组：定义邻接矩阵如下，它是一个二维数组：(6.2)1-nji,0 ,01-nji,0 ,1EvvEvvjiAjiji若若若若对于加权图，如果图中从对于加权图，如果图中从vi到到vj存在一条边，则邻存在一条边，则邻接矩阵的第接矩阵的第i行第行第j列的元素值为边列的元素值为边(vi,vj)的的权权wij，否则值为否则值为。(6.3)1-nji,0 ,1-nji,0 ,EvvEvvwjiAjijiji若若若若例例 加权图加权图G如图如图6.6所示，写出其邻接矩阵表示。所示，写出其邻接矩阵表示。图图6.6 加权图加权图G图图6.6的邻接矩阵如下：的邻接矩阵如下：35v1v
18、2V0v3v427988 29288935837857对于有对于有n个顶点的图个顶点的图G，一般地，其邻接矩阵需要，一般地，其邻接矩阵需要n2个存储位置。考虑到无向图邻接矩阵的个存储位置。考虑到无向图邻接矩阵的对称性对称性，当使用数组存储对称矩阵时，可以只存储其下三当使用数组存储对称矩阵时，可以只存储其下三角（或上三角）的元素；同时，图中不含有角（或上三角）的元素；同时，图中不含有(i,i)形式的边，所以邻接矩阵的对角元素全为形式的边，所以邻接矩阵的对角元素全为0或是或是，也不需要存储。因而无向图的存储空间可压缩到也不需要存储。因而无向图的存储空间可压缩到个个n(n-1)/2存储位置。存储位置
19、。用邻接矩阵表示图时，可以很容易地判定图中任用邻接矩阵表示图时，可以很容易地判定图中任意两顶点之间是否存在意两顶点之间是否存在边边（或弧）。（或弧）。借助于邻接矩阵，也很容易求图中各顶点的借助于邻接矩阵，也很容易求图中各顶点的度度。设用邻接矩阵表示有设用邻接矩阵表示有n个顶点的图个顶点的图G，计算，计算G中有中有多少条边时，需要检查矩阵中的所有元素，因此多少条边时，需要检查矩阵中的所有元素，因此时间复杂度时间复杂度为为O(n2)。另一方面，其。另一方面，其存储空间存储空间仅与仅与图图G中的顶点数有关，与边数无关，即为中的顶点数有关，与边数无关，即为O(n2)。因此，当图中边的数目远远小于因此，
20、当图中边的数目远远小于n2时，检查图中时，检查图中边的数目的时间复杂度及存储邻接矩阵的空间复边的数目的时间复杂度及存储邻接矩阵的空间复杂度都将有极大的浪费。为解决这个问题，可以杂度都将有极大的浪费。为解决这个问题，可以采用另外一种存储结构，即采用另外一种存储结构，即邻接表邻接表。6.2.2 邻接表邻接表邻接表邻接表是图的动态表示方法，它使用链表存储图是图的动态表示方法，它使用链表存储图中顶点的邻接点，每个顶点的所有邻接点存储在中顶点的邻接点，每个顶点的所有邻接点存储在一个链表中，而这些链表的表头又分别存储在一一个链表中，而这些链表的表头又分别存储在一个数组的各元素中。个数组的各元素中。设图设图
21、G=(V,E)，则邻接表由一个，则邻接表由一个一维数组一维数组和和|V|个个链表链表组成，邻接表数组包含组成，邻接表数组包含|V|个元素；与顶点个元素；与顶点vi（0in-1）相邻接的所有顶点组成第）相邻接的所有顶点组成第i个链表，其个链表，其表头指针存于一维数组的第表头指针存于一维数组的第i个元素中。除指向链个元素中。除指向链表的指针外，数组元素中还可以保存相应顶点的表的指针外，数组元素中还可以保存相应顶点的相关信息。相关信息。链表的每个结点有两个域，一个是链表的每个结点有两个域，一个是顶点域顶点域，存储，存储邻接顶点在数组中的序号；另一个是邻接顶点在数组中的序号；另一个是指针域指针域，指，
22、指向下一个邻接顶点。向下一个邻接顶点。邻接表的邻接表的表结点结构表结点结构如下图所示：如下图所示：顶点序号顶点序号指针指针例例 以图以图6.1(a)为例，给出它的邻接表为例，给出它的邻接表 图图6.7 邻接表示例邻接表示例2340304241230123401234对于对于带权图带权图，可以让每个链表元素增加一个域，可以让每个链表元素增加一个域，存储两个顶点连成的这条边的权。它的表结点结存储两个顶点连成的这条边的权。它的表结点结构如下所示：构如下所示：例例 图图6.6的邻接表如图的邻接表如图6.8所示：所示：图图6.8 带权图带权图邻接表示例邻接表示例顶点序号顶点序号权值权值指针指针v00v1
23、1v22v33v441738250738230549130842182932对于无向图，使用邻接表可以很方便地求出顶点对于无向图，使用邻接表可以很方便地求出顶点的度，第的度，第i个单链表中个单链表中结点的个数结点的个数即为顶点即为顶点vi的的度度。对于有向图，第对于有向图，第i个单链表中结点的个数为顶点个单链表中结点的个数为顶点vi的的出度出度；如果要计算顶点；如果要计算顶点vi的的入度入度，需要遍历邻接，需要遍历邻接表中的所有表中的所有n个单链表，找出顶点为个单链表，找出顶点为vi的结点个数。的结点个数。用邻接表表示有用邻接表表示有n个顶点和个顶点和e条边的无向图时，需条边的无向图时，需要一
24、个由要一个由n个元素组成的顺序表（表头结点表）个元素组成的顺序表（表头结点表）和和2e个结点组成的个结点组成的n个单链表。而表示有个单链表。而表示有n个顶点个顶点e条弧的有向图时，需要一个由条弧的有向图时，需要一个由n个元素组成的顺个元素组成的顺序表和序表和e个结点组成的个结点组成的n个单链表。邻接表的空间个单链表。邻接表的空间复杂度为复杂度为O(n+e)。使用邻接表存储方式时，判定两个顶点间是否使用邻接表存储方式时，判定两个顶点间是否存存在边在边的操作将比使用邻接矩阵费时，此时需要遍的操作将比使用邻接矩阵费时，此时需要遍历邻接表中的一个单链表。历邻接表中的一个单链表。6.2.3 逆邻接表逆邻
25、接表使用邻接表表示有向图时，求某个顶点的入度比使用邻接表表示有向图时，求某个顶点的入度比计算顶点的出度要麻烦，为此，可以仿效邻接表计算顶点的出度要麻烦，为此，可以仿效邻接表建立有向图的建立有向图的逆邻接表逆邻接表，即把所有邻接到顶点，即把所有邻接到顶点vi 的顶点链接成一个单链表，此时，逆邻接表中第的顶点链接成一个单链表，此时，逆邻接表中第i个单链表中结点的个数即是顶点个单链表中结点的个数即是顶点vi 的入度。的入度。例例 图图6.1(b)的逆邻接表如图的逆邻接表如图6.9所示：所示：图图6.9 逆邻接表示例逆邻接表示例012012012234031156.2.4 邻接多重表邻接多重表在邻接表
26、的基础上，提出邻接多重表结构，让无在邻接表的基础上，提出邻接多重表结构，让无向图中的每条边只出现一次，并通过各指针将这向图中的每条边只出现一次，并通过各指针将这些边互相连接起来，便于查找。些边互相连接起来，便于查找。邻接多重表中，无向图的每条边用一个邻接多重表中，无向图的每条边用一个结点结点表示，表示，结点含有结点含有5个域，具体形式如下：个域，具体形式如下：infoivexilinkjvexjlink其中，其中，info域域存储与该条边相关的一些信息，例存储与该条边相关的一些信息，例如是否已被访问过的标记、边的权值等；如是否已被访问过的标记、边的权值等；ivex和和jvex是两个顶点域，存储
27、这条边所依附的两个顶是两个顶点域，存储这条边所依附的两个顶点；点；ilink和和jlink是两个指针域，依靠它们可以将是两个指针域，依靠它们可以将各条边连接起来，各条边连接起来，ilink指向与指向与ivex相关联的下一相关联的下一条边，条边，jlink指向与指向与jvex相关联的下一条边。在这相关联的下一条边。在这种存储结构中，既有水平方向的指针，也有垂直种存储结构中，既有水平方向的指针，也有垂直方向的指针，所以又被称为方向的指针，所以又被称为十字链表十字链表。例：例：图图6.10(a)的邻接多重表如图的邻接多重表如图6.10(b)所示所示图图6.10 图及其邻接多重表图及其邻接多重表013
28、2(a)(b)012011230203136.2.5 图的实现图的实现/图的邻接矩阵实现图的邻接矩阵实现/int const MaxVtxNum=10000;/最大顶点个数最大顶点个数templateclass Vertex/Vertex类的抽象数据类型类的抽象数据类型public:Vertex();/构造函数构造函数Vertex();/析构函数析构函数VtxdataType VtxData;/顶点数据顶点数据;templateclass Graph private:EdgeweightType AdjMatrixMaxVtxNumMaxVtxNum;/图的图的邻接矩阵邻接矩阵SeqList
29、Vertex VtxListMaxVtxNum;/顶点顶点表表int CurrentVtxNum;/当前的顶点数当前的顶点数int CurrentEdgeNum;/当前的边数当前的边数public:typedef EdgeweightType*EdgeGraph();/构造函数构造函数Graph();/析构函数析构函数int countVtx();/返回图中的顶点数返回图中的顶点数int countEdge();/返回图中的边数返回图中的边数int first_adj(int v);/得到顶点得到顶点v的第一个邻接顶点的第一个邻接顶点int next_adj(int v1,int v2);/得
30、到顶点得到顶点v1在邻接点在邻接点v2之后之后的下一个邻接点的下一个邻接点EdgeweightType weight(Edge e);/返回边返回边e的权值的权值EdgeweightType weight(int v1,int v2);/返回边返回边的权的权值值;templateGraph:Graph()/构构造函数造函数for(int i=0;iMaxVtxNum;i+)for(int j=0:jMaxVtxNum;j+)AdjMatrixij=0;CurrentVtxNum=0;CurrentEdgeNum=0;templateGraph:Graph()类类Graph中关于图中顶点的操作如
31、下：中关于图中顶点的操作如下：templateint Graph:countVtx()/返回图中的顶点数返回图中的顶点数return CurrentVtxNum;templateint Graph:first_adj(int v)/得到顶点得到顶点v的第一个邻接顶点的第一个邻接顶点for(int v1=0;v10&AdjMatrixvv1 INFINITY)return v1;return 1;templateint Graph:next_adj(int v1,v2)/得到顶点得到顶点v1位于邻接顶点位于邻接顶点v2之后的下一个邻接之后的下一个邻接点点for(int vn=v2+1;vn 0&
32、AdjMatrixv1vn INFINITY)return vn;return 1;类类Graph中关于图中边的操作如下：中关于图中边的操作如下：templateint Graph:countEdge()/返回返回图中的边数图中的边数return CurrentEdgeNum;templateEdgeweightType Graph:weight(Edge e)/返回边返回边e的权值的权值return*e;templateEdgeweightType Graph:weight(int v1,int v2)/返回边返回边的权值的权值return AdjMatrixv1v2;使用邻接表时，为每个边
33、链表的表元素定义节点使用邻接表时，为每个边链表的表元素定义节点Edgelink，实现的图类及成，实现的图类及成员函数如下：员函数如下：template/定义边链表的节点类定义边链表的节点类class Edgelink public:int destvtx;/边的另一个顶点边的另一个顶点EdgeweightType weight;/边上的权值边上的权值Edgelink*next;/指向下一条边指向下一条边链的指针链的指针Edgelink();Edgelink();templateclass VtxNode/定义顶点类定义顶点类public:VtxdataType data;/顶点数据类型顶点数据
34、类型Edgelink*first;/指向边链表的指向边链表的头指针头指针VtxNode();VtxNode();template/构造函数构造函数class Graphprivate:seqList VtxNode NodeListMaxVtxNum;/顶点表顶点表int CurrentVtxNum;/当前顶点数当前顶点数 int CurrentEdgeNum;/当前的边数当前的边数public:Graph();Graph();typedef Edgelink*Edgeint countVtx();/返回图中的顶点数返回图中的顶点数int countEdge();/返回图中的边数返回图中的边数
35、int first_adj(int v);/得到顶点得到顶点v的第一个邻接顶点的第一个邻接顶点int next_adj(int v1,int v2);/得到顶点得到顶点v1位于邻接顶点位于邻接顶点v2之后的下一个邻接点之后的下一个邻接点EdgeweightType weight(Edge e);/返回边返回边e的权值的权值EdgeweightType weight(int v1,int v2);/返回边返回边的权的权值值;templateGraph:Graph()/构造函数构造函数CurrentVtxNum=0;CurrentEdgeNum=0;采用邻接表存储方式时，对图中顶点的操作如下：采用
36、邻接表存储方式时，对图中顶点的操作如下：template/返回图中的返回图中的顶点数顶点数int Graph:countVtx()return CurrentVtxNum;template/得到顶点得到顶点v的的第一个邻接顶点第一个邻接顶点int Graph:first_adj(int v)if(NodeListv-first!=NULL)return NodeListv-first-destvtx;return 1;template/得到顶点得到顶点v1位于邻接顶点位于邻接顶点v2之后的下一个邻接顶点之后的下一个邻接顶点int Graph:next_adj(int v1,int v2)Edg
37、elink*p=NodeListv1-first;while(p!=NULL)if(p-destvtx=v2&p-next!=NULL)return p-next-destvtx;elsep=p-next;return-1;对图中边的操作如下：对图中边的操作如下：template/返返回图中的边数回图中的边数int Graph:countEdge()return CurrentEdgeNum;template/返返回边回边e的权值的权值EdgeweightType Graph:weight(Edge e)return e-weight;template/返返回边回边的权值的权值Edgeweig
38、htType Graph:weight(int v1,int v2)Edgelink*p=NodeListv1-first;while(p!=NULL)if(p-destvtx=v2)return p-weight;elsep=p-next;return 0;6.3 图的遍历及求图的连通分量图的遍历及求图的连通分量哥尼斯堡桥问题哥尼斯堡桥问题问：一个散步者能否从任何一个位置出发，走过问：一个散步者能否从任何一个位置出发，走过七座桥，且每座桥只走过一次，最后回到出发点。七座桥，且每座桥只走过一次，最后回到出发点。图图6.11哥尼斯堡桥问题哥尼斯堡桥问题ABCD（a）哥尼斯堡镇的七桥）哥尼斯堡镇的
39、七桥（b）七桥的逻辑结构）七桥的逻辑结构遍历遍历 设给定一个连通图设给定一个连通图G=(V,E)，我们希望从图，我们希望从图中的某个顶点出发，经过一定的路线访问图中的中的某个顶点出发，经过一定的路线访问图中的所有顶点，使每个顶点被访问且只访问一次，这所有顶点，使每个顶点被访问且只访问一次，这一过程称为图的一过程称为图的遍历（遍历（traversal）。与树的遍历类似，图的遍历也需要依据某种与树的遍历类似，图的遍历也需要依据某种规律进行，遍历的方式主要有两种：规律进行，遍历的方式主要有两种：深度优先搜深度优先搜索索（depth first search,DFS）及）及广度优先搜索广度优先搜索（b
40、readth first search,BFS）。）。6.3.1 深度优先搜索深度优先搜索深度优先搜索类似于树的先序遍历，深度优先搜索类似于树的先序遍历，遍历过程遍历过程如如下：下：直观地看，深度优先搜索即是从开始顶点起，直观地看，深度优先搜索即是从开始顶点起，沿着一条路径尽可能地向前搜索，直到不能再向沿着一条路径尽可能地向前搜索，直到不能再向前时（这个顶点的所有邻接点都已被访问过）就前时（这个顶点的所有邻接点都已被访问过）就往回退，回退过程也称为往回退，回退过程也称为回溯回溯。回溯时沿着与访。回溯时沿着与访问的顺序相反的顺序，当回溯到仍有未被访问邻问的顺序相反的顺序，当回溯到仍有未被访问邻接
41、点的一个顶点时，把这个点当成起始点，再找接点的一个顶点时，把这个点当成起始点，再找一条路径继续向前搜索。因此，图的深度优先搜一条路径继续向前搜索。因此，图的深度优先搜索遍历过程是个索遍历过程是个递归过程递归过程。例：例：图图6.12(a)，它的邻接表如图，它的邻接表如图6.12(b)所示，从顶点所示，从顶点v1开开 始，进行深度优先搜索，始，进行深度优先搜索，图图6.12 图的深度优先搜索示例图的深度优先搜索示例它的一个它的一个访问序列访问序列为：为：v1v2v4v8v5v6v3v714532768(a)无向图无向图231451671122334455667788283838284576(b)
42、邻接表邻接表深度优先搜索过程中，记录顶点访问顺序的深度优先搜索过程中，记录顶点访问顺序的栈栈的变化情况的变化情况如图如图6.13所示：所示：图图6.13 深度优先搜索过程中栈的变化情况深度优先搜索过程中栈的变化情况v1v7v3v6v8v4v2v1v2v1v4v2v1v8v4v2v1v8v4v2v1v6v8v4v2v1v3v6v8v4v2v1v5v8v4v2v1图的深度优先搜索过程在某种程度上将依赖于邻图的深度优先搜索过程在某种程度上将依赖于邻接表的接表的存储次序存储次序及邻接点的及邻接点的选择算法选择算法，遍历的顺，遍历的顺序可能有多个结果。另外，选择的初始顶点不同，序可能有多个结果。另外，选
43、择的初始顶点不同，遍历的结果也不同。遍历的结果也不同。例如，下面的顶点序列也是图例如，下面的顶点序列也是图6.12(a)从从v1开始的开始的深度优先遍历结果：深度优先遍历结果：v1v2v5v8v6v3v7v4下列遍历序列是从下列遍历序列是从v2开始的一种深度优先搜索结开始的一种深度优先搜索结果：果：v2v1v3v6v8v4v5v7图的深度优先搜索算法如下：图的深度优先搜索算法如下：/图的深度优先遍历图的深度优先遍历/template void Graph:DFS()int*visited=new intCurrentVtxNum;/定义定义visitedfor(int i=0;iCurrent
44、VtxNum;i+)/初始化初始化visitedvisitedi=0;for(int i=0;iCurrentVtxNum;i+)if(visitedi=0)DFS(i,visited);delete visited;templatevoid Graph:DFS(int v,int visited)visite(v);/访问顶点访问顶点vvisitedv=1;/将将visitedv置为置为1，表示已经访问过，表示已经访问过int w=first_adj(v);/取取v的第一个邻接顶点的第一个邻接顶点wwhile(w!=-1)if(!visitedw)/若顶点若顶点w还未被访问还未被访问DFS(
45、w,visited);/递归调用递归调用w=next_adj(v,w);/取下一个邻接顶点取下一个邻接顶点实现的实现的DFS方法有两个：方法有两个：DFS()和和DFS(int v,int visited)。lDFS()中作初始准备，设置访问标志。中作初始准备，设置访问标志。lDFS(int v,int visited)将实际遍历图中各点，将实际遍历图中各点，并且递归调用。并且递归调用。visited的设置不能放在的设置不能放在DFS(int v,int visited)方法中，否则反复调方法中，否则反复调用时，会改变已得到的访问标志。用时，会改变已得到的访问标志。深度优先搜索遍历图的算法中用
46、到两个主要操作，深度优先搜索遍历图的算法中用到两个主要操作，一是找一个结点的一是找一个结点的第一个邻接顶点第一个邻接顶点，二是找这个，二是找这个顶点的顶点的下一个邻接顶点下一个邻接顶点。时间代价时间代价l邻接矩阵作存储结构邻接矩阵作存储结构深度优先搜索的时间代价是深度优先搜索的时间代价是O(|V|)，遍历所有，遍历所有顶点的时间复杂度为顶点的时间复杂度为O(|V|2)，其中，其中|V|是图中顶是图中顶点的个数，对图中每个顶点最多只调用一次点的个数，对图中每个顶点最多只调用一次DFS()。l邻接表作存储结构邻接表作存储结构深度优先搜索的时间代价为深度优先搜索的时间代价为O(|V|+|E|)，遍历
47、边，遍历边所花的时间为所花的时间为O(|E|)，|E|是图中的边数，遍历是图中的边数，遍历每个顶点的次数最多为每个顶点的次数最多为1次。次。6.3.2 广度优先搜索广度优先搜索广度优先搜索的广度优先搜索的过程过程如下：如下：它首先将起始顶点作为候选顶点，访问候选它首先将起始顶点作为候选顶点，访问候选顶点；与候选顶点相邻接的尚未被访问的所有顶顶点；与候选顶点相邻接的尚未被访问的所有顶点又作为下一批候选顶点，继续这个过程，访问点又作为下一批候选顶点，继续这个过程，访问下一个候选顶点，与该候选顶点相邻接的尚未被下一个候选顶点，与该候选顶点相邻接的尚未被访问的所有顶点再作为下一批的候选顶点，直到访问的
48、所有顶点再作为下一批的候选顶点，直到访问完图中的所有顶点。访问完图中的所有顶点。例：例：仍以图仍以图6.12(a)为例，对它进行广度优先搜索为例，对它进行广度优先搜索它的一个它的一个访问序列访问序列为：为：v1v2v3v4v5v6v7v814532768(a)无向图无向图231451671122334455667788283838284576(b)邻接表邻接表从例中可以看出，广度优先搜索过程中，先入队列的顶点从例中可以看出，广度优先搜索过程中，先入队列的顶点将先被访问，顶点入队列顺序依赖于它在图的邻接表中的将先被访问，顶点入队列顺序依赖于它在图的邻接表中的次序次序及相应的及相应的选择算法选择算
49、法，因此，与深度优先搜索一样，广，因此，与深度优先搜索一样，广度优先搜索序列可能不唯一，但当邻接表及入队列算法确度优先搜索序列可能不唯一，但当邻接表及入队列算法确定下来后，这个顺序就确定了。定下来后，这个顺序就确定了。下面是图下面是图6.12(a)的另一种广度优先搜索结果，当然使用的的另一种广度优先搜索结果，当然使用的邻接表不同于图邻接表不同于图6.12(b)：v1v3v2v7v6v5v4v8选择不同的起始顶点，广度优先搜索的序列也会有变化，选择不同的起始顶点，广度优先搜索的序列也会有变化，例如从例如从v2开始的广度优先搜索序列为：开始的广度优先搜索序列为：v2v1v4v5v3v8v6v7/图
50、的广度优先遍历图的广度优先遍历/template void Graph:BFS(int v)int*visited=new intCurrentVtxNum;/定义及初定义及初始化始化visitedfor(int i=0;iCurrentVtxNum;i+)visitedi=0;visite(v);/访问顶点访问顶点vvisitedv=1;/将将visitedv置为置为1，表示已经访问过，表示已经访问过Queue q;/初始化队列初始化队列qq.EnQueue(v);/将顶点将顶点v入队列入队列while(!q.IsEmpty()/若若q不为空不为空v=q.DeQueue();/出队列出队列i
