1.前言
对于图的遍历来说通常有两种遍历次序，它们是深度优先遍历和广度优先遍历
2.深度优先遍历
深度优先遍历（Depth_First_Search）：也有称为深度优先搜索，简称为DFS。1.它从图中某个顶点V出发，访问此顶点，然后从V的未被访问的邻接结点出发深度优先遍历图，直至图中所有和V有路径相通的顶点被访问到。2.对于非连通图来说，图中尚有顶点未被访问则另选图中未被访问的顶点作为起始点，重复一步骤即可。图的深度遍历类似于先序遍历。
对于邻接矩阵实现的图来说，其深度优先遍历算法如下：
bool visited[MAXVER]; //标记访问过的顶点的数组
//邻接矩阵的深度优先递归算法
void DFS(Graph graph,size_t i)
{
visited[i] = true;
std::cout << graph.vers[i] << std::endl;
for (size_t j = 0 ; j < graph.verNum ; j++)
{
//存在邻边且与i关联的另一个顶点未经访问
if (graph.edge[i][j] != INFINI && !visited[j])
{
DFS(graph,j); //对访问过的顶点的邻接结点进行递归
}
}
}
//邻接矩阵的深度遍历操作
void DFSTraverse(Graph graph)
{
for (size_t i = 0 ; i < graph.verNum ; i++)
{
visited[i] = false; //默认所有的顶点都未经访问
}
for (size_t i = 0 ; i < graph.verNum ; i++)
{
if (!visited [i])
{
DFS(graph,i); //如果图是连通图，则此函数执行一次
}
}
}
其深度优先遍历算法时间复杂度推导：推导一个算法的时间复杂度一般是推导最坏情况下的时间复杂度。先推导出算法语句总的执行次数和问题规模的函数，然后根据大O阶推导法。假设图的顶点数为n，边数为e。可知上诉算法的时间复杂度为O(n*n).
对于邻接表实现的图来说，其深度优先遍历算法如下：
bool visited[MAXVER];
//邻接表的深度优先递归算法
void DFS(AdjListGraph graph,size_t i)
{
visited[i] = true;
std::cout << graph.adjList[i].data;
EdgeNode* workNode = graph.adjList[i].firstEdge;
while(workNode)
{
if (!visited[workNode->adjVex])
{
DFS(graph,workNode->adjVex);
}
workNode = workNode->next;
}
}
//邻接表的深度遍历操作
void DFSTraverse(AdjListGraph graph)
{
for (size_t i = 0 ; i < graph.verNum ; i++)
{
visited[i] = false; //默认所有的顶点都未经访问
}
for (size_t i = 0 ; i < graph.verNum ; i++)
{
if (!visited [i])
{
DFS(graph,i); //如果图是连通图，则此函数执行一次
}
}
}
上诉遍历算法时间复杂度为：O(n+e).
3.广度优先遍历
广度优先遍历(Breadth_ First_Search)：又称广度优先搜索。图的广度优先遍历类似于树的层序遍历。下面看看思想是怎么样的。
假设现有一无向图：
无向图示例2.png
广度遍历示意图.png
假设从A顶点开始访问，则访问完A（出队）后就将A顶点的邻接顶点依次入队。然后又将对头元素出队，又将对头元素的未经访问的顶点依次入队。直到对空为止。总之每次访问一个顶点就将该顶点的未经访问的邻接顶点入队。
对于邻接矩阵实现的图来说，其深度优先遍历算法如下：
bool visited1[MAXVER]; //标记访问过的顶点的数组
void BFSTraverse(Graph graph)
{
//初始化一队列,存储将要出队（访问）的顶点在顶点数组中的下标
std::queue<size_t>que;
//默认所有顶点未经访问
for (size_t i = 0 ; i < graph.verNum ; i++)
{
visited[i] = false;
}
//如果是连通图，则此循环执行一次
for (size_t i = 0 ; i < graph.verNum ; i++)
{
if (!visited1[i])
{
visited1[i] = true;
std::cout << graph.vers[i];
que.push(i);
while (!que.empty())
{
size_t k = que.front();//记录将要出队的顶点在顶点数组中的下标
que.pop(); //当对头顶点出队后，就将对头顶点的未被访问的邻接顶点入队
for (size_t j = 0; j < graph.verNum; j++)
{
if (graph.edge[k][j] != INFINI && !visited1[j])
{
visited1[j] = true;
std::cout << graph.vers[j];
que.push(graph.vers[j]);
}
}
}
}
}
}
对于邻接表实现的图来说，其深度优先遍历算法如下：
//邻接表的广度优先遍历
void BFSTraverse(AdjListGraph graph)
{
bool visited[MAXVER];
std::queue<size_t>que;
for (size_t i = 0 ; i < graph.verNum ; i++)
{
visited[i] = false;
}
for (size_t i = 0 ; i < graph.verNum ; i ++)
{
if (!visited[i])
{
visited[i] = true;
std::cout << graph.adjList[i].data;
que.push(i);
while (!que.empty())
{
//记录队头的顶点的下标
size_t k = que.front();
que.pop();
//从已经出对头的第一个邻接顶点开始访问
EdgeNode* workNode = graph.adjList[k].firstEdge;
while (workNode)
{
if (!visited[workNode->adjVex])
{
visited[workNode->adjVex] = true;
std::cout << graph.adjList[workNode->adjVex].data;
que.push(workNode->adjVex);
}
workNode = workNode->next;
}
}
}
}
}
广度优先遍历的算法的时间复杂度和深度优先遍历算法是一样的。深度优先遍历更适合于目标比较明确以找到目标为主的情况。而广度优先遍历更适合不断扩大范围寻找最优解的情况。
网友评论