C++中深度优先搜索与广度优先搜索实现方法 |21xrx.com

C++中深度优先搜索与广度优先搜索实现方法

2023-07-01 19:11:29 深夜i -- --

C++ 深度优先搜索广度优先搜索实现方法搜索算法

深度优先搜索（DFS）和广度优先搜索（BFS）是图搜索算法中最基本的两种方法。它们被广泛应用于许多问题的解决中，例如迷宫问题、寻找最短路径、图像识别等。

在C++中，深度优先搜索和广度优先搜索的实现方法都需要使用图的邻接表或邻接矩阵来存储图的结构。邻接表是一个由链表组成的数组，每个数组元素都对应一个顶点，并且与这个顶点相邻的所有顶点都被存储在一个链表中。邻接矩阵则是一个二维数组，其中每个元素表示两个顶点是否相邻。

深度优先搜索的实现方法是以深度为优先级，先选择一个起点，访问与这个起点相邻的第一个顶点，然后从这个相邻顶点再继续向下搜索，直到达到某个终点或者搜索到所有可达的顶点为止。如果这个路径不存在或者无法到达终点，则返回上一个顶点，继续搜索其他方向。

使用邻接表存储图的深度优先搜索实现方法如下：


int visited[MAX_SIZE];
void dfs(int u)
{
  visited[u] = 1;
  cout<< u << " ";
  for (auto i : adj[u])
  {
    if (!visited[i])
    {
      dfs(i);
    }
  }
}

其中，adj[u]表示邻接表中与顶点u相邻的所有顶点。

广度优先搜索的实现方法则是以广度为优先级，先选择一个起点，访问起点的所有相邻顶点，并将它们加入到一个队列中。然后再依次访问这些相邻顶点相邻的顶点，并将它们加入到队列中。直到队列为空或者找到终点为止。

使用邻接表存储图的广度优先搜索实现方法如下：


int visited[MAX_SIZE];
void bfs(int u)
{
  queue<int> q;
  visited[u] = 1;
  q.push(u);
  while(!q.empty())
  {
    u = q.front();
    q.pop();
    cout<< u << " ";
    for(auto i : adj[u])
    {
      if(!visited[i])
      {
        visited[i] = 1;
        q.push(i);
      }
    }
  }
}

其中，adj[u]表示邻接表中与顶点u相邻的所有顶点。

上述代码中，visited数组表示节点是否被访问过的标记数组。MAX_SIZE表示邻接表或邻接矩阵的最大容量。

总的来说，深度优先搜索和广度优先搜索都是图搜索中非常基础的算法。在解决一些特定的问题时，我们需要根据实际情况选择一个更加适合的算法来实现。而这些算法的实现方法可以通过使用邻接表或邻接矩阵等数据结构来描述图结构，再通过使用递归或队列等方式来进行搜索。

上一篇: idea打包java可执行jar包

下一篇: C++中的函数可以嵌套定义吗？

评论区

()

相似文章