数据结构——图（三、图的 广度/深度 优先搜索）

一、广度优先搜索(BFS)

①找到与一个顶点相邻的所有顶点
②标记哪些顶点被访问过
③需要一个辅助队列

#define MaxVertexNum 100
bool visited[MaxVertexNum];  //访问标记数组 
void BFSTraverse(Graph G){  //对图进行广度优先遍历，处理非连通图的函数 
    for(int i=0;i<G.vexnum;i++)// 遍历一下所有的 顶点
        visited[i] = false;    // 将所有的顶点都  设为 未访问标志。
    InitQueue(Q);    //初始化辅助队列Q 
    for(int i=0;i<G.vexnum;i++)// 从0号顶点开始遍历
        if(!visited[i])        // 对每个连通分量调用一次BFS() 
            BFS(G,i);    
}
void BFS(Graph G,int v){
    visit(v);
    visited[V]=true;   //对v做已访问标记 
    EnQueue(Q,v);   //顶点v入队 
    while(isEmpty(Q)){
        Dequeue(Q,v);   //队首顶点v出队 
        //for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        for(p=G.vertices[v].firstarc;p;p=p->nextarc){  //检测v的所有邻接点 
        	w=p->adjvex;
            if(visited[w]==false){
                visit(w);  //w为v尚未访问的邻接点，访问w 
                visited[w]=true;  // 对w做已访问标记 
                EnQueue(Q,w);  // 顶点w入队 
            }        	
		}

    }
}

无论是邻接矩阵还是邻接表的存储方式，BFS算法都需要借助一个辅助队列Q，
n个顶点均需要入队一次，在最坏的情况下，空间复杂度为O(|V|)

BFS遍历图的实质就是对每个顶点查找其邻接点的过程，耗费时取决于存储结构。
1、采用邻接表存储，每个顶点均需搜索（或入队）一次，时间复杂度为O(|V|),在搜索每个顶点的邻接点时
每条边至少被访问一次，时间复杂度为O(|E|),总的时间复杂度为 O(|V|+|E|)
2、采用邻接矩阵存储，查找每个顶点的邻接点所需要的时间为O(|V|),总的时间复杂度为O(|V|²) 

同一个图的邻接矩阵存储是唯一的，所以其广度优先生成树也是唯一的。
但因为邻接表存储表示不唯一，所以其广度优先生成树也是不唯一。 

广度优先搜索的应用——只可以检测无向图是否有环，有向图无法检测

二、深度优先搜索(DFS)

DFS算法是一个递归算法，需要借助一个递归工作栈，最好的空间复杂度是O(1),最差的空间复杂度是O(|V|)

DFS遍历图的实质就是对每个顶点查找其邻接点的过程，耗费时取决于存储结构。
1、采用邻接表存储，每个顶点均需搜索（或入队）一次，时间复杂度为O(|V|),在搜索每个顶点的邻接点时
每条边至少被访问一次，时间复杂度为O(|E|),总的时间复杂度为 O(|V|+|E|)
2、采用邻接矩阵存储，查找每个顶点的邻接点所需要的时间为O(|V|),总的时间复杂度为O(|V|²)  

#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM]; //访问标记数组 
void DFSTraverse(Graph G)  //对图进行深度优先遍历 
{
    for(v=0;v<G.vexnum;i++)
        visited[v]=false;   //初始化已访问标记数组 
    for(v=0;v<G.vexnum;i++)   //本代码是从v0开始遍历 
        if(!visited[v])   //对尚未访问的顶点调用DFS() 
            DFS(G,v);
}

//用邻接表实现深度优先搜索算法 
void DFS(ALGraph G,int v)
{
    visit(v);   
    visited[v]=true;
    for(p=G.vertices[v].firstarc;p;p=p->nextarc){  //检测v的所有邻接点 
    	j=p->adjvex;
        if(!visited[w])
            DFS(G,w);    	  //j为v的尚未访问邻接点，递归访问v 
	}

}

//用邻接矩阵实现深度优先搜索算法 
void DFS(MLGraph G,int v)
{
    visit(v);   
    visited[v]=true;
    for(j=0;j<G.vexnum;j++){  //检测v的所有邻接点 
        if(visited[j]==false && G.edge[i][j]==1)
            DFS(G,j);    	  //j为v的尚未访问邻接点，递归访问v 
	}

}

深度优先搜索应用——检测是否有向图/无向图是否有环

比如，无向图，先访问结点1，再访问结点2，再访问结点5，再访问结点3，此时结点3有两个邻接点，在先访问结点2的情况下，发现结点2已经被访问过，并且不是结点3的父节点，结点3的父节点是它的来时路——结点5。则此时，图里存在环。

 三、图的遍历与连通性

1、对于无向图来说，若无向图是连通的，则从任意一个结点出发，仅需一次遍历就能访问图中所有顶点；若无向图是非连通的，则从某一个顶点出发，一次性只能访问到该顶点所在连通分量的所有顶点 
2、对于无向图，BFSTraverse、 DFSTraverse这两个函数调用BFS、DFS的次数等于该图的连通分量 
3、对于有向图来说，若从初始顶点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。（即与是否为强连通图无关）
4、对于有向图，非强连通分量一次调用不一定能访问到该子图的所有顶点。