Направленный граф, находящий узел, входные ребра которого не все достижимы из данного узла

Question

В недавнем интервью мне задали следующий вопрос.

Дан набор узлов и ребер с начальным узлом, указывающим на конечный конечный узел. На приведенной ниже диаграмме он начинается с 1 и заканчивается на 15. Их вопрос был дан Узлу 2 (или любому узлу) в качестве отправной точки, как мы можем найти следующий узел на своем пути, входные ребра которого не все достижимы из Узла 2 ( т.е. как мы можем достичь 14).

Как я могу это сделать, псевдокод должен подойти.

Answer 1

1. Отметьте все ребра, которые достижимы от начального узла.
2. Найдите первый узел, который достижим от начального узла, у которого есть немаркированные входные ребра.

Answer 2

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

• написать подпрограмму, которая расширяет родительскую карту для всех узлов ниже начального узла (используя dfs). подпрограмме не нужно исследовать узлы, которые уже являются ключами на карте.

• вызов подпрограммы выше для каждого узла в графе. это дает полную карту от узлов к родителям (по сути, транспонирование графа).

• вызовите приведенную выше подпрограмму из данного узла в вопросе (например, 2) с новой картой. это дает карту от узлов к родителям, достижимым от 2.

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

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

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

Answer 3

Я бы сказал:

1. Найти узлы, которые недоступны из узла 2. Запустите BFS или любой полный алгоритм, чтобы найти множество всех достижимых R.Найти недоступный с помощью U = V - R

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

На втором шаге вы последовательно выбираете узлы в U и выполняете BFS.Вы обрабатываете узлы по-разному:

• Всякий раз, когда вы находите узел X, принадлежащий U, который уже был выбран, вы останавливаете
• Всякий раз, когда вы находите узел Y, принадлежащийU и не выбран, вы удаляете этот узел из U
• Когда вы находите узел в R, вы помните край и помечаете этот узел как «не посещать никогда».

Answer 4

• Если этот алгоритм должен выполнить однократный поиск, просто рассмотрите StartNode:
  • Найдите все узлы, которые доступны из Start Node.(Запустив алгоритм обхода графа BFS)
  • Сохраните этот список узлов, которые доступны из StartNode, в хеш-таблице для эффективного поиска.
  • Для каждого узла, доступного из текущего узла (по порядку):
    • проверить входящие узлы (начальный верстек входящего фронта)
    • Если все входящие узлыдоступно в хеш-таблице, затем перейдите к следующему достижимому узлу - иначе верните этот узел.