Что такое список смежности и как его кодировать? - PullRequest
Новая
       34

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

3 голосов
/ 19 октября 2011

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

Ответы [ 3 ]

5 голосов
/ 19 октября 2011

Простой пример. Предположим, у вас есть тип вершины 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), если у вас есть ненаправленный граф .)

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

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

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

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

3 голосов
/ 19 октября 2011 
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 будут недействительными.

2 голосов
/ 19 октября 2011

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

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

boost docs предоставляют несколько основных примеров с картинками.

...