DAG, поиск ребер для подмножества вершин

Question

У меня DAG G = (V, E), это представление списка смежности.Я пытаюсь сжать его в соответствии с некоторыми параметрами, которые привязаны к вершинам.

Теперь у меня есть граф G = (V, E) и список, содержащий подмножество V.

Есть идеи, как мне эффективно найти ребра для подмножеств вершин из исходного графа?

Мне нужно подключить подмножество с использованием исходного графика.

Посмотрите на этот график

{9: [10], 7: [9], 8: [9], 6: [7], 3: [8], 2: [3, 4], 5: [4, 6], 4: [7], 1: [2]}

Теперь, еслиЯ беру подмножество [1,4,7]

Как найти соединения для подмножества?пожалуйста, смотрите транзитивное закрытие как проблему.Мне нужно найти все ребра, но не дубликаты в транзитивном замыкании.

Answer 1

Если ваше подмножество S, вы можете сделать | S | поиск в глубину (или поиск в ширину ), чтобы определить ребра в вашем подмножестве графа.Каждый поиск O (V + E) , то есть O (V ^ 2 + VE) или лучше O (S (V + E)) ,если S мало.Затем вы можете использовать транзитивное сокращение для удаления ненужных ребер.

Если ваш график не является полностью ациклическим, он почти наверняка поможет объединить сильно связанные компоненты первый.Это дешево и может существенно сократить требуемую работу.

Answer 2

Простой метод - найти транзитивное замыкание исходного графа (используя Флойд-Варшалл ) и затем использовать его для добавления ребер к результирующему графу.

Найдя транзитивное замыкание, вы получите матрицу смежности, где matrix [x] [y] истинна, когда есть какой-либо путь (прямой или косвенный) между вершинами x и y в исходном графе.Используя это, вы можете просто добавить ребра (a, b) для каждой пары вершин a и b в графе подмножества, если матрица [a] [b] истинна (т.е. в исходном графе был путь от a до b)).

Это добавит больше ребер, чем строго необходимо, но даст вам точный график подмножества.

Answer 3

Сначала вам нужно будет использовать некоторый алгоритм, чтобы получить транзитивное замыкание. Из вашего примера кажется, что график очень разреженный, поэтому вместо Флойд-Варшалла используйте Алгоритм Джонсона . Алго Джонсона требует O ((V ^ 2) * log V + VE), который меньше, чем O (V ^ 3) Флойд-Варшалла для разреженных графов. Обратите внимание, что эта разница заметна только в том случае, если у вас большой разреженный график.

Теперь добавьте ребра формы для каждой пары вершин в графе подмножеств, если x достижим от y (что будет дано алгоритмом Джонсона).

Answer 4

Поместите подмножество (назовем его S ) в хеш-таблицу.Затем пройдитесь по списку смежности и для каждого ребра посмотрите, находится ли его первая вершина в хеш-таблице.Таким образом, вы получите все необходимые кромки в O (| S | + | E |).