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

Making an adjacency list in C++ for a directed graph(在 C++ 中为有向图制作邻接表)

问题描述

大家好 :) 今天我正在提高我在图论和数据结构方面的技能.我决定用 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?)

推荐答案

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

You may use a vector in node, as a adjacency list.

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

如果图形在编译时已知，则可以使用array，但它有点有点"更难.如果您只知道图形的大小(在编译时)，您可以执行类似的操作.

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]

当然，您可以做无指针邻接表并在表格上方"工作.比你在节点中有 vector 并且你推送邻居的数量.有了图的两种表示，就可以实现所有使用邻接表的算法.

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) 时间内从 vector 中删除任何元素.只需将其与最后一个元素交换即可，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();

<小时>

具体示例(节点中有向量，C++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 到 0.是有向图.如果你想要无向，你应该添加到两个节点的邻居地址.您可以使用数字代替指针.vector 在 class node 和推回数字，没有地址.

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.

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

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

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).否则，您必须保留不存在的顶点.在这里，顺序很重要！

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();//添加节点，没有指针的图是安全的.如果您想使用指针，您主要不应该改变图形的大小.您可能会不小心更改某些节点的地址，在添加顶点时，vector 将被复制到新位置(空间不足).

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

处理它的一种方法是使用 reserve，尽管您必须知道最大尺寸图的！但实际上我鼓励你在使用指针时不要使用 vector 来保持顶点.如果你不知道实现，更安全的可能是自我内存管理(智能指针，例如 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.

使用vector 作为邻接表总是好的！没有机会改变节点的地址.

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

这篇关于在 C++ 中为有向图制作邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！