在 C++ 中为有向图制作邻接表

Making an adjacency list in C++ for a directed graph

提问by Musicode

Hello all :) Today I am refining my skills on graph theory and data structures. I decided to do a small project in C++ because it's been a while since I've worked in C++.

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

I want to make an adjacency list for a directed graph. In other words, something which looks like:

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

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

This would be a directed graph with V0 (vertex 0) having an edge to V1 and V3, V1 having an edge to V2, and V2 having an edge to V4, like this:

这将是一个有向图，其中 V0（顶点 0）有一条到 V1 和 V3 的边，V1 有一条到 V2 的边，V2 有一条到 V4 的边，如下所示：

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

I know that in order to do this, I will need to create an adjacency list in C++.An adjacency list is basically an array of linked lists. Okay, let's see some pseudo C++ code:

我知道为了做到这一点，我需要在 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
}

As you can tell, this pseudocode is currently far from the mark. And that is what i wanted some help with -- pointers and structs in C++ have never been my strong suit. First of all, this takes care of the vertices that a vertex points to -- but what about the vertex itself? How can I keep track of that vertex? When I loop over the array, it will do me no good to only know what vertices are being pointed to, rather than also knowing what points tothem. The first element in each list should probably be that vertex, and then the elements after that are the vertices it points to. But then, how can I access this first element of the list in my main program? (sorry if this is convoluted or confusing, I would happy to rephrase).

正如你所看到的，这个伪代码目前离目标还很远。这就是我想要的一些帮助——C++ 中的指针和结构从来都不是我的强项。首先，这会处理顶点指向的顶点——但是顶点本身呢？我怎样才能跟踪那个顶点？当我圈在阵列上，这对我没什么好只知道顶点被指向的是什么，而不是还知道什么点给他们。每个列表中的第一个元素可能应该是那个顶点，然后是它指向的顶点。但是，如何在主程序中访问列表的第一个元素？（对不起，如果这令人费解或令人困惑，我很乐意改写）。

I would like to be able to loop over this adjacency list to do some cool things with graphs. For example, to implement some graph theory algorithms (sorts, shortest paths, etc) using the adjacency list representation.

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

(Also, I had a question about the adjacency list. What is different than just using a list of arrays? Why can't I just have a list with an array at each element in the list?)

（另外，我有一个关于邻接列表的问题。与仅使用数组列表有什么不同？为什么我不能在列表中的每个元素上都有一个带有数组的列表？）

回答by Tacet

You may use a vectorin node, as a adjacency list.

您可以在节点中使用向量作为邻接列表。

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

If the graph is known at compile time, you can use array, but it's "a little bit" harder. If you know just size of graph (at compile time) you can do something like that.

如果图形在编译时已知，您可以使用array，但它“有点”难。如果您只知道图形的大小（在编译时），您可以执行类似的操作。

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

To add a neighbor, you doing something like that (do not forget numbering from zero):

要添加邻居，您可以执行以下操作（不要忘记从零开始编号）：

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

Of course, you can do no-pointer adjacency list and work "above" a table. Than you have vector<int>in node and you pushing number of neighbour. With both representation of the graph, you can realize all algorithms which use adjacency list.

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

And finally, I might add. Some use a listinstead of a vector, because the removal is in O(1)time. Mistake. For most algorithms, the order in the adjacency list is not important. So you can erase any element from vector in O(1)time. Just swap it with last element, pop_backis O(1)complexity. Something like that:

最后，我可以补充一下。有些使用列表而不是向量，因为移除是在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();

---

---

Specific example (you have vector in node, C++11 (!)):

具体示例（节点中有向量，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]};

I believe it's clear. From 0you can go to 1, from 1to 0and to itself, and (as in eg.) from 2to 0. It's directed graph. If you want undirected, you should add to both nodes neighbour's addresses. You can use numbers instead of pointers. vector<unsigned int>in class nodeand pushing back numbers, no addresses.

我相信这很清楚。从0你可以去到1，从1到0和到它自己，和（如在例如）从2到0。是有向图。如果你想要无向，你应该添加到两个节点的邻居地址。您可以使用数字代替指针。vector<unsigned int>在class node和推回数字，没有地址。

---

---

As we know, you do not need to use pointers. Here is an example of it, too.

我们知道，您不需要使用指针。这里也是一个例子。

When the number of vertexes may change, you can use vector of nodes (vector<node>) instead array, and just resizing. The rest remains unchanged. For example:

当顶点数量可能发生变化时，您可以使用节点向量 ( vector<node>) 代替数组，只需调整大小即可。其余保持不变。例如：

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);

But you can'terase a node, this breaches numbering! If you want to erase something, you should use list (list<node*>) of pointers. Otherwise you must keep non-existent vertexes. Here, the order matters!

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

---

---

Regarding the line nodes.emplace_back(); //adding node, It is safe with graph without pointers. If you want use pointers, you predominately shouldn'tchange size of graph. You can accidentally change address of some nodes, while adding vertex, when vectorwill be copied to new place (out of space).

关于线nodes.emplace_back(); //adding node，没有指针的图形是安全的。如果你想使用指针，你主要不应该改变图形的大小。您可能会意外更改某些节点的地址，同时添加顶点，何时vector将被复制到新位置（空间不足）。

One way to deal with it is using reserve, although you have to know maximal size of graph! But in fact I encourage you not to use vectorto keep vertexes, when you are using pointers. If you don't know implementation, more safe could be self memory management (smart pointers eg. shared_ptror just new).

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

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

Using vectoras adjacency listis always fine! There's no chance to change node's address.

使用vector作为邻接表总是罚款！没有机会更改节点的地址。

回答by Shashwat Kumar

This may not be very general approach but thats how I handle adjacency list in most of the cases. C++ has STL library which supports a data structure for linked list named as list.

这可能不是非常通用的方法，但这就是我在大多数情况下处理邻接列表的方式。C++ 有 STL 库，它支持名为list.

Say you have Nnodes in the graph, create a linked list for every node.

假设N图中有节点，为每个节点创建一个链表。

list graph[N];

Now graph[i]represent the neighbours of node i. For every edge i to j, do

现在graph[i]代表节点 i 的邻居。对于每条边 i 到 j，做

graph[i].push_back(j);

The best comfort is no handling of pointers so as segmentation fault errors.

最好的安慰是不处理指针，以免出现分段错误。

For more reference http://www.cplusplus.com/reference/list/list/

更多参考http://www.cplusplus.com/reference/list/list/

回答by Ahmed U3

I suggest you adding in the node structure, the Adjacency List And define the graph structure as List of Nodes instead of List of Adjacency Lists :)

我建议您添加节点结构，邻接列表并将图结构定义为节点列表而不是邻接列表列表:)

struct node {
    int vertex;
    node* next;
    adjList m_neighbors;
};
struct graph{
    //List of nodes
};

回答by Kohn1001

I would recommend the more general and simple approach of using vector and pairs: #include #include

我会推荐使用向量和对的更一般和简单的方法：#include #include

typedef std::pair<int, int> ii; /* the first int is for the data, and the second is for the weight of the Edge - Mostly usable for Dijkstra */
typedef std::vector<ii> vii;
typedef std::vector <vii> WeightedAdjList; /* Usable for Dijkstra -for example */
typedef std::vector<vi> AdjList; /*use this one for DFS/BFS */

Or alias style (>=C++11):

或别名样式（>=C++11）：

using ii = std::pair<int,int>;
using vii = std::vector<ii>;
using vi = std::vector<int>;
using WeightedAdjList = std::vector<vii>;
using AdjList = std::vector<vi>;

From here: using vector and pairs (from tejas's answer)

从这里： 使用向量和对（来自 tejas 的回答）

For additional information you can refer to a very good summary of topcoder: Power up c++ with STL

有关其他信息，您可以参考 topcoder 的一个很好的总结： Power up c++​​ with STL

回答by Visiedo

My approach would be to use a hash map to store the list of nodes in the graph

我的方法是使用哈希映射来存储图中的节点列表

class Graph {
private:
  unordered_map<uint64_t, Node> nodeList;
  ...
}

The map takes the node ID as key, and the node itself as value. This way you could search for a node in the graph in constant time.

该映射将节点 ID 作为键，将节点本身作为值。通过这种方式，您可以在恒定时间内搜索图中的节点。

The node contains the adjacency list, in this case as a c++11 vector. It could also be a linked list, although for this use case I would not see a difference in efficiency. Maybe the list would be better if you would like to keep it sorted somehow.

该节点包含邻接列表，在本例中为 c++11 向量。它也可以是一个链表，但对于这个用例，我不会看到效率上的差异。如果您想以某种方式对其进行排序，也许列表会更好。

class Node{
    uint64_t id;     // Node ID
    vector<uint64_t> adjList;  
...
}

With this approach you have to go through the adjacency list and then search the map on the ID to get the node.

使用这种方法，您必须遍历邻接列表，然后在 ID 上搜索地图以获取节点。

As an alternative, you could have a vector of pointers to the neighbor nodes itself. That would give you a direct access to the neighbor nodes, but then you could not use a map to keep all your nodes in the graph, and you would loose the possibility to search entries easily in your graph.

作为替代方案，您可以拥有一个指向相邻节点本身的指针向量。这将使您可以直接访问相邻节点，但是您无法使用地图将所有节点保留在图中，并且您将失去在图中轻松搜索条目的可能性。

As you can see, there is a lot of trade-off decisions you have to make when implementing a graph, all depends on your use cases.

如您所见，在实现图形时您必须做出许多权衡决定，这一切都取决于您的用例。