数据结构（十）----图

一.图的概念

1.图的定义

2.图的类别

3.图的性质

4.几种特殊形态的图

二.图的存储结构

1.邻接矩阵（顺序存储）

2.邻接表（顺序+链式存储）

3.十字链表

4.邻接多重表

四.图的遍历

1.广度优先遍历（BFS）

•广度优先生成树

•广度优先生成森林

2.深度优先遍历（DFS）

•深度优先生成树

•深度优先生成森林

一.图的概念

1.图的定义

图G（Graph）由 顶点集V（vertex） 和 边集E（edge） 组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V={v1,…,vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u,v) | u $\epsilon$ V,v $\epsilon$ V}，用|E|表示图G中边的条数。

注：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集（边集可以为空）。

2.图的类别

•无向图：

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

上图中用集合的方式表示：

•有向图：

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

上图用集合的方式表示：

•简单图：

简单图中 ①：不存在重复边；② 不存在顶点到自身的边。

注：之后探讨的都是简单图

•多重图：

图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。

3.图的性质

•图的度：

对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。

在具有n个顶点、e条边的无向图中：

无向图的全部顶点的度的和等于边数的2倍，因为每一条边会给连接的顶点分别提供一个度。

对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v)；出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)。例如下图中A的出度为4(OD)，入度为1(ID)，所以他的度为5（TD）

在具有n个顶点、e条边的有向图中：

因为一条边会给一端的顶点贡献出度，给另一端的顶点贡献入度。

•顶点之间的关系描述：

路径----顶点 $v_{p}$ 到顶点 $v_{q}$ 之间的一条路径，即顶点序列。在无向图中路径的方向是没有限制的，在有向图中路径的方向必须和弧的方向一致。

回路----第一个顶点和最后一个顶点相同的路径称为回路或环。

简单路径----在路径序列中，顶点不重复出现的路径称为简单路径。

简单回路----除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

路径长度---路径上边的数目。

点到点的距离----从顶点u出发到顶点v的最短路径若存在，，则此路径的长度称为从u到v的距离。若从u到v根不不存在路径，则记该距离为无穷( $\bowtie$ )。

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。在无向图中若图中任意两个顶点都是连通的，则称图为连通图，否则称为非连通图。

常见考点：

对于n个顶点的无向图G，若G是连通图，则最少有n-1条边。若G是非连通图，则最多可能有 $C_{n-1}^{2}$ 条边。

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若有向图中任何一对顶点都是强连通的，则称此图为强连通图。

常见考点：

对于n个顶点的有向图G，若G是强连通图，则最少有n条边(形成回路)。

•子图：

子图中无向图和有向图的概念相同，这里以无向图为例：

设有两个图G=(V,E)和G'=(V',E')，若V'是V的子集，且E'是E的子集，则称G'是G的子图。

并非任意挑几个点、几条边都能构成子图：

若有满足V(G’)= V(G)的子图G'，即子图中包含了原图的所有顶点，则称其为G的生成子图：

•连通分量：

无向图的极大连通子图称为连通分量：

子图必须连通且包含尽可能多的顶点和边。

有向图中的极大强连通子图称为有向图的强连通分量：

子图必须强连通并且保留尽可能多的边。

注：下图中F与A,B,C,D,E这几个顶点是不强连通的，因为其他顶点有到F的边，但是F没有到其他顶点的边。

•生成树：

连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能少，但要保证连通）。

可以观察到，若图中顶点数为n，则它的生成树含n-1条边。对生成树而言，若砍去它的一条边
则会变成非连通图，若加上一条边则会形成一个回路。

•生成森林：

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

若无向图是非连通图，那么可以把他分为几个连通分量，这些连通分量都是极大连通子图，之后再把这些连通分量生成对应的生成树，就可以得到非连通图的生成森林。

•边的权、带权图/网：

边的权----在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网----边上带有权值的图称为带权图，也称网。

带权路径长度----当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

4.几种特殊形态的图

无向完全图----无向图中任意两个顶点之间都存在边。

有向完全图----有向图中任意两个顶点之间都存在方向相反的两条弧。

若有向图的顶点|V|=n,则边的数目为：

$|E| \epsilon [0,2C_{n}^{2}]=[0,n(n-1)]$

稀疏图----边数很少的图。

稠密图----边数很多的图。

没有绝对的界限，一般来说|E| < |V| loglV|时，可以将G视为稀疏图。

生成树----不存在回路，且连通的无向图。n个顶点的图，必有n-1条边，若|E|>n-1，则一定有回路。

有向树----一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

常见考点总结：

二.图的存储结构

1.邻接矩阵（顺序存储）

对于无向图而言，若A和B之间有一条边，则在邻接矩阵中会对应两个1。若没有边，则在邻接矩阵中表示为0。

对于有向图而言，每一条弧只会对应一个1，例如，A到B的弧对应邻接矩阵的1，B到A没有弧对应邻接矩阵的0。

#define MaxVertexNum 100    //顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum];    //顶点表，顶点的数组下标和邻接矩阵的行和列是对应的
    int Edge[MaxVertexNum][MaxVertexNum];    //邻接矩阵，边表
    int vexnum arcnum;    //图的当前顶点数和边数/弧数
} MGraph;

如何根据邻接矩阵求某一顶点的入度，出度呢？

对于无向图而言，可以遍历顶点所对应的行和列，行或列中1的个数就是顶点的度，即:

第 i 个结点的度 = 第 i 行(或第 i 列)的非零元素个数。

例如B对应的行1的个数是3，对应的列1的个数也是3，那么B的度就是3。

遍历行或列，时间复杂度为O(n)，或者说O( |v| )（顶点个数）

对于有向图而言，求顶点的出度，遍历行，求顶点的入度，遍历列：

第 i 个结点的出度=第 i 行的非零元素个数

第 i 个结点的入度=第 i 列的非零元素个数

第 i 个结点的度=第 i 行、第 i 列的非零元素个数之和

时间复杂度也为O(|v|)

设图的邻接矩阵为A(矩阵元素为0/1)，则A^n的元素 $A^{n}$ [i] [j]等于由顶点 i 到顶点 j 的长度为 n 的路径的数目。

例如下图，若两个矩阵相乘，则第1行第4列的元素的等式如下图所示(矩阵的第1行与第4列分别相乘再相加)，其含义用 $a_{1,2}a_{2,4}$ 举例： $a_{1,2}$ 为1表示A到B之间有边， $a_{2,4}$ 为1表示B到D之间有边，所以可以找到一条路径:A-->B,B-->D。

所以 $A^{2}=[1][4]=1$ 的意思为从A到D，路径长度为2，只能找到1条符合条件的路径：

A-->B,B-->D

同理， $A^{3}$ 得到的矩阵如下，可以得出从A到B长度为3的路径有3条，从A到D长度为3的路径有1条......

若用邻接矩阵存储带权图（网），那么只需要在邻接矩阵对应位置填入边的权值即可。

注：一些带权图中会把自己指向自己的边设为0，所以邻接矩阵中的0或∞都表示与之对应的两个顶点之间不存在边。

#define MaxVertexNum 100    //顶点数目的最大值
#define INFINITY 最大的int值    //宏定义常量“无穷"
typedef char VertexType;    //顶点的数据类型
typedef int EdgeType;    //带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];    //顶点
    EdgeType Edge[MaxVertexNum] [MaxVertexNum];    //边的权
    int vexnum,arcnum;    //图的当前顶点数和弧数
}MGraph;

邻接矩阵的性能：

若有n个顶点，则需要O(n)的存储空间存储一维数组，同时需要n*n的数组存储边的信息，所以需要O(n^2)的存储空间，所以保留阶数更高的部分，邻接矩阵的空间复杂度为O(n^2)，或者说O(|V|^2) -- 只和顶点数相关，和实际的边数无关。

若某个图中顶点数较多，边数很少，那么邻接矩阵的很多空间将被浪费，所以邻接矩阵适合存储稠密图。无向图的邻接矩阵是对称矩阵，可以压缩存储(只存储上三角区/下三角区)。

邻接矩阵的缺点：空间复杂度高，不适合存储稀疏图。

2.邻接表（顺序+链式存储）

如下图所示，在无向图中，边的数据是有冗余的，边结点的数目是实际边的数目的2倍。例如0号结点(A)指向1号结点(B)的边和1号结点(B)指向指向0号结点(A)的边是同一条边。

所以无向图中边结点的数目为2|E|，整体空间复杂度为O(|V|+2|E|)，而有向图中没有这样的问题，边结点的数量是|E|，整体空间复杂度为O(|V| + |E|)。

//"顶点"
typedef struct VNode{
    VertexType data;    //顶点信息
    ArcNode *first    //第一条边/弧
}VNode ,AdjList [MaxVertexNum];

//用邻接表存储的图
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;    //图的当前顶点数和弧数
}ALGraph;

//"边/弧"
typedef struct ArcNode{
    int adjvex;    //边/弧指向哪个顶点
    struct ArcNode *next;    //指向下一条弧的指针
    //InfoType info;    //边权值
}ArcNode;

在邻接表中，怎么求一个结点的度呢？

对于无向图而言，只需要遍历结点对应的边链表即可，有多少边结点就有多少度。

对于有向图而言，需要探讨入度和出度，对于出度，只需要遍历结点对应的边链表即可，但是对于入度，需要将所有的边链表依次遍历，找到指向该结点的边。

例如，对于A结点而言，需要依次遍历所有边链表，找到指向0号结点的边。

图的邻接表表示方式并不唯一，即边在边链表中的顺序是随意的。而对于邻接矩阵，只要确定了顶点编号，那么图的邻接矩阵表示方式就是唯一的。

邻接矩阵和邻接表的对比：

3.十字链表

由于邻接表中对于入度的计算不方便，所以对邻接表进一步优化，即十字链表和邻接多重表，十字链表用于存储有向图，邻接多重表用于存储无向图。

以A结点为例，

A指向的结点，从A结点绿色部分开始找，A结点绿色部分指向的第一个弧结点的信息为弧尾顶点编号为0(A)，弧头顶点编号为1(B)的弧结点，即A--->B的弧。

从这一弧结点绿色部分指向的弧结点为弧尾相同的另一条弧，即同样从A结点出发的弧，即A--->C的弧。

而指向A结点的弧，从A结点橙色部分开始找，A结点橙色部分指向的第一个弧结点的信息为弧尾顶点编号为2，弧头顶点编号为0的弧结点，即C--->A的弧。

顺着弧结点的橙色指针往后找的话，就能找到下一条指向A结点的弧，即D-->A的弧。除了C--->A与D--->A的弧指向A结点外，没有其他弧指向A了，所以该弧结点的橙色指针为^(空)

十字链表法的空间复杂度为O(|V|+|E|)，空间复杂度与邻接表相同，为O(|V|+|E|)，不需要像邻接矩阵那样消耗O(|V|^2)的存储空间。

十字链表法解决了邻接表中找入边不方便的问题，但是十字链表法只能用于有向图。

4.邻接多重表

用邻接矩阵存储无向图，空间复杂度过高：O(|V|^2)，而用邻接表存储无向图的话，每一条边会对应两个弧结点，即存在数据冗余，删除顶点、删除边等操作时间复杂度高。可以用邻接多重表进行优化。

邻接多重表和十字链表的结构很相似，以A举例：

A的firstedge指向的是与A顶点相连的第一条边，即A和B相连的边，随着该边结点的橙色部分继续往后找，就能找到与A顶点相连的下一条边，即A和D相连的边。除了这两条边外，没有其他的边与A相连了，所以iLink为^(空)。

由于是无向图，所以 i，j 在的位置是随意的，假设i，j此时分别为A，B，那么与A相连的下一条边由橙色部分指向，与B相连的下一条边由绿色部分指向，反过来同理。

可以看到，每一条边只会对应一个边结点数据，不会出现冗余的信息。当要删除某个结点或某条边时，只需要删除对应该结点/边的信息，修改相应指针即可。

例如删除A，B之间的边，那么删除该边结点后，修改与A相连的第一条边和与B相连的第一条边的指针即可。

删除E结点，需要将与E相连的边全部删除，同时修改相应指针。

邻接多重表只能用于存储无向图，每条边只对应一份数据，空间复杂度为O(|V|+|E|)，删除边，删除结点很方便。

总结：

十字链表法只能用于存储有向图，他解决了邻接矩阵中空间复杂度较高（O(|v|^2)）的问题，同时也解决了邻接表存储有向图时，找入边必须遍历，不太方便的问题。

邻接多重表只能用于存储无向图，他既解决了邻接矩阵空间复杂度较高的问题，也解决了邻接表中每一条边对应两份信息，删除结点或边都不方便的问题。

三.图的基本操作

1.Adjacent(G,x,y)：判断图G是否存在边<x,y>或(x,y)。

对于无向图和有向图，判断两点之间是否有边，以B，D为例：

若是邻接矩阵，只需要判断B,D对应数值是否为1即可。时间复杂度为O(1)。

若是邻接表，需要查看B的边结点中有没有D的编号，最好的情况是目标结点的编号刚好是第一个边结点，时间复杂度为O(1)。与B连接的边最多有v-1条，所以最坏情况就是遍历完所有的边，都找不到目标结点的编号，最坏时间复杂度为O(|V|)。

2. Neighbors(G,x)：列出图G中与结点x邻接的边。

无向图：

对于邻接矩阵，想要找到某结点x邻接的边，只需要找到该结点对应的行和列进行遍历即可。时间复杂度为O(|V|)

对于邻接表，只需要遍历该点对应的边结点即可。时间复杂度为O(1)~O(|V|)

有向图：

对于邻接矩阵，若想找到某结点的出边，遍历对应行，若想找到某结点的入边，遍历对应列。时间复杂度为O(v)。

对于邻接表，找出边，遍历对应的边结点，时间复杂度为O(1)~O(v)，找入边，则需要遍历所有的边结点，因为遍历完所有的边结点才能得到有多少边指向该结点，时间复杂度为O(|E|)，E表示图中所有的边。

3.InsertVertex(G,x)：在图G中插入顶点x。

对于无向图和有向图：

若采用邻接矩阵，只需要在数组中写入新的元素即可，时间复杂度为O(1)。

若采用邻接表，也只需要在存储结点的数组末尾插入新结点。时间复杂度为O(1)。

4.DeleteVertex(G,x)：从图G中删除顶点x。

无向图：

对于邻接矩阵，只需要删除点x的行和列，并在数组中将x置空，该操作的时间复杂度为O(|V|)。

对于邻接表，除了删除x连接的边结点，还需要在和他相连的顶点的边表中找到指向点x的边的信息，将这些信息删除。

若想删除的结点没有连接任何边，那么删除该结点只需要O(1)的时间复杂度，若想删除的结点连接了其他所有结点，并且这一点连接在所有结点边表的末尾，这就需要遍历所有的边，最坏时间复杂度为O(|E|)。

有向图：

对于邻接矩阵，其操作和无向图相同，时间复杂度为O(|V|)。

对于邻接表，若删除某结点，需要将其对应的出边和入边一起删除，删除出边，只需要删除对应的边结点，时间复杂度为O(1)~O(|V|)，删除入边，则需要遍历所有的边，才能找到指向该结点的边并将其删除，时间复杂度为O(|E|)

5.AddEdge(G,x,y)：若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边

无向图和有向图：

对于邻接矩阵，只需要将两点对应的数值改为1，时间复杂度为O(1)。

对于邻接表，若想在两点间添加一条边，需要在两点的边表末尾添加边结点，时间复杂度为O(1)~O(|V|)。

其实，采用头插法能将时间复杂度降到O(1)，就是将新的边的信息插入到边表的头部。

6.FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点
或图中不存在x，则返回-1。

无向图：

对于邻接矩阵，从左到右扫描该结点对应的行，找到第一个“1”，就找到了该结点的第一个邻接点。时间复杂度为O(1)~O(|V|)。

对于邻接表，只需要找到与其相邻的边结点中的第一个结点，时间复杂度为O(1)。

有向图：

对于邻接矩阵，找出边，从左到右遍历行，找入边，从左到右遍历列，时间复杂度为O(1)~O(|V|)。

对于邻接表，找出边的操作和无向图相同，时间复杂度为O(1)，找入边则需要遍历所有的边，最好的情况是遍历的第一个元素就是指向当前结点的一条边，时间复杂度为O(1)。

最坏的情况是，遍历完所有的边都找不到指向当前结点的边，时间复杂度为O(|E|)。

7.NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

对于邻接矩阵，若想找到一个邻接点后的下一个邻接点，只需要在遍历到第一个邻接点后继续往后遍历即可，时间复杂度为O(1)~O(|V|)。

对于邻接表，只需要找到与该结点相连的第2个边结点即可，时间复杂度为O(1)。

8.Get_edge_value(G,x,y):获取图G中边(x,y)或<x,y>对应的权值。Set_edge_value(G,x,y,v):设置图G中迈(x,y)或<x,y>对应的权值为v。

这两种操作主要的时间开销在于找边/弧，所以时间复杂度与判断两点间是否有边一样：

对于邻接矩阵，时间复杂度为O(1)，对于邻接表，时间复杂度为O(1)~O(|V|)。

四.图的遍历

1.广度优先遍历（BFS）

树是一种特殊的图，所以图的广度优先遍历和树的广度优先遍历类似。如下图所示，从2出发，找到与他相邻的结点，即1，6，再遍历与1，6相邻的结点，以此类推。

图的广度优先遍历与树的广度优先遍历的区别：

•对于树而言，广度优先遍历的关键是找到该结点的孩子，对于图而言，则是找到与该结点相邻的结点。

•在树中，不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点。而对于图而言，搜索相邻的顶点时，有可能搜到已经访问过的顶点。为了防止这种情况，只需要给结点赋一个标记即可，若某个结点已经被访问过（标记过），那再访问到该结点时，跳过该结点即可。这就能保证每个点只被访问一次。

•在实现树的广度优先遍历（层序遍历）时，需要辅助队列：

① 若树非空，根结点入队。

② 若队列非空，队头元素出队并访问，同时将该元素的所有孩子入队。

③ 重复②直至队列为空。

所以，对于图的广度优先遍历，也可以设置辅助队列：

① 找到初始顶点，并标记为被访问过。

② 若队列不空，则让初始顶点出队，利用（FirstNeighbor(G,x)）找到第一个与顶点相邻的结点，并标记该结点已被访问过。利用（NextNeighbor(G,x)）找到下一个与顶点相邻的结点。直至找到与初始顶点相邻的所有结点，将这些点入队。

③ 重复②直至队列为空。

bool visited[MAX_VERTEX_NUM];    //访问标记数组

//广度优先遍历
void BFS(Graph G,int v){     //从顶点v出发，广度优先遍历图G
    visit(v);   //访问初始顶点v
    visited[v]=TRUE;    //对v做已访问标记
    Enqueue(Q,v);    //顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);    //顶点v出队列
        for(w=FirstNeighbor(G,v);    w>=0;    w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if( !visited [w]){    //w为v的尚未访问的邻接顶点
                visit(w);    //访问顶点w
                visited[w]=TRUE;//对w做已访问标记
                EnQueue(Q,w);//顶点w入队列
            }
    }
}

注：对于广度优先遍历而言，从某个结点出发找到相邻结点的顺序可能不同，但如果用的是邻接矩阵，一个图的邻接矩阵表示方式是唯一的，那么遍历某个结点的顺序就是固定的，例如下图，若想找到3号顶点的相邻点，那么其遍历顺序就是4，6，7（递增顺序）。

而用邻接表存储图，则某个结点的相邻点的遍历顺序可能不同：

总结：采用邻接表存储，广度优先遍历的遍历序列是不唯一的，采用邻接矩阵存储，广度优先遍历的遍历序列是唯一的。

若想实现非连通图的广度优先遍历，那么可以在使用完一次BFS后，检查是否还有未访问的结点，若有，则对另一个连通分量使用一次BFS即可。

bool visited[MAX_VERTEX_NUM];    //访问标记数组

void BFSTraverse(Graph G){     //对图G进行广度优先遍历                                        
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;    //访问标记数组初始化
    InitQueue(Q);    //初始化辅助队列Q
    for(i=0;i<G.vexnum;++i)    //从0号顶点开始遍历
        if(!visited[i])    //对每个连通分量调用一次BFS
            BFS(G,i);    //vi未访问过，从vi开始BFS
}

//广度优先遍历
void BFS(Graph G,int v){     //从顶点v出发，广度优先遍历图G
    visit(v);   //访问初始顶点v
    visited[v]=TRUE;    //对v做已访问标记
    Enqueue(Q,v);    //顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);    //顶点v出队列
        for(w=FirstNeighbor(G,v);    w>=0;    w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if( !visited [w]){    //w为v的尚未访问的邻接顶点
                visit(w);    //访问顶点w
                visited[w]=TRUE;//对w做已访问标记
                EnQueue(Q,w);//顶点w入队列
            }
    }
}

所以，对于一个无向图而言，调用BFS函数的次数= 连通分量数。

BFS的空间复杂度（最坏情况）：

若某结点与其他所有结点相邻，那么在访问1号结点时，就需要将其他所有结点入队，那么辅助队列的大小就是O(|V|)。

BFS的时间复杂度（最坏情况）：

若用邻接矩阵存储图，访问v个顶点需要O(|V|)的时间，并且需要查找与这个顶点相邻的所有边，即遍历该顶点对应的行，时间复杂度时O(|V|)，所以总共的时间复杂度为 $O(|V|^2)$ 。

若采用邻接表，访问v个顶点需要O(|V|)的时间，并且需要查找各个顶点相连接的边，无向图的边结点个数为2E，所以时间复杂度为O(2|E|)，即O(|E|)，总共时间复杂度为 $O(|V|+|E|)$ 。

这里的时间复杂度分析，并没有从代码出发，因为只考虑最深层循环的循环次数可能会出错。例如，访问一个所有结点都没有边相连的图，那么BFS的for循环执行0次，但是每个点都需要使用一次BFS，即每一次都要使用visit(v);时间开销实际为O(|V|)。

只需要记住广度优先算法和深度优先算法的时间开销主要来自于访问各个顶点，以及查找各个顶点相邻的边。将两者访问开销相加，就能得到总的时间复杂度。

•广度优先生成树

下图的红线表示的是，当某个顶点第一次访问时，是从哪一条边过去的，例如访问4号顶点，是从与3号相邻的边过去的。所以n个顶点，则访问完所有顶点后，被标红的线有n-1条。

当我们将其余的线去掉，这个图就变成了树，因为没有回路存在了，也就是广度优先生成树，这棵树是通过广度优先遍历的过程得来的。

若采用邻接表，邻接表的表示方式不同，广度优先生成树也不同，所以基于邻接表的广度优先生成树是不唯一的。若采用邻接矩阵，其广度优先生成树就是唯一的。

还有一个重要的知识点：

如下图所示，从2号顶点出发，由广度优先遍历得来的生成树一定是高度最小的以2为根的生成树。

•广度优先生成森林

对非连通图的广度优先遍历，可得到广度优先生成森林。

2.深度优先遍历（DFS）

树的深度优先遍历分为先根遍历和后根遍历，图的深度优先遍历与树的先根遍历类似，树的先根遍历过程如下：

void PreOrder(TreeNode *R){
    if(R!=NULL){
        visit(R);
        while(R还有下一个子树T)
            PreOrder(T);    //先根遍历下一棵子树
    }
}

下图的树的先根遍历序列为：1，2，5，6，3，4，7，8。

对于树而言，新找到的相邻结点一定为访问过的，对于图而言则不一定，所以也需要设置标记数组

bool visited[MAX_VERTEX_NUM];    //访问标记数组

//先访问初始结点，再访问与其相邻的其他结点，对其他结点依次再进行DFS
void DFS(Graph G,int v){    //从顶点v出发，深度优先遍历图G    
    visit(v);    //访问顶点v
    visited [v]=TRUE;    //    设为已访问结点
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visited[w]){    //w为u的尚未访问的邻接顶点
            DFS(G,w);
        }
}

执行过程如下：

从2号顶点出发，将2号顶点的visited[2]=TRUE；并且访问与之相邻的顶点。与之相邻的第一个顶点是1，所以DFS传入的参数是1。

在1号顶点的这层DFS中，将visited[1]=TRUE，并且访问与之相邻的顶点，由于2号顶点的visited[2]=TRUE;所以下一个与1相邻的点是5。

由于与5号结点相邻的点都被访问过，所以这一点的不会进入下一层DFS,执行完这一层的DFS后，返回上一层，即1号结点的DFS。

由于1号结点的最后一个邻接点5号结点已经被处理过，所以1号顶点的DFS执行结束，继续返回上一层DFS。

2号结点的第一个相邻点1号结点，已经处理完毕，所以现在访问其他与2号结点相邻的结点，即6号顶点。其余过程依次类推。

得到从2出发的深度遍历序列：2，1，5，6，3，4，7，8

如果是非连通图，则无法遍历完所有结点。所以和广度优先遍历相同，在进行一次DFS之后，在扫描一次数组，若该数组中某一顶点的visited[v]=FALSE，那么就从这一顶点出发，在执行DFS即可

bool visited[MAX VERTEX NUM];    //访问标记数组

void DFSTraverse(Graph G){     //对图G进行深度优先遍历  
    for(v=0;V<G.vexnum;++v)
        visited[v]=FALSE;    //初始化已访问标记数据
    for(v=0;v<G.vexnum;++V)    //本代码中是从v=0开始遍历
        if(!visited[v])
            DFS(G,v);
}

//深度优先遍历
void DFS(Graph G,int v){    //从顶点v出发，深度优先遍历图G    
    visit(v);    //访问顶点v
    visited [v]=TRUE;    //    设为已访问结点
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visited[w]){    //w为u的尚未访问的邻接顶点
            DFS(G,w);
        }
}

DFS的空间复杂度：

若从1号结点出发，进行深度优先遍历，那么DFS函数的递归调用深度和结点数相同，所以最坏时间复杂度是O(|V|)。

若从1号结点开始进行深度优先遍历，那么递归调用栈最多只有两层，所以只有常数级的空间复杂度，即O(1)。

注：DFS的空间复杂度主要来自于递归工作栈，而BFS的空间复杂度则来自于辅助队列。

DFS的时间复杂度：

在DFS的时间复杂度的计算中，也可以将时间开销分为两部分：

时间复杂度=访问各结点所需时间+探索各条边所需时间

所以若图采用邻接矩阵存储，时间复杂度为 $O(|V|^2)$

若图采用邻接表存储，时间复杂度为 $O(|V|+|E|)$

总结：与广度优先遍历相同，同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一。同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一。

•深度优先生成树

深度优先遍历就是探索各条边所连接的顶点的过程，与广度优先生成树相同，若只保留红色的边，这个图就变为了没有回路的树。

总结：

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一。同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一。

•深度优先生成森林

若某个图是非连通的，就需要调用多次DFS函数，每调用一次DFS函数，就会生成一棵深度优先生成树。下图有两个连通分量，那么就对应两棵深度优先生成树，这两棵树形成深度优先生成森林。

总结：

无向图：

对无向图进行BFS/DFS，遍历调用BFS/DFS函数的次数=连通分量数。
对于连通图，只需调用1次 BFS/DFS。

有向图：

对有向图进行BFS/DFS遍历，调用BFS/DFS函数的次数要具体问题具体分析。
1.若起始顶点到其他各顶点都有路径，则只需调用1次BFS/DFS 函数。

2.对于强连通图，从任一结点出发都只需调用1次 BFS/DFS。