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

C++实现图的邻接表

2023-07-04 19:50:24 深夜i -- --

C++ 图邻接表

图是一种非常常见的数据结构，它可以用来描述很多现实生活中的问题，比如路线规划、社交网络等。而邻接表是用来表示图的一种常见方式，它通过链表的形式存储每个顶点的邻居，方便进行图的遍历和操作。在C++中，实现邻接表也是一项非常重要的任务，下面我们来介绍如何实现图的邻接表。

首先，我们需要定义一个邻接表的数据结构。一般而言，邻接表可以由一个数组和一个链表组成。数组用来存储每个顶点，链表则存储该顶点的邻居。因此，邻接表的定义可以如下所示：


struct node {
  int val;
  node* next;
  node(int x) : val(x), next(nullptr) {};
};
vector<node*> adjList;

其中，`node`是表示链表中的节点的结构体，`adjList`则是一个指向链表头节点的数组，数组的下标即为顶点的编号（从0开始）。

接着，我们需要实现一些基本的操作。比如向邻接表中添加一个顶点的操作，可以通过以下代码来实现：


void addVertex(int x) {
  if ((int)adjList.size() <= x) {
    adjList.resize(x+1, nullptr);
  }
}

其中，`addVertex`需要传入一个顶点的编号`x`，如果邻接表中还没有这个编号对应的元素，就需要扩展数组长度，将其初始化为`nullptr`。

再比如，向邻接表中添加一条边的操作，可以通过以下代码来实现：


void addEdge(int x, int y) {
  addVertex(x);
  addVertex(y);
  node* tmp = new node(y);
  tmp->next = adjList[x];
  adjList[x] = tmp;
}

其中，`addEdge`需要传入两个顶点的编号`x`和`y`，表示它们之间的一条边。首先需要调用`addVertex`函数来确保邻接表中已经存在这两个顶点，然后就可以将`y`作为一个新的链表节点插入到`x`的邻居链表中。

最后，我们需要实现一些遍历或操作的函数，比如深度优先搜索（DFS）和广度优先搜索（BFS）。这里我们以DFS为例，展示如何递归实现：


void dfs(int u, vector<bool>& visited) {
  visited[u] = true;
  node* tmp = adjList[u];
  while (tmp != nullptr) {
    int v = tmp->val;
    if (!visited[v]) {
      dfs(v, visited);
    }
    tmp = tmp->next;
  }
}

其中，`dfs`需要传入当前遍历到的顶点编号`u`和一个表示是否被访问过的布尔数组`visited`。首先，将当前顶点标记为已访问，然后依次遍历它的所有邻居节点，如果发现邻居节点没有被访问过，就继续递归遍历。

这样，我们就完成了对C++实现图的邻接表的介绍。通过以上内容，相信读者已经可以掌握如何使用邻接表来表示图，以及如何实现基本的操作和遍历算法。在实际应用中，我们可以根据需求灵活使用这些操作和算法，来解决各种图论相关的问题。

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

下一篇: 如何在C++中调用数组函数

评论区

()

相似文章