c++ - 邻接表图形表示的实现

我只是从图论开始的。我不知道如何使用链接列表编码邻接列表。例如，如果我有此图(无向):

A--------B
|       /|\
|      / | \
|     /  |  \
|    /   |   \
|   /    |    \
|  /     |     \
| /      |      \
C        E-------D

我该如何编码？我知道如何使用邻接矩阵来执行此操作，但是如何使用邻接表和链接列表(C++)对其进行编码？

最佳答案

邻接列表只是列表的 vector/数组。图中的每个元素都是数组中的一个元素，并且任何边都添加到它的邻接表中。因此，它看起来像:

A-> {B，C}

B-> {A，C，D，E}

C-> {A，B}

D-> {B，E}

E-> {B，D}

因此，我们从std::vector<std::list<vertex>>之类的东西开始。但是，我们可以做得更好，因为顶点是唯一的，因此我们可以使用map。此外，顶点只能在边缘列表中出现一次，因此我们将其修改为std::map<vertex, std::set<vertex>>。

首先，类似:

struct vertex
{
   //
};

class undirected_graph
{
private:
    std::map<vertex, std::set<vertex>> graph_container;
public:
    void add_vertex(const vertex& v) { //add a vertex to the map }
    void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list }
    //Other methods
    //...
 };

关于c++ - 邻接表图形表示的实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14133115/