用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 

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

Answer 1

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

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

如果在编译时已知该图，则可以使用数组，但它“有点”困难。如果您只知道图的大小（在编译时），您可以做类似的事情。

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

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

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

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

//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]};

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

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

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

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