Я хотів би знати, чи є ефективнималгоритм S = F (v, G) побудувати підграф S з DAG G = (V, E) таким чином, що всі шляхи в S містять вершину v з V. Якщо так, то можна ефективно розширити F до F "(N, G) для набору вершин N. Я відкритий для будь-яких структур даних для зберігання DAG G спочатку.
Фактично, стан, який я забув додати, полягає б у тому, що G має унікальну вершину r без вхідного краю, а шлях повинен мати форму, де d - вершина без вихідного краю.
Інший стан, який я пропустив, дає розширений F "(N, G) такий, що для всіх v, w з N, якщо <r, .., v, .., w> де w - мийка, то ми повинні ігнорувати шляхи <r, .., v, .., x> де x! = w.
У мене насправді є одне рішення, але воно не масштабне, коли #V> 2000 і #N> 2.
Відповіді:
1 для відповіді № 1Я вважаю, що ви шукаєте найбільший підграф S з G = ({r} + V + (d), E), де r - унікальний вузловий джерело, а d - раковина така, що кожен шлях від r до d передає певний вузол v
Мій запропонований алгоритм:
Знайти всі шляхи між r та v за допомогою, наприклад, відповіді наведені в Знайти шляхи між двома даними вузлами?
Знайти всі шляхи між v і використанням одного і того жалгоритм Оскільки G є ациклічним, то шлях від v до d не може повернутись до шляху, вже знайденого на кроці 1. Таким чином, у отриманому графіку всі шляхи між r та d пройдуть v.
1 для відповіді № 2
Результуючий графік містить вузли, які є доступнимивід v і вузлів v досяжна з (або, вузлів, що досягаються з v у перекладеному підграфі). Отримання набору доступних вузлів може бути здійснено ефективно.
Це може бути легко розширене для набору вузлів: ви повинні просто додати їх усіх на початку вашого широкого першого пошуку.