【数据结构与算法】图(Graph)

文章目录

• 图的逻辑结构
• • 一.图的定义
  • 二.图的基本概念和术语
• 图的存储结构
• • 一.邻接矩阵（数组）
  • 二.邻接表（链式）
  • 三.十字链表
  • 四.邻接多重表
  • 五.边集数组
• 图的遍历
• • 一.深度优先遍历
  • 二.广度优先遍历
  • 三.图的遍历与图的连通性

图的逻辑结构

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

一.图的定义

图(Graph)是由顶点的有穷非空集合V ( G )和顶点之间边的**有穷集合E ( G ) **组成的数据结构，通常表示为: G = ( V , E )，其中，G表示个图，V 是图G中顶点的集合，E 是图G 中边的集合。若V = { v 1 , v 2 , . . . , v n } ，则用∣ V ∣表示图G中顶点的个数，也称图G 的阶，E = { ( u , v ) ∣ u ∈ V , v ∈ V } ，用∣ E ∣ 表示图G中边的条数。

注意:线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

• 顶点（vertex）：图中的元素；

• 边（edge）：图中的顶点与其他任意顶点建立连接的关系；

• 关联/依附：边/弧与顶点之间的关系。

• 邻接顶点： 有边/弧相连的两个顶点之间的关系。存在(u_i,v_j)，则称u_i和v_j互为邻接点，并称边 (u,v) 依附于顶点 u 和 v；存在<u,v> ，则称顶点 u 邻接到 v，顶点 v 邻接自顶点 u，并称<u,v>与顶点 u 和顶点 v 相关联。

• 顶点的度： 顶点 v 的度是指与它相关联的边的条数，记作deg(v)。在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点 v 的入度是以 v 为终点的有向边的条数，记作 indev(v) ;顶点 v 的出度是以 v 为起始点的有向边的条数，记作 outdev(v)。因此：dev(v) = indev(v) + outdev(v)。注意：对于无向图，顶点的度等于该顶点的入度和出度，即 dev(v) = indev(v) = outdev(v)。

  

• 路径： 接续的边构成的顶点序列。 在图 G = (V， E) 中，若从顶点 vi 出发有一组边使其可到达顶点 vj，则称顶点 vi 到顶点 vj 的顶点序列为从顶点 vi 到顶点 vj 的路径。

• 路径长度： 对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。

• 简单路径与回路： 若路径上各顶点 v1，v2，v3，…，vm 均不重复，则称这样的路径为简单路径。若路径上第一个顶点 v1 和最后一个顶点 vm 重合，则称这样的路径为回路或环。

• 简单环：除路径起点和终点相同外，其余顶点均不相同的路径。

• 距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷(∞)。
• 一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

二.图的基本概念和术语

图的分类

图有多种类型，包括有向图、无向图、简单图、多重图等

【无向图】

若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联。

图(b)所示的无向图G2可表示为

G_2 = ( V 2 , E 2 )

V_2 = { 1 , 2 , 3 , 4 }

E_2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

【有向图】

若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。

图(a)所示的有向图G_1可表示为

G_1 = (V_1,E_1)

V_1={1,2,3}

E_1={<1,2>,<2,1>,<2,3>}

【完全图】

简单来说，完全图就是任意两个点都有一条边相连。

【简单图】

一个图G若满足:①不存在重复边;②不存在顶点到自身的边，则称图G为简单图。上图中G_1和G_2均为简单图。数据结构中仅讨论简单图。

【带权图（网)】

图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费，带权的图称为网。在带权图中，每条边都有一个权重（weight）（非负实数）。

【多重图】

图中某两个顶点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则称为多重图。多重图的定义和简单图是相对的。

【子图】

设图G = {V, E}和图G1 = {V_1，E_1}，若V_1属于V且E_1属于E，则称G_1是G的子图。

【稠密图、稀疏图】

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足|E| < |V|log|V|时，可以G视为稀疏图。

【连通图】

在无向图中，若从顶点 v1 到顶点 v2 有路径，则称顶点 v1 与顶点 v2 是连通的。若图中任意一对顶点都是连通的，则称此图为连通图。否则称为非连通图。

无向图中的极大连通子图称为连通分量。极大连通子图的意思是：该子图是G的连通图，将G的任何不在该子图中的顶点加入，子图不在连通。

若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图。

【强连通图】

在有向图中，若在每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径，也存在一条从 vj 到 vi 的路径，则称此图是强连通图。

有向图中的极大强连通子图称为有向图的强连通分量，图G_1的强连通分量如下图所示。

注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

【极小连通子图】

该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。极小连通子图可以包含所有顶点，可以不。

【生成树、生成森林】

连通图的生成树是包含无向图G中全部顶点的一个极小连通子图。若图中顶点数为n,则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

在非连通图中，各个连通分量的生成树的集合构成了生成森林。

注意:包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。

图的存储结构

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，要么会造成很多存储单元的浪费，要么又带来操作的不便。因此，对于图来说，如何对它实现物理存储是个难题，接下来我们介绍五种不同的存储结构。

一.邻接矩阵（数组）

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图G有n个顶点，则邻接矩阵A是一个n ∗ n的方阵，定义为:

1. 下图是一个【无向图和它的邻接矩阵】：

可以看出:

• 无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的)。 因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
• 对于无向图，邻接矩阵的第 i行(或第 i列)非零元素(或非∞ 元素)的个数正好是第 i个顶点的度TD(v_i)。比如顶点 v_1的度就是1+0+1+0=2。
• 求顶点v_i的所有邻接点就是将矩阵中第i行元素扫描一遍， A [ i ] [ j ] 为 1就是邻接点。
• 完全图的邻接矩阵中，对角元素为0，其余1。

2. 下图是一个【有向图和它的邻接矩阵】：

可以看出:

• 主对角线上数值依然为0。但因为是有向图，所以此矩阵并不对称。

• 有向图讲究入度与出度。第 i行含义：以结点v_i为尾的弧（即出度边）；第i列含义：以结点v_i为头的弧（即入度边）。

  顶点的出度=第 i 行元素之和

  顶点的入度=第 i 列元素之和

  顶点的度=第 i 行元素之和+第 i 列元素之和

• 与无向图同样的办法，判断顶点v_i到 v_j是否存在弧，只需要查找矩阵中A [ i ] [ j ] 是否为1即可。

3. 对于带权图而言,若顶点v_i和v_j之间有边相连，则邻接矩阵中对应项存放着该边对应的权值
   

下图是一个【带权图和它的邻接矩阵】：

邻接矩阵的实现

通过以上对无向图、有向图和网的描述，可定义出邻接矩阵的存储结构：

#define MVNum 100	//顶点数目的最大值
typedef char VertexType;	//设顶点的数据类型为字符型
typedef int EdgeType;	//假设边的权值类型为整型

typedef struct{
	VertexType Vexs[MVNum];	//顶点表
	ArcType arcs[MVNum][MVNum];	//邻接矩阵，边表
	int vexnum, arcnum;	//图的当前顶点数和弧数
}MGraph;

采用邻接矩阵表示法创建无向网

【算法思想】

1. 输入总顶点数和总边数
2. 依次输入点的信息存入顶点表中
3. 初始化邻接矩阵，使每个权值初始化为极大值。
4. 构造邻接矩阵

【算法实现】

//查找图中顶点的下标
int LocateVEX(AMGraph G,Vertex Type u){//图中查找顶点u，存在则返回顶点表中的下标；否则返回-1
    int i;
    for(i=0;i<G.vexnum;++i)
        if(u==G.vex[i])
            return i;
    return -1;
}

Status CreateUDN(AMGraph &G){//采用邻接矩阵法，创建无线网G
    cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
    for(i=0;i<G.vexnum;++i)
        cin>>G.vexs[i];//依次在顶点表中输入点的信息
    for(i=0;i<G.vexnum;++i)//初始化邻接矩阵
        for(j=0;G.vexnum;++j)
            G.arcs[i][j]=MaxInt;//边的权值均置为极大值
    
    //构造邻接矩阵
    for(k=0;k<G.arcnum;++k){
        cin>>v1>>v2>>w;//输入一条边所依附的顶点即边的权值
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);//确定v1和v2在G中的位置
        G.arcs[i][j]=w;//边<v1,v2>的权值置为w
        G.arcs[j][i]=G.arcs[i][j];//置<v1,v2>的对称边<v2,v1>的权值为w
    }
    return OK;
}

对上面无向网稍作修改可以创建无向图和有向网：

• 无向图：1.初始化邻接矩阵时，w均为0 2.构造邻接矩阵时，w为1
• 有向网：邻接矩阵是非对称矩阵：仅为G.arcs[i][j]赋值，无需为G.arcs[j][i]赋值。

①在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)。
②当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0和1的枚举类型。
③无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
④邻接矩阵表示法的空间复杂度为O(n^2)， 其中n为图的顶点数 |V|。
⑤ 用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
⑥ 稠密图适合使用邻接矩阵的存储表示。

二.邻接表（链式）

当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：

而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
所谓邻接表，是指对图G GG中的每个顶点v i v_iv**i​建立一个单链表，第i ii个单链表中的结点表示依附于顶点v i v_iv**i​ 的边(对于有向图则是以顶点v i v_iv**i​为尾的弧)，这个单链表就称为顶点v i v_iv**i​的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点:顶点表结点和边表结点，如下图所示。

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。
无向图的邻接表的实例如下图所示。

有向图的邻接表的实例如下图所示。

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。

图的邻接表存储结构定义如下：

#define MAXVEX 100	//图中顶点数目的最大值
type char VertexType;	//顶点类型应由用户定义
typedef int EdgeType;	//边上的权值类型应由用户定义
/*边表结点*/
typedef struct EdgeNode{
	int adjvex;	//该弧所指向的顶点的下标或者位置
	EdgeType weight;	//权值，对于非网图可以不需要
	struct EdgeNode *next;	//指向下一个邻接点
}EdgeNode;

/*顶点表结点*/
typedef struct VertexNode{
	Vertex data;	//顶点域，存储顶点信息
	EdgeNode *firstedge	//边表头指针
}VertexNode, AdjList[MAXVEX];

/*邻接表*/
typedef struct{
	AdjList adjList;
	int numVertexes, numEdges;	//图中当前顶点数和边数
}
123456789101112131415161718192021

图的邻接表存储方法具有以下特点

1. 若G GG为无向图，则所需的存储空间为O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V|+2|E|)O(∣V∣+2∣E∣)；若G GG为有向图,则所需的存储空间为O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|)O(∣V∣+∣E∣)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次
2. 对于稀疏图，采用邻接表表示将极大地节省存储空间。
3. 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O ( n ) O(n)O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
4. 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此,也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然,这实际上与邻接表存储方式是类似的。
5. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

三.十字链表

十字链表是有向图的一种链式存储结构。
对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的，就是把它们整合在一起。这就是我们现在要介绍的有向图的一种存储方法：十字链表(Orthogonal List)。
我们重新定义顶点表结点结构如下表所示。

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout 表示出边表头指针，指向该顶点的出边表中的第一个结点。
重新定义的边表结点结构如下表所示。

其中tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

接下来通过一个例子详细介绍十字链表的结构。
如下图所示，顶点依然是存入一个一维数组{ V 0 , V 1 , V 2 , V 3 } {V_0,V_1,V_2,V_3}{V0​,V1​,V2​,V3​}，实线箭头指针的图示完全与的邻接表的结构相同。就以顶点V 0 V_0V0​来说，firstout 指向的是出边表中的第一个结点V 3 V_3V3​。所以V 0 V_0V0​边表结点的h e a d v e x = 3 headvex=3headvex=3，而tailvex就是当前顶点V 0 V_0V0​的下标0，由于V 0 V_0V0​只有一个出边顶点，所以headlink和taillink都是空。

我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于V 0 V_0V0​来说，它有两个顶点V 1 V_1V1​和V 2 V_2V2​的入边。因此V 0 V_0V0​的firstin指向顶点V 1 V_1V1​的边表结点中headvex为0的结点，如上图右图中的①。接着由入边结点的headlink指向下一个入边顶点V 2 V_2V2​，如图中的②。对于顶点V 1 V_1V1​,它有一个入边顶点V 2 V_2V2​，所以它的firstin指向顶点V 2 V_2V2​的边表结点中headvex为1的结点，如图中的③。顶点V 2 V_2V2​和V 3 V_3V3​也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起， 这样既容易找到以V 1 V_1V1为尾的弧，也容易找到以V 1 V_1V1为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中

四.邻接多重表

邻接多重表是无向图的另一种链式存储结构。
在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。比如下图中，若要删除左图的( V 0 , V 2 ) (V_0,V_2)(V0​,V2​) 这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较烦琐的。

重新定义的边表结点结构如下表所示。

其中ivex和jvex是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点ivex的下一条边，jlink 指向依附顶点jvex的下一条边。这就是邻接多重表结构。

每个顶点也用一一个结点表示，它由如下所示的两个域组成。

其中，data 域存储该顶点的相关信息，firstedge 域指示第一条依附于该顶点的边。

我们来看结构示意图的绘制过程，理解了它是如何连线的，也就理解邻接多重表构造原理了。如下图7所示，左图告诉我们它有4个顶点和5条边，显然，我们就应该先将4个顶点和5条边的边表结点画出来。

我们开始连线，如图，首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同,这很好理解。接着，由于顶点V 0 V_0V0​的( V 0 , V 1 ) (V_0,V_1)(V0​,V1​) 边的邻边有( V 0 , V 3 ) (V_0,V_3)(V0​,V3​) 和( V 0 , V 2 ) (V_0,V_2)(V0​,V2​)。 因此⑤⑥的连线就是满足指向下一条依附于顶点V 0 V_0V0​的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。同样的道理，连线⑦就是指( V 1 , V 0 ) (V_1,V_0)(V1​,V0​) 这条边，它是相当于顶点V 1 V_1V1​指向( V 1 , V 2 ) (V_1,V_2)(V1​,V2​) 边后的下一条。V 2 V_2V2​有三条边依附，所以在③之后就有了⑧⑨。连线④的就是顶点V 3 V_3V3​在连线④之后的下一条边。 左图一共有5条边，所以右图有10条连线，完全符合预期。

到这里，可以明显的看出，邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。 这样对边的操作就方便多了，若要删除左图的( V 0 , V 2 ) (V_0,V_2)(V0,V2) 这条边，只需要将右图的⑥⑨的链接指向改为NULL即可。

五.边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、 终点下标(end)和权(weight)组成，如下图所示。显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。

图的遍历

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次， 这一过程就叫做图的遍历(Traversing Graph)。
对于图的遍历来，通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

一.深度优先遍历

深度优先搜索（Depth First Search）简称 DFS，是遍历图存储结构的一种算法，既适用于无向图，也适用于有向图。

首先通过一个样例，演示一下深度优先搜索算法是如何实现图的遍历的：

思路：

• 使用一个状态标记数组，数组中有 false 和 true 两种状态，false 表示该顶点未访问过，true 表示该顶点已经访问过了，没访问一个顶点，就将状态数组中其下标对应的位置标记为 true。
• 使用递归的方式进行深度遍历。

DFS代码：

void _DFS(size_t srci, vector<bool>& visited)
{
	// 访问此顶点元素，并将其状态置为true
	cout << "[" << srci << "]" << _vertexs[srci] << "  ";
	visited[srci] = true;

	// 找一个srci的未访问过的邻接顶点去往深度遍历
	for (size_t i = 0;i < _vertexs.size();++i)
	{
		if (_matrix[srci][i] != MAX_W && visited[i] == false)
		{
			_DFS(i, visited);
		}
	}
}

void DFS(const V& src)
{
	// 获取开始顶点下标，设置好标记数组
	size_t srci = GetVertexIndex(src);
	vector<bool> visited(_vertexs.size(), false);
	// 进入子函数，进行递归遍历
	_DFS(srci, visited);
}

图的遍历有许多应用，比如求联通分量、欧拉回路、生成树、DAG的判定、DAG的根、桥边、关节点等的计算都可以通过遍历来进行。

二.广度优先遍历

广度优先搜索（Breadth First Search）简称 BFS，是遍历图存储结构的一种算法，既适用于无向图，也适用于有向图。

首先通过一个样例，演示一下广度优先搜索算法是如何实现图的遍历的：

思路：

• 使用一个数组来标记各个顶点的状态，数组中有 false 和 true 两种状态，false 表示该顶点还未入队列，true 表示该顶点已经进入队列了。每当顶点入队列时，就将该顶点标记为 true，防止重复访问。
• 一个顶点出队列时，就将该顶点的未入队列的邻接顶点进入队列，并将进入队列的顶点的状态置为 true。
• 队列为空时，代表图已经访问完毕。
  

BFS代码： 下列代码遍历时采用一层一层遍历的方式

void BFS(const V& src)
{
	// 获取开始顶点下标
	size_t srci = GetVertexIndex(src);
	size_t n = _vertexs.size();

	// 队列和标记数组，使用false进行初始化
	queue<int> q;
	vector<bool> visited(n, false);

	// 首先将开始顶点入队列，并将其状态置为true
	q.push(srci);
	visited[srci] = true;
	int levelSize = 1;

	int count = 0;
	// 队列为空，则遍历结束
	while (!q.empty())
	{
		cout << "第" << count++ << "层: ";
		for (size_t k = 0;k < levelSize;++k)
		{
			// 访问队头元素并将其从队列中删除
			int front = q.front();
			q.pop();
			cout << "[" << front << "]" << _vertexs[front] << " ";

			// 将该顶点未访问过的邻接顶点入队列，并标记其状态
			for (size_t i = 0;i < n;++i)
			{
				if (_matrix[front][i] != MAX_W && visited[i] == false)
				{
					q.push(i);
					visited[i] = true;
				}
			}
		}
		levelSize = q.size();
		cout << endl;
	}
}

三.图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。
对于无向图来说，若无向图是连通的，则从任一结点出发， 仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
故在BFSTraverse ()或DFSTraverse ()中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点。对于无向图，上述两个函数调用BFS (G,i)或DFS(G,i)的次数等于该图的连通分量数；而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量，非强连通分量一次调用BFS (G, i)或DFS (G, i)无法访问到该连通分量的所有顶点。
如下图所示为有向图的非强连通分量。