Структура данных для ориентированных графов, позволяющая быстро удалять узлы? - PullRequest
Новая
       45

Структура данных для ориентированных графов, позволяющая быстро удалять узлы?

8 голосов
/ 23 февраля 2011

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

Если я сохраню список ребер (в виде пар индексов узлов), то при уничтожении какого-либо узла n мне придется искать во всем списке ребра, у которых источником или целью является n. Это слишком дорого для моего приложения. Можно ли избежать этого поиска, сохранив некоторые дополнительные данные в узлах?

Одна идея состоит в том, чтобы каждый узел сохранял свои собственные источники и цели в виде двух отдельных списков. Когда узел n уничтожен, его списки тоже уничтожены. Но тогда как все цели / источники, связанные с узлом n, узнают об обновлении своих списков (то есть об удалении несуществующего узла из своих списков)? Это потребует некоторых дорогостоящих поисков ...

Можно ли этого избежать?

Thx.

Ответы [ 2 ]

4 голосов
/ 23 февраля 2011

Вы можете выбрать один из двух вариантов: Список смежности и Матрица смежности. Первое, вероятно, лучше всего подходит для того, что вы делаете. Чтобы удалить узел, просто удалите список для этого узла для всех его внешних ребер. Для ребер можно рассмотреть возможность сохранения хеш-таблицы для каждого списка для O (1) поиска.

Это хороший обзор http://www.algorithmist.com/index.php/Graph_data_structures

2 голосов
/ 24 февраля 2011

Я решил это!Это решение для ненаправленных графов, после чего легко добавить направление.

В каждой вершине у меня есть специальный список смежности.Это список (с двойной связью, для простоты вставки / удаления), элементы которого являются «слотами»: 

class Slot {
  Slot prev, next; // pointers to the other slots in the list
  Slot other_end; // the other end of the edge: not a vertex, but a Slot!
  Vertex other_vertex; // the actual vertex at the other end

  void kill() {
    if (next!=null) next.kill(); // recursion
    other_end.pop_out();
  }

  void pop_out() {
    if (next!=null) next.prev = prev;
    if (prev!=null) prev.next = next;
    else other_end.other_vertex.slot_list = next; // in case this slot is the
                                                  // first in its list, I need
                                                  // to adjust the vertex's
                                                  // slot_list pointer.
    // other_end.other_vertex is actually the vertex to which this slot belongs;
    // but this slot doesn't know it, so I have to go around like this.
  }

}

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

Когда вершина убита, она рекурсивно посылает сигнал «убить» вверх по списку слотов.Каждый слот отвечает, уничтожая свой other_end (который любезно выскакивает из списка соседей, исправляя предыдущие / следующие указатели позади).

Таким образом, вершина плюс все ее ребра удаляются без какого-либо поиска.Цена, которую я должен заплатить, - это память: вместо 3 указателей (prev, next и vertex для обычного двойного связанного списка смежности) я должен оставить 4 указателя (prev, next, vertex и other_end).

Это основная идея.Для ориентированных графов мне нужно только как-то различать слоты IN и OUT.Возможно, разделив список смежности каждой вершины на два отдельных списка: IN_slot_list и OUT_slot_list.

...