c++ - 在 C++ 中为有向图创建邻接表

Question

大家好 :) 今天我正在精炼我在图论和数据结构方面的技能。我决定用 C++ 做一个小项目，因为我已经有一段时间没有用 C++ 工作了。

我想为有向图制作一个邻接表。换句话说，它看起来像:

0-->1-->3
1-->2
2-->4
3-->
4-->

这将是一个有向图，其中 V0(顶点 0)具有到 V1 和 V3 的边，V1 具有到 V2 的边，而 V2 具有到 V4 的边，如下所示:

V0----->V1---->V2---->V4
 |
 |
 v
 V3 

我知道，为了做到这一点，我需要用 C++ 创建邻接表。邻接表基本上是一个链表数组。好的，让我们看一些伪 C++ 代码:

#include <stdio>
#include <iostream>
using namespace std;

struct graph{
//The graph is essentially an array of the adjList struct.  
node* List[];

};

struct adjList{
//A simple linked list which can contain an int at each node in the list.

};

struct node {
int vertex;
node* next;
};

int main() {
//insert cool graph theory sorting algorithm here
}

如您所知，此伪代码目前还远未达到目标。这就是我需要的帮助——C++ 中的指针和结构从来都不是我的强项。首先，这会处理顶点指向的顶点——但是顶点本身呢？我怎样才能跟踪那个顶点？当我遍历数组时，只知道指向哪些顶点而不是知道哪些点指向它们对我没有好处。每个列表中的第一个元素可能应该是那个顶点，然后是它指向的顶点之后的元素。但是，我怎样才能在我的主程序中访问列表的第一个元素呢？ (抱歉，如果这令人费解或令人困惑，我很乐意改写)。

我希望能够遍历这个邻接表来用图表做一些很酷的事情。例如，使用邻接表表示来实现一些图论算法(排序、最短路径等)。

(另外，我有一个关于邻接表的问题。与仅使用数组列表有什么不同？为什么我不能只在列表中的每个元素处使用一个数组的列表？)

Answer 1

您可以使用 vector在节点中，作为邻接表。

class node {
  int value;
  vector<node*> neighbors;
 };

如果图在编译时是已知的，你可以使用array ，但它“有点”难。如果你只知道图形的大小(在编译时)，你可以做类似的事情。

template<unsigned int N>
class graph {
  array<node, N> nodes;
 }

要添加邻居，您需要做类似的事情(不要忘记从零开始编号):

nodes[i].neighbors.push_back(nodes+j); //or &nodes[j]

当然，您可以使用无指针邻接表并在表“上方”工作。比你有vector<int>在节点中，您推送邻居的数量。通过图的两种表示，您可以实现所有使用邻接表的算法。

最后，我想补充一点。有些使用 list而不是 vector ，因为移除是在 O(1) 时间内完成的。错误。对于大多数算法，邻接表中的顺序并不重要。因此，您可以在 O(1) 时间内从 vector 中删除任何元素。只需将它与最后一个元素交换，pop_back是O(1) 复杂度。类似的东西:

if(i != number_of_last_element_in_list) //neighbors.size() - 1
 swap(neighbors[i], neighbor.back());
neighbors.pop_back();

---

具体示例(节点中有 vector ，C++11 (!)):

//creation of nodes, as previously
constexpr unsigned int N = 3;
array<node,N> nodes; //or array<node, 3> nodes;
//creating edge (adding neighbors), in the constructor, or somewhere
nodes[0].neighbors = {&nodes[1]};
nodes[1].neighbors = {&nodes[0], &nodes[1]};
//adding runtime, i,j from user, eg. i = 2, j = 0
nodes[i].neighbors.push_back(&nodes[j]); //nodes[2].neighbors = {&nodes[0]};

我相信这很清楚。来自 0你可以去1 , 来自 1至 0和自身，以及(例如)来自 2至 0 .是有向图。如果你想要无向，你应该添加到两个节点的邻居地址。您可以使用数字而不是指针。 vector<unsigned int>在class node并推回数字，没有地址。

---

众所周知，您不需要使用指针。这也是它的一个例子。

当顶点数可能发生变化时，您可以使用节点 vector ( vector<node> ) 而不是数组，而只使用 resizing .其余保持不变。例如:

vector<node> nodes(n); //you have n nodes
nodes.emplace_back(); //you added new node, or .resize(n+1)
//here is place to runtime graph generate
//as previously, i,j from user, but now you have 'vector<unsigned int>' in node
nodes[i].neighbors.push_back(j);

但是你不能删除一个节点，这违反了编号!如果你想删除一些东西，你应该使用指针列表(list<node*>)。否则你必须保留不存在的顶点。在这里，顺序很重要!

---

关于 nodes.emplace_back(); //adding node 行, 没有指针的图形是安全的。如果你想使用指针，你主要不应该改变图表的大小。当 vector 时，您可能会在添加顶点时不小心更改某些节点的地址。将被复制到新的地方(空间不足)。

处理它的一种方法是使用 reserve ，虽然你必须知道图的最大尺寸!但实际上我鼓励你不要使用 vector在使用指针时保留顶点。如果您不知道实现，更安全的可能是 self 内存管理(智能指针，例如 shared_ptr 或只是 new)。

node* const graph = new node[size]; //<-- It is your graph.
//Here no address change accidentally.

使用 vector因为 adjacency list 总是fine!没有机会更改节点的地址。