Удаление ребер в графе, хранящемся в списке смежности - PullRequest
Новая
       50

Удаление ребер в графе, хранящемся в списке смежности

0 голосов
/ 07 июля 2019

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

Моя первоначальная идея состояла в том, чтобы использовать что-то вроде

vector<list<pair<Vertex, List<Vertex>::iterator>>> Graph

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

Мой вопрос заключается в том,есть способ добиться удаления ребра за O (1) времени с использованием списков смежности или есть способ как-то пометить ребро, поэтому, когда я нахожусь в соседней вершине, я точно буду знать, что ребро в противоположном направлении было пройдено,Заранее спасибо.

1 Ответ

1 голос
/ 07 июля 2019

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

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

Подход 1 - гарантированная сложность O (logE)

Просто используйте std::set вместо std::list:

std::vector<std::set<int>> Graph;

Это позволяет проходить и обрабатывать все смежные узлы одинаково: 

// adj is your graph,
// v is current vertex
for (auto &w : adj[v]) {
  // process edge [v, w]
}

Но вы можете удалить противоположный край в O (logE): 

// remove [v,w] and [w,v]
adj[v].erase(w);
adj[w].erase(v);

Подход 2 - среднее значение O (1), наихудший случай O (E)

Постоянная сложность по времени возможна с помощью std :: unordered_set, но только в среднем:

std::vector<std::unordered_set<int>> Graph;

Шаблоны обхода и стирания остаются прежними, но лично я предпочел бы подход 1. 1. 1035 *

...