Подграф графа заданной начальной вершины

Question

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

Я уже выполнил это требование, но мне любопытно, есть ли более эффективное решение. Решение, которое я придумал, состояло в том, чтобы сделать DFS графа и записать каждую вершину, которая встречалась в наборе S. Затем я просто взял все ребра из исходного графа, которые были связаны с вершиной в S, и я построил подграф из него. Ребра в исходном графике хранятся в словаре C #, который, я считаю, в основном является хешем.

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

Есть ли лучшее решение, чем то, которое я придумал?

Answer 1

Я думаю, что обход BFS является наиболее эффективным алгоритмом для этого.

Если вы выполняете BFS и ставите в очередь всех соседей для каждого узла (т. Е. Пересекаете все ребра, прикрепленные к текущему узлу) и прерываете обход, только когда текущий узел уже был посетив, вы избежите описанной вами проблемы с "тем же ребенком" / "пропущенными ребрами".

Answer 2

«быстрый» алгоритм, который перечисляет все индуцированные подграфы указанный размер можно найти здесь:

http://theinf1.informatik.uni -jena.de / ~ Верник / мотивы-wabi2005.pdf

это помогает?