在C ++中为有向图创建一个邻接表 [英] Making an adjacency list in C++ for a directed graph

问题描述

Hello all :)今天，我正在提炼我的图形理论和数据结构的技能。我决定在C ++中做一个小项目，因为从C ++开始工作已经有一段时间了。

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++.

我想为有向图建立邻接表。换句话说，看起来像这样的东西：

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

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

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----->V1---->V2---->V4
 |
 |
 v
 V3 

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

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:

#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 + +从来没有是我强大的西装。首先，这需要处理顶点指向的顶点 - 但顶点本身呢？如何跟踪该顶点？当我循环遍历数组时，它不会仅仅知道正在被指向的顶点，而不知道对它们进行什么指向。每个列表中的第一个元素应该是该顶点，然后其后的元素是它指向的顶点。但是，那么，我如何访问这个列表的第一个元素在我的主程序？ （对不起，如果这是复杂或混乱，我很乐意改头换面）。

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 to them. 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).

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

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

推荐答案

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

You may use a vector in 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.

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]

当然，你可以做无指针邻接表工作上面一个表。比你在节点中有向量< int> ，并且你推送邻居的数量。与图形的表示，你可以实现使用邻接列表的所有算法。

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.

最后，我可能添加。有些使用列表而不是向量，因为删除操作位于 O（1）时间。错误。对于大多数算法，邻接表中的顺序并不重要。因此，您可以在 O（1）时间内从向量中清除任何元素。只需将其与最后一个元素互换， pop_back 是 O（1 ）复杂性。像这样：

And finally, I might add. Some use a list instead 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_back is O(1) complexity. Something like that:

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

---

具体示例++ 11（！））：

---

Specific example (you have vector in node, 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 到 code>。它是有向图。如果你想要无向，你应该添加到两个节点邻居的地址。您可以使用数字而不是指针。 在类节点中的向量< unsigned int> ，并回推数字，没有地址。

I believe it's clear. From 0 you can go to 1, from 1 to 0 and to itself, and (as in eg.) from 2 to 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 node and pushing back numbers, no addresses.

我们知道，你不需要使用指针。

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

当顶点的数量可能改变时，你可以使用向量的节点（ vector< ; node> ）代替数组，只需调整大小< a>。其余保持不变。例如：

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> 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（ list< node *> ）的指针。否则，你必须保持不存在的顶点。这里，顺序很重要！

But you can't erase 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!

关于 nodes.emplace_back //添加节点，对于没有指针的图形是安全的。如果您想使用指针，您主要不应更改图表的大小。
当您将向量复制到新位置（空间不足）时，您可以不小心更改某些节点的地址，同时添加顶点。

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

一种处理方式是使用预留，虽然你必须知道图的最大大小！但事实上，我鼓励你不使用向量保留顶点，当你使用指针。如果你不知道实现，更安全的可能是自我内存管理（智能指针，如 shared_ptr 或只是新的）。

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 vector to keep vertexes, when you are using pointers. If you don't know implementation, more safe could be self memory management (smart pointers eg. shared_ptr or just new).

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

使用向量作为邻接列表始终精细！没有机会更改节点的地址。

Using vector as adjacency list is always fine! There's no chance to change node's address.

这篇关于在C ++中为有向图创建一个邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！