21xrx.com
2024-11-22 07:05:13 Friday
登录
文章检索 我的文章 写文章
C++深度优先算法实现
2023-07-05 11:58:06 深夜i     --     --
C++ 深度优先算法 实现

深度优先算法是一种以深度为基础的搜索算法,它从根节点开始遍历图或树,并且尽可能深入直到找到目标节点或者所有可达节点都被访问。在C++中,我们可以使用递归或者栈来实现深度优先算法。

首先,我们需要定义一个图或者树的数据结构来存储节点的信息。例如,我们可以用下面的代码来定义一个简单的图:


#include<vector>

using namespace std;

struct Node

{

  int val;

  vector<Node*> neighbors;

};

其中,每个节点都包含一个值和一个邻居列表,邻居列表存储了与该节点相连的所有节点。接下来,我们需要用深度优先算法遍历图或树。

使用递归实现深度优先算法很简单,只需要定义一个函数来遍历节点,并且在访问每个节点时递归地遍历其所有未被访问的邻居。下面是一个递归实现的深度优先算法的代码示例:


void dfs(Node* node, vector<bool>& visited)

{

  visited[node->val] = true;

  for(auto neighbor : node->neighbors)

  {

    if(!visited[neighbor->val])

    {

      dfs(neighbor, visited);

    }

  }

}

其中,visited是一个数组,用于标记每个节点是否被访问过。当我们访问一个节点时,将其标记为已访问,并且遍历其所有未被访问的邻居。如果邻居节点未被访问,则递归地遍历该邻居节点。

另外一种实现深度优先算法的方式是使用栈。我们可以将起始节点加入到栈中,并且在每次遍历时将已访问节点的邻居加入到栈中,然后依次访问栈中的节点。下面是一个使用栈实现深度优先算法的代码示例:


void dfs(Node* node, vector<bool>& visited)

{

  stack<Node*> s;

  s.push(node);

  visited[node->val] = true;

  while(!s.empty())

  {

    Node* current = s.top();

    s.pop();

    for(auto neighbor : current->neighbors)

    {

      if(!visited[neighbor->val])

      {

        visited[neighbor->val] = true;

        s.push(neighbor);

      }

    }

  }

}

此处我们使用了一个栈来存储所有已访问但还未遍历其邻居的节点。当访问一个节点时,将其邻居加入到栈中,并且标记邻居节点为已访问。然后继续从栈中取出已访问但还未遍历其邻居的节点,进行遍历操作。

总之,这里演示了两种在C++中实现深度优先算法的方法,使用递归或者栈都可以实现该算法。根据具体情况选择适合的方法来实现深度优先算法,以提高程序的执行效率和准确性。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复