邻接列表图表示的实现

Question

我刚刚开始使用图论.我无法弄清楚如何使用链表编码邻接列表.例如,如果我有这个图(未定向):

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

我该如何编码？我知道如何使用邻接矩阵,但如何使用邻接列表和链接列表(c ++)来编码它？

Answer 1

邻接列表只是列表的向量/数组.图中的每个元素都是数组中的元素,任何边都会添加到它的邻接列表中.因此它看起来像:

A - > {B,C}

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

C - > {A,B}

D - > {B,E}

E - > {B,D}

所以我们从类似的东西开始std::vector<std::list<vertex>>.但是,我们可以做得比这更好,因为verticies是唯一的,因此我们可以使用a 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
    //...
 };