介绍
在数据结构中，树和图可以说是不可或缺的两种数据结构。其中，对于图来说，最重要的算法可以说就是遍历算法。而搜索算法中，最标志性的就是深度优先算法和广度优先算法。
图的定义
图的定义普遍为两种，一种是邻接表，另一种是邻接矩阵。图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同生成的邻接表也不同。因此，对于同一个表，基于邻接矩阵的遍历所得到的BFS序列和DFS序列是不唯一的，基于邻接表的遍历所得到的BFS和DFS是唯一的。
邻接表
代码语言：javascript复制#define MXNUM 100
typedef char VertexType;
typedef int EdgeType;
typedef struct VNode{ VertexType data;
ArcNode *first;}VNode,AdjList[MXNUM];typedef struct{
AdjList vertics;
int vexnum,arcnum;}ALGraph;邻接矩阵
代码语言：javascript复制#define MXNUM 100
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
VertexType Vex[MXNUM];
EdgeType Edge[MXNUM][MXNUM];
int Vexnum,Edgenum;}MGraph;typedef struct ArcNode{
int adjvex;
struct ArcNode *next;}ArcNode;广度优先算法
广度优先算法的实现
广度优先算法是一种分层的查找过程，每向前走一步可能会访问一批顶点，不像深度优先搜索算法那样有回溯的情况，因此它不是一个递归的算法。为了实现逐层访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。
代码语言：javascript复制void BFSTraverse(MGraph G){
int i;
for(i=0;i<G.Vexnum; i)
{
visited[i]=false;
}
InitQueue(Q);
for(i=0;i<G.Vexnum; i)
{
if(!visited[i])
BFS(G,i);
}}void BFS(MGraph G,int v){
visit(v);
visited[v]=true;
enqueue(Q,v);
while(!Empty(Q))
{
Dequeue(Q,v);
for(int w=firstNeighbor(v);w>=0;w=NextNeighbor(G,w,v))
{
if(!visited[w])
{
visit(w);
visited[w]=true;
enqueue(Q,w);
}
}
}}无论是邻接表还是邻接矩阵存储图，广度优先算法的空间复杂度都是O（n）。 采用邻接表存储方式时，每个顶点均需要搜索一次，故时间复杂度O(|V|)，在搜索任意节点的邻接点时，每条边至少访问一次，故时间复杂度为O(E)，算法总时间复杂度为O(E V)。采用邻接矩阵存储时，时间复杂度为O(V*V)。
广度优先算法的应用
广度优先算法在很多求解问题的最优解方面有很好的应用，下面以求图中某一结点的单源最短路径为例。 算法思路：求某一结点的单源最短路径，可以使用广度优先算法，每向外搜索一层，路径 1。全部搜索完后，就可以得到所求节点到所有节点的路径。
代码语言：javascript复制void MIN_Distance(MGraph G,int v){
for(i=0;i<G.Vexnum;i )
dis[i]=&;
visited[v]=true;
dis[v]=0;
Enqueue(Q,v);
while(!Empty(Q))
{
Dequeue(Q,v);
for(w=firstNeighbor(G,v);w>=0;w=nextNeighbor(G,v,w))
{
if(!visited[w])
{
visited[w]=true;
dis[w]=dis[v] 1l;
Enqueue(Q,w);
}
}
}}可以看出来，其实就是将简单的广度优先算法的变型。
深度优先算法
深度优先算法的实现
图的深度优先算法类似于树的先序遍历，DFS算法是一个递归算法，需要借助一个工作栈，故其空间复杂度度为O(V)。 深度优先算法的邻接矩阵的时间复杂度为O(V*V),邻接表的时间复杂度为O（V E）。
代码语言：javascript复制void DFSTraverse(MGraph G,int v){
for(int i=0;i<G.Vexnum; i)
{
visited[i]=false;
}
for(int i=0;i<G.Vexnum; i)
if(!visited[i])
DFS(G,i);}void DFS(MGraph G,int v){
visit(v);
visited[v]=true;
for(int w=firstNeighbor(G,v);w>=0;w=nextNeighbor(G,w,v))
{
if(!visited[w])
DFS(G,w);
}}后续
图的遍历算法可以用来检索是连通图还是非连通图，只需要进行一次深度优先算法或者广度优先遍历，如果可以遍历所有节点，代表是连通图，如果一次不能遍历所有节点，代表是非连通图。
