C++代码实现深度优先算法 |21xrx.com

C++代码实现深度优先算法

2023-09-17 02:57:55 深夜i -- --

C++ 代码实现深度优先算法图遍历递归

深度优先算法是一种常用的图遍历算法，在计算机科学领域应用广泛。它以递归方式实现，在遍历图的过程中，不断深入到图的最深处，直到不能再继续深入为止。接下来，我们将使用C++代码来演示深度优先算法的实现。

首先，我们需要定义一个图的类，用于存储图的结构和相关操作。在这个类中，我们将使用邻接表来表示图。邻接表是一种数据结构，用于存储图的顶点和它们之间的边。


class Graph{
private:
  int V;         // 图的顶点数量
  list<int> *adj;    // 邻接表
public:
  Graph(int V);
  void addEdge(int v, int w);  // 添加边
  void DFS(int v);        // 深度优先搜索遍历
};
Graph::Graph(int V){
  this->V = V;
  adj = new list<int>[V];
}
void Graph::addEdge(int v, int w){
  adj[v].push_back(w);  // 在顶点v的邻接表中添加顶点w
}
void Graph::DFS(int v){
  // 使用一个数组来标记已经访问过的顶点
  bool *visited = new bool[V];
  for(int i=0; i<V; i++){
    visited[i] = false;
  }
  // 递归实现深度优先遍历
  DFSUtil(v, visited);
}
void Graph::DFSUtil(int v, bool visited[]){
  visited[v] = true;
  cout << v << " ";  // 输出当前访问的顶点
  // 递归访问没有访问过的相邻顶点
  list<int>::iterator it;
  for(it=adj[v].begin(); it!=adj[v].end(); it++){
    if(!visited[*it]){
      DFSUtil(*it, visited);
    }
  }
}

在上述代码中，我们首先定义了一个`Graph`类，它包含了图的顶点数量和邻接表。我们可以使用`addEdge`方法来添加边，将顶点v与顶点w连接起来。接下来，我们实现了`DFS`方法，它用于启动深度优先遍历，并调用递归函数`DFSUtil`来实际访问顶点。

在`DFSUtil`方法中，我们首先标记当前顶点为已访问，然后输出当前顶点。接下来，我们递归访问与当前顶点相邻的未访问过的顶点，直到所有顶点都被访问过为止。

使用上述代码，我们可以创建一个图对象，并通过调用`DFS`方法来执行深度优先遍历。例如，下面是一个示例代码段，演示如何创建一个图，并对它执行深度优先遍历：


int main(){
  Graph g(5);  // 创建一个拥有5个顶点的图
  // 添加边
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 3);
  g.addEdge(2, 4);
  cout << "Depth First Traversal (starting from vertex 0): ";
  g.DFS(0);
  return 0;
}

在上述示例中，我们创建了一个包含5个顶点的图，并添加了一些边。然后，我们调用`DFS`方法，从顶点0开始执行深度优先遍历。最后，我们输出遍历结果。

深度优先算法是一种非常重要且常用的图遍历算法，在解决很多实际问题中都有应用。通过使用C++编程语言实现深度优先算法，我们可以更好地理解其原理和操作过程。希望本文对你深入理解深度优先算法的实现有所帮助。

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

下一篇: C++中find_if的用法详解

评论区

()

相似文章