一、广度优先搜索(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、对于有向图，非强连通分量一次调用不一定能访问到该子图的所有顶点。
)
)
)
