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

Question

Я рассматриваю реализации структуры данных графа и смотрю на представление "списка инцидентов".Вот краткое описание этого здесь:

Список инцидентов

Таким образом, каждая вершина графа хранит список тех ребер, с которыми она сталкивается.

Учитывая, что мой граф является ориентированным графом, мне не очень понятно из этого описания пара моментов:

1. Хранит ли сам график также список всех ребер?
2. Сохраняют ли вершины только исходящие ребра или входящие и исходящие?
3. Если и то, и другое, они в отдельных списках?

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

Любые указатели будут высоко оценены.

Answer 1

Я знаю, что, возможно, поднимаю старый вопрос из мертвых, но я счел уместным комментировать.

Вы можете создать структуру графика списка инцидентов, а также настроить его для орграфов.

Рассмотрим объект LinkedList<Vertex> и объект LinkedList<Edge>.Это позволит вам перебрать все ребра и все вершины, но не содержит информации о том, как все это связано.

Скажем, мы добавляем несколько LinkedList<Connection> объектов.На самом деле по одному на каждый Vertex.Connection - это просто место встречи Edge и Vertex.Таким образом, Edge будет иметь два Connection объекта (для неориентированного графа), а Vertex будет иметь один LinkedList<Connection> объект, представляющий соединения с каждым Edge, связанным с ним.По сути, это список инцидентности.

Вы можете изменить это для представления орграфа, если удалите некоторые из этих Connection объектов.В частности, вам придется выбрать, где не будет этих ссылок.Вы можете удалить Connection из связанного LinkedList<Connection>, если вы не хотите видеть Edge из Vertex (для примера выше, N2 будет иметь пустой LinkedList<Connection>),Вместо этого вы могли бы сделать ссылки необязательными для Edge (для приведенного выше примера E1 будет иметь один Connection, указывающий на N2, и один Connection, равный NULL, что позволяет переходить с E1 на N2, но не обратно на N1.Ваш выбор того, как реализовать это, будет полностью зависеть от вас. Один из них более интуитивен - ребра направлены, поэтому удаление соединений на ребрах, чтобы определить, каким образом они идут, кажется логичным. Другое на первый взгляд может показаться более сложным, ноостановит вас без необходимости прыгать по краям, которые никуда не ведут при выполнении поиска в ширину и сначала в глубину.

В форме точки:

1. В моих реализациях списка инцидентов яВам нужно для вашей реализации?

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

3. Если вы сделаете и то, и другое, вам, вероятно, понадобится какой-то способ различить, является ли он входящим или исходящим.Будь то наличие двух LinkedList<Connection> объектов на вершине или наличие boolean pointingToVertex примитива на Connection, или что-то еще.Возможно, ваши Edge будут направлены, а ненаправленные ребра будут состоять из двух ребер, указывающих противоположные пути.Соображения должны быть сделаны в зависимости от потребностей вашей структуры.

Answer 2

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

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

Использование карты наборов гарантирует O (1) для поиска вершин и амортизированную сложность O (1) для вставки и удаления ребер.Ведение списка инцидентности ребер вместо смежного списка вершин - это просто способ передать некоторую конкретную информацию о самом ребре.Это также полезно для абстрактных алгоритмов, когда, например, вы связываете вес с ребрами.

РЕДАКТИРОВАТЬ:

Я обновил переговоров в Википедии для "список заболеваемости "тема.

Answer 3

Изучив и подумав об этом, я пришел к выводу, что структуры данных графа списка заболеваемости не существует. Я думаю, что статья в Википедии была продуктом некоторой путаницы в сознании автора. Спасибо всем, кто прочитал этот вопрос и потратил на него какое-то время.

Armand