logo标签列表

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

c++graphadjacency-list
12

大家好 :) 今天我正在提升自己的图论和数据结构技能。因为已经有一段时间没有用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++中创建一个邻接表。邻接表基本上是链表数组。好的，让我们看一些伪代码：

#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 ++中的结构体从来不是我的强项。首先，这处理了一个顶点指向的顶点，但是该顶点本身呢？我如何跟踪该顶点？当我遍历数组时，仅知道被指向的顶点对我没有任何好处，而不知道指向它们的点。每个列表中的第一个元素应该是该顶点，然后是它指向的元素。但是，我如何在我的主程序中访问此列表的第一个元素？（如果这很复杂或令人困惑，我很乐意重新表述）。

我希望能够遍历此邻接表以对图进行一些有趣的操作。例如，使用邻接表表示来实现一些图论算法（排序，最短路径等）。

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

5个回答
16

你可以在Node.js中使用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)时间内从向量中删除任何元素。只需将其与最后一个元素交换，pop_back的时间复杂度为O(1)。就像这样:

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

具体示例（节点中有向量，使用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。这是有向图。如果想得到无向图，你需要将每个节点的地址加入到其相邻节点中。你可以使用数字代替指针，在class node中使用vector<unsigned int> ，并推入数字，而不是地址。

正如我们所知，您不需要使用指针。这里也提供了一个示例。

当顶点数量可能会改变时，您可以使用节点向量 (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);

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

关于代码行nodes.emplace_back(); //adding node，对于没有指针的图形结构来说是安全的。如果您想使用指针，请不要改变图的大小。当添加顶点时，您可能会意外地更改某些节点的地址，因为vector将被复制到新位置（超出空间）。

解决这个问题的一种方法是使用reserve，不过您必须知道图的最大大小！但实际上，我鼓励您在使用指针时不要使用vector来保存顶点。如果您不知道具体实现，更安全的做法可能是自我内存管理（例如，智能指针如shared_ptr或只是new）。 

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

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

3

这可能不是非常通用的方法，但这是我在大多数情况下处理邻接表的方式。 C++有一个名为list的支持链表数据结构的STL库。

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

list graph[N];

现在，graph[i]代表节点i的邻居。对于每一个从i到j的边，执行以下操作：
graph[i].push_back(j);

最好的舒适体验就是不涉及指针从而避免发生段错误。更多参考信息请查看http://www.cplusplus.com/reference/list/list/。
这种方法看起来不错，因为它使用了已经包含在库中的列表。我会考虑这种方式。 - Musicode
1
我建议在节点结构中添加邻接表，并将图的结构定义为节点列表而不是邻接列表 :)
struct node {
    int vertex;
    node* next;
    adjList m_neighbors;
};
struct graph{
    //List of nodes
};
让每个节点的邻接列表由图中节点列表中的节点索引组成。 - Ahmed U3
0
我建议使用更通用和简单的方法，即使用向量和对： #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 */

或者别名风格（>=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>;

从这里开始： 使用向量和对（来自Tejas的答案）

如需更多信息，您可以参考Topcoder的非常好的总结： 使用STL强化C ++

0
我的方法是使用哈希映射来存储图中节点的列表。
class Graph {
private:
  unordered_map<uint64_t, Node> nodeList;
  ...
}

该映射以节点ID作为键，节点本身作为值。这样一来，您可以在图中以恒定的时间搜索节点。

该节点包含邻接列表，此处使用c ++ 11向量。它也可以是链接列表，但对于此用例，我不认为效率会有什么区别。也许如果您希望以某种方式保持排序，则列表可能更好。

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

使用这种方法，您必须通过邻接列表进行遍历，然后根据ID在映射中搜索节点。

作为替代方案，您可以拥有指向邻居节点本身的指针向量。这将直接访问邻居节点，但是您不能使用映射来保留图中的所有节点，您将失去在图中轻松搜索条目的可能性。

正如您所看到的，实现图形时需要做出很多权衡决策，这完全取决于您的用例。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接