一、深度优先搜索
深度优先搜索（Depth First Serch，DFS）类似于树的先序遍历。深度优先遍历，从初始节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后在以这个被访问的邻接节点作为初始节点，访问它的第一个邻接节点。我们可以这样理解：每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。
我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问。显然，深度优先搜索是一个递归的过程。
深度优先遍历算法步骤：
- 访问初始节点 v，并标记节点 v 为以访问；
- 查找节点 v 的第一个邻接节点 w；
- 若 w 存在，则继续执行步骤 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个节点继续；
- 若 w 未访问，对 w 进行深度优先遍历递归，即把 w 当做另一个 v，然后进行步骤 1,2,3；
- 查找节点 v 的 w 邻接点的下一个邻接节点，转到步骤 3；
#define Graph MGraph
int visited[MaxVertexNum] = {0}; // 定义标记数组，记录某个顶点是否被访问过
/**
* @brief 深度优先遍历
*
* @param graph 待遍历的图
*/
void DFS(Graph graph)
{
int i = 0;
for(i = 0; i < graph->vertexNum; i++)
{
visited[i] = 0;
}
for(i = 0; i < graph->vertexNum; i++)
{
if(!visited[i])
{
DFSByNode(graph,i);
}
}
}
/**
* @brief 深度优先遍历
*
* @param graph 待遍历的图
* @param v 第一个开始的顶点
*/
void DFSByNode(Graph graph,int v)
{
int w;
printf("%-5c",graph->vertex[v]);
visited[v] = 1; // 标记已访问
for(w = GetFirstNeighbor(graph,v); w >= 0; w = GetNextNeighbor(graph,v,w))
{
if(!visited[w]) // w为尚未访问的邻接顶点
{
DFSByNode(graph,w);
}
}
}
/**
* @brief 得到第一个邻接节点的下标
*
* @param graph 待操作的图
* @param index 对应节点的下标
* @return int 如果存在返回对应的下标，否则返回-1
*/
int GetFirstNeighbor(Graph graph,int index)
{
int j = 0;
for(j = 0; j < graph->vertexNum; j++)
{
if(graph->edge[index][j] > 0)
{
return j;
}
}
return -1;
}
/**
* @brief 根据前一个邻接节点的下标获取下一个邻接节点
*
* @param graph 待操作的图
* @param v1 对应节点的下标
* @param v2 上一个邻接节点的下标
* @return int
*/
int GetNextNeighbor(Graph graph,int v1,int v2)
{
int j = 0;
for(j = v2+1; j < graph->vertexNum; j++)
{
if(graph->edge[v1][j] > 0)
{
return j;
}
}
return -1;
}
邻接矩阵存储的图访问 V 个顶点需要 \(O(V)\) 的时间，查找每个顶点的邻接点都需要 \(O(V)\) 的时间，时间复杂度为 \(O(V^{2})\)
邻接表存储的图访问 V 个顶点需要 \(O(V)\) 的时间，查找每个顶点的邻接点都需要 \(O(E)\) 的时间，时间复杂度为 \(O(V+E)\)
每调用一次 DFS，就把 V 所在的连通分量遍历一遍；
二、广度优先搜索
广度优先搜索（Breadth First Search，BFS）类似于树的层序遍历。广度优先遍历需要使用一个队列以保证访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点。
广度优先遍历的算法步骤：
- 访问初始节点 v 并标记节点 v 为已访问；
- 节点 v 入队列；
- 当队列非空时，继续执行，否则算法结束；
- 出队列，取得队头节点 u；
- 查找节点 u 的第一个邻接节点 w；
- 若节点 u 的邻接节点 w 不存在，则转到步骤 3，否则循环执行以下三个步骤；
- 若节点 w 尚未被访问，则访问节点 w 并标记为已访问；
- 节点 w 入队列；
- 查找节点 u 的继 w 邻接节点后的下一个邻接节点 w，转到步骤 6；
#define Graph MGraph
int visited[MaxVertexNum] = {0}; // 定义标记数组，记录某个顶点是否被访问过
/**
* @brief 广度优先遍历
*
* @param G 待遍历的图
*/
void BFS(Graph graph)
{
int i = 0;
for(i = 0; i < graph->vertexNum; i++)
{
visited[i] = 0;
}
for(i = 0; i < graph->vertexNum; i++) // 从0号节点开始遍历
{
if(!visited[i]) // 对每个联通分量调用一次BFSByNode
{
BFSByNode(graph,i); // vertex[i]没有访问过，vVertex[i]开始BFS
}
}
}
/**
* @brief 广度优先遍历
*
* @param G 待遍历的图
* @param V 第一个开始的顶点
*/
void BFSByNode(Graph graph,int v)
{
int u = 0; // 表示队列的头节点对应的下标
int w = 0; // 邻接节点w
Queue Q = Create();
printf("%-5c",graph->vertex[v]);
visited[v] = 1; // 对以访问的v左标记
Enqueue(Q,v); // 顶点v入队Q
while(!IsEmpty(Q))
{
u = Dequeue(Q); // 顶点v出队
for(w = GetFirstNeighbor(graph,u); w >= 0; w = GetNextNeighbor(graph,u,w))
{
if(!visited[w]) // w为u的尚未访问的邻接顶点
{
printf("%-5c",graph->vertex[w]);
visited[w] = 1; // 对w做已访问标记
Enqueue(Q,w); // 顶点w入队
}
}
}
}
/**
* @brief 得到第一个邻接节点的下标
*
* @param graph 待操作的图
* @param index 对应节点的下标
* @return int 如果存在返回对应的下标，否则返回-1
*/
int GetFirstNeighbor(Graph graph,int index)
{
int j = 0;
for(j = 0; j < graph->vertexNum; j++)
{
if(graph->edge[index][j] > 0)
{
return j;
}
}
return -1;
}
/**
* @brief 根据前一个邻接节点的下标获取下一个邻接节点
*
* @param graph 待操作的图
* @param v1 对应节点的下标
* @param v2 上一个邻接节点的下标
* @return int
*/
int GetNextNeighbor(Graph graph,int v1,int v2)
{
int j = 0;
for(j = v2+1; j < graph->vertexNum; j++)
{
if(graph->edge[v1][j] > 0)
{
return j;
}
}
return -1;
}
邻接矩阵存储的图访问 V 个顶点需要 \(O(V)\) 的时间，查找每个顶点的邻接点都需要 \(O(V)\) 的时间，时间复杂度为 \(O(V^{2})\)
邻接表存储的图访问 V 个顶点需要 \(O(V)\) 的时间，查找每个顶点的邻接点都需要 \(O(E)\) 的时间，时间复杂度为 \(O(V+E)\)
每调用一次 BFS，就把 V 所在的连通分量遍历一遍；
三、测试程序
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i = 0,j = 0;
char data[] = {'A','B','C','D','E','F','G'};
int weight[][sizeof(data)] = {
{0,12,0,0,0,16,14},
{12,0,10,0,0,7,0},
{0,10,0,3,5,6,0},
{0,0,3,0,4,0,0},
{0,0,5,4,0,2,8},
{16,7,6,0,2,0,9},
{14,0,0,0,8,9,0}
};
Graph graph = CreateGraph(sizeof(data));
for(i = 0; i < graph->vertexNum; i++)
{
graph->vertex[i] = data[i];
}
for(i = 0; i < graph->vertexNum; i++)
{
for(j = 0; j <= i; j++)
{
if(weight[i][j] != 0)
{
Edge edge = malloc(sizeof(struct ENode));
edge->v1 = i;
edge->v2 = j;
edge->weight = weight[i][j];
InsertEdge(graph,edge);
}
}
}
DFS(graph);
printf("\n");
BFS(graph);
printf("\n");
return 0;
}