C++实现邻接表 |21xrx.com

C++实现邻接表

2023-07-06 00:55:45 深夜i -- --

C++ 邻接表实现

邻接表是一种表示图的数据结构，它通过记录一个图中每个顶点的邻接顶点来描述图的结构。而作为一种目前广泛应用于实践开发中的语言，C++也可以非常方便地用来实现邻接表。

在C++中实现邻接表的方式有多种，其中一种较为常见的方法是使用向量和链表。具体而言，我们可以定义一个向量用于存储顶点的信息，而每个顶点又可以通过链表的方式记录其邻接顶点。以下是一个可能的实现：


#include <vector>
using namespace std;
struct Node {
  int val;
  Node* next;
  Node(int v, Node* p = nullptr) : val(v), next(p) {}
};
class Graph {
private:
  vector<Node*> vertices; // 存储顶点信息的向量
  int V; // 图中顶点的数量
public:
  Graph(int v) : V(v) {
    vertices.reserve(V); // 预分配存储空间
    for (int i = 0; i < V; ++i) {
      vertices.push_back(new Node(i)); // 初始化顶点
    }
  }
  void addEdge(int u, int v) {
    vertices[u]->next = new Node(v, vertices[u]->next);
    vertices[v]->next = new Node(u, vertices[v]->next);
  }
  void print() const {
    for (int i = 0; i < V; ++i) {
      cout << "Vertex " << i << ":\t";
      Node* cur = vertices[i]->next;
      while (cur != nullptr)
        cout << cur->val << " ";
        cur = cur->next;
      
      cout << endl;
    }
  }
};
int main() {
 Graph g(4);
 g.addEdge(0, 1);
 g.addEdge(1, 2);
 g.addEdge(2, 0);
 g.addEdge(0, 3);
 g.print();
 return 0;
}

在这个实现中，我们首先定义了一个Node结构体，用于表示邻接表中的一个节点。其中，val代表顶点的编号，next指向下一个邻接顶点。接着，我们定义了Graph类，并在其中声明了一个存储顶点信息的向量vertices。在构造函数中，我们初始化了每个顶点，其邻接链表则都为空。最后，通过调用addEdge方法，我们可以很方便地将边添加进邻接表中。

通过以上代码的演示，我们可以发现C++实现邻接表具有较为简洁、高效等优点，大大提升了代码的可维护性和扩展性。在实际应用开发中，这一技术也具有广泛并且实用的意义。

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

下一篇: C++中结构体和类的区别是什么？

评论区

()

相似文章