「C++实现图的邻接表存储和广度优先遍历实例分析」 |21xrx.com

「C++实现图的邻接表存储和广度优先遍历实例分析」

2023-06-27 12:27:56 深夜i -- --

C++ 图邻接表存储广度优先遍历

在计算机科学中，图是很重要的一种数据结构。在实际的应用中，图可以用来表示各种关系，比如社交网络中的好友关系，道路交通中的路网结构等等。邻接表是图的一种常用存储方法，本文将介绍如何使用C++实现图的邻接表存储和广度优先遍历。

邻接表存储方法是一种图的链式存储方式，它将每一个节点的相邻节点都存储在与该节点相连的链表中。换句话说，每一个节点会存储一个指向它所有相邻节点的链表。

我们可以使用C++中的链表来实现邻接表存储。下面是一个用C++实现的图的邻接表存储的示例代码：


#include <iostream>
#include <list>
using namespace std;
class Graph {
private:
  int V; //节点数量
  list<int> *adj; //邻接表
public:
  Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
  }
  //添加边
  void addEdge(int v, int w) {
    adj[v].push_back(w);
  }
  //广度优先遍历
  void BFS(int s) {
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
      visited[i] = false;
    list<int> queue;
    visited[s] = true;
    queue.push_back(s);
    while (!queue.empty()) {
      s = queue.front();
      cout << s << " ";
      queue.pop_front();
      for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
        if (!visited[*i]) {
          visited[*i] = true;
          queue.push_back(*i);
        }
      }
    }
  }
};
int main() {
  //创建一个图
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);
  cout << "广度优先遍历从节点2开始:\n";
  g.BFS(2);
  return 0;
}

在上面的示例代码中，Graph类是一个实现邻接表存储的图的类。在类中，我们在构造函数中初始化了邻接表，并且实现了添加边和广度优先遍历的方法。

在main函数中，我们创建了一个名为g的Graph对象，并向它添加了一些边，然后进行了一次广度优先遍历。在广度优先遍历过程中，我们使用了一个visited数组来记录已经遍历过的节点，同时使用了一个queue队列来存储待遍历的节点。

当我们运行上面的示例代码时，输出结果如下所示：

广度优先遍历从节点2开始: 2 0 3 1

以上输出结果展示了广度优先遍历的结果是从节点2开始，依次遍历节点2,0,3和1。

总之，邻接表存储和广度优先遍历是图算法中的两个重要概念，它们在计算机科学中的应用十分广泛，我们可以使用C++来实现它们的许多实际操作。

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

下一篇: C++中string类型出现中文乱码问题

评论区

()

相似文章