C++图的实现代码 |21xrx.com

C++图的实现代码

2023-06-22 03:18:25 深夜i -- --

C++ 图实现代码数据结构

图是一种非常重要的数据结构，用于模拟许多实际情况。在C++中，可以通过类来实现图。下面是C++中使用类来实现图的代码示例。

首先需要定义一个图类，该类应具有以下属性：图的大小、存储顶点的向量、存储边的向量、存储每个顶点是否已被访问的向量。


class Graph {
private:
  int size; // 图的大小
  vector<vector<int>> vertex; // 存储顶点的向量
  vector<vector<int>> edge; // 存储边的向量
  vector<bool> visited; // 存储每个顶点是否已被访问的向量
public:
  Graph(int n) {
    size = n;
    visited.resize(size, false);
    vertex.resize(size);
    edge.resize(size);
  }
  // 添加边的函数
  void addEdge(int u, int v) {
    vertex[u].push_back(v);
    vertex[v].push_back(u);
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  // 深度优先搜索的函数
  void dfs(int v) {
    visited[v] = true; // 标记当前顶点已被访问
    cout << v << " "; // 输出当前顶点
    for (auto u : vertex[v]) { // 遍历当前顶点的邻接点
      if (!visited[u]) { // 如果该邻接点未被访问，则继续深度优先搜索
        dfs(u);
      }
    }
  }
};

在上面的代码中，用vector >来存储顶点和边。类的构造函数接受一个整数n作为参数，表示图的大小，同时初始化存储顶点、边和访问标记的向量。添加边的函数addEdge()使用向量来存储邻接表。

C++ 中也提供了一个非常强大的向量标准模板类，叫做vector，vector 是一个动态数组，它可以根据需要自动调整数组的大小。这使得 vector 很容易使用并且效率很高。

深度优先搜索的函数 dfs() 通过递归遍历所有未被访问过的顶点，同时将visited向量中的值相应修改，标记顶点已访问。函数内部也输出正在访问的顶点。

接下来我们可以在main函数里创建一个图对象并调用其方法，例如：


int main() {
  Graph graph(6);
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 3);
  graph.addEdge(2, 4);
  graph.addEdge(3, 5);
  cout << "DFS traversal of the graph:" << endl;
  graph.dfs(0);
  return 0;
}

在上述代码中，我们创建了一个包含六个顶点的图，并添加了边。然后使用深度优先搜索方法遍历并输出了整个图，在图上的遍历顺序将被控制台输出。

C++提供非常方便的图形实现方法。通过一个简单的类定义，您就可以轻松创建和修改图，并使用深度优先搜索或广度优先搜索等算法来遍历和操作图。

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

下一篇: C++子类的初始化列表

评论区

()

相似文章