Что такое список смежности и как его кодировать?

Вот сообщение SO списка смежности. Однако я не вижу разницы от односвязного списка? Также здесь есть статья в Википедии, в которой говорится, что это все ребра (графа, дискретные математический тип) в списке, который довольно широк, если у меня есть граф, который не является графом пути. Как закодировать список смежности?


c++ graph adjacency-list
person user1001776    schedule 19.10.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Простой пример: предположим, у вас есть тип вершины Vertex. Ваш граф состоит из набора вершин, которые вы можете реализовать как:

std::unordered_set<Vertex> vertices;

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

typedef std::pair<Vertex, Vertex> Edge;
std::list<Edge> edges_as_list;
std::unordered_set<Edge> edges_as_set;

(Возможно, вы захотите снабдить последний набор неориентированным компаратором, для которого (a,b) == (b,a), если у вас есть неориентированный граф.)

С другой стороны, если вы хотите создать представление в виде матрицы смежности, вы должны вместо этого создать массив логических значений и указать, какие вершины имеют между собой ребра:

bool edges_as_matrix[vertices.size()][vertices.size()]; // `vector` is better
// edges_as_matrix[i][j] = true if there's an edge

(Для этого вам понадобится способ перечисления вершин. В неориентированном графе матрица смежности симметрична, а в ориентированном графе это не обязательно.)

Представление списка лучше, если ребер мало, а матричное представление лучше, если ребер много.

person Kerrek SB    schedule 19.10.2011
comment
здорово, что вы рассмотрели список и матрицу - person user1001776; 19.10.2011
comment
Вы уверены, что это список смежности? Список смежности — это не просто список пар ребер/вершин. - person Alex P.; 15.03.2015

arrow_upward
3
arrow_downward 

struct Node {
    std::vector<std::shared_ptr<Node>> Neighbors;
};
struct AdjacencyList{
    std::vector<std::shared_ptr<Node>> Nodes;
};

AdjacencyList содержит массив всех Node, и каждый Node имеет ссылки на все остальные Node в списке. Технически класс AdjacencyList не требуется, все, что требуется, это std::shared_ptr<Node> root;, но наличие AdjacencyList с vector значительно упрощает перебор их и многое другое.

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

AdjacencyList содержит указатели на A, B, C, D, E и F.
A содержит указатели на B и C.
B содержит указатели на A и D и E.
C содержит указатели на A.
D содержит указатели на B и E. E имеет указатели на B и D.
F не имеет указателей на другие узлы.

Список AdjacencyList должен содержать указатели, а не значения Node, иначе при изменении размера все указатели Neighbors будут признаны недействительными.

person Mooing Duck    schedule 19.10.2011
comment
ХОРОШО. я сделал это на бумаге, пытаясь решить головоломку, прежде чем я знал правильную академическую терминологию. - person user1001776; 19.10.2011

arrow_upward
2
arrow_downward

Таким образом, Boost включает контейнер adjacency_list как часть boost::graph.

В общем, список смежности — это больше, чем односвязный список. Он описывает прямые соединения (потенциально заданного направления) любой вершины с другими вершинами графа.

документы по повышению эффективности содержат несколько основных примеров, с картинками.

person Joe    schedule 19.10.2011