Реализация представления графа списка смежности

Я только начал с теории графов. Я не могу понять, как кодировать список смежности, используя связанные списки. например, если у меня есть этот график (ненаправленный):

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

Как мне это закодировать? Я знаю, как это сделать, используя матрицу смежности, но как это закодировать, используя список смежности и связанные списки (С++)?


c++ data-structures graph-theory
person Somebody    schedule 03.01.2013    source источник

Ответы (3)


arrow_upward
14
arrow_downward

Список смежности — это просто вектор/массив списков. Каждый элемент графа является элементом массива, и любое ребро добавляется в его список смежности. Таким образом, это выглядит примерно так:

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
    //...
 };
person Yuushi    schedule 03.01.2013
comment
Из Википедии: В теории графов список смежности — это представление всех ребер или дуг в график в виде списка. То, что вы реализовали, может быть оптимизацией этого, но основная концепция немного затемнена. - person Potatoswatter; 03.01.2013
comment
@PushkarMishra Конечно. Если вы пытаетесь реализовать это впервые, используйте то, что проще всего. - person Yuushi; 03.01.2013
comment
являются ли векторы эффективным вариантом? - person Somebody; 03.01.2013
comment
Ну, весь смысл списков смежности по сравнению с матрицами смежности заключается в том, что они более эффективны с точки зрения памяти для графов, которые не имеют слишком много ребер. Реализация map/set, вероятно, будет быстрее, но для любых не очень больших графов разница, вероятно, будет минимальной. - person Yuushi; 03.01.2013
comment
использование std::map для списка смежности приведет к сложности O(|V|*log(|V|)+|E|) для обхода bfs/dfs, где |V|,|E| - размер вершин и ребер соответственно. Следовательно, для разреженной матрицы это приведет к более высокой временной сложности. - person Kaushik Acharya; 06.02.2015
comment
@KaushikAcharya Более высокая временная сложность по сравнению с чем? Если вы имеете в виду по сравнению с undordered_map, то да, вы можете уменьшить его до O (| V | + | E |) (с учетом амортизированного поиска O (1)). - person Yuushi; 06.02.2015

arrow_upward
3
arrow_downward

Список смежности будет просто набором объектов, представляющих ребра графа.

struct edge {
    node *nodes[2];

    edge( node *a, node *b ) {
        if ( a < b ) { // define canonical order of edges for undirected graph
            nodes[0] = a;
            nodes[1] = b;
        } else {
            nodes[0] = b;
            nodes[1] = a;
        }
    }
};

Связанный список не кажется особенно практичным; обычно вы должны определить порядок ребер и поместить их в std::set или std::map.

bool operator< ( edge const &lhs, edge const &rhs ) {
    if ( lhs.nodes[0] < rhs.nodes[0] ) return true;
    if ( rhs.nodes[0] < lhs.nodes[0] ) return false;
    return lhs.nodes[1] < rhs.nodes[1];
}

typedef std::set< edge > graph;

Есть много способов сделать это, трудно предложить что-то еще, не зная, что вы собираетесь делать с графиком.

person Potatoswatter    schedule 03.01.2013

arrow_upward
0
arrow_downward

Вы можете черпать вдохновение из исходного кода следующего репозитория ( CXXGraph ).

Этот репозиторий содержит только библиотеку заголовков и реализацию матрицы смежности.

person Zig Razor    schedule 05.07.2021