Поиск по глубине
Подобно поиску в ширину , здесь мы узнаем о другом алгоритме обхода графа, называемом методом поиска в глубину . В то время как поиск по ширине ищет инкрементные длины кромок от исходного узла, поиск по глубине сначала идет по пути ребер, насколько это возможно. Как только он достигнет одного конца пути, поиск вернется к последнему узлу с не посещенным краем пути и продолжит поиск. Ниже приведена визуализация того, что делает алгоритм, когда верхний узел является отправной точкой поиска. Простым выходом этого алгоритма является список узлов, которые достижимы с данного узла. Поэтому при реализации этого алгоритма вам нужно будет отслеживать узлы, которые вы посещаете.
Напишите функцию dfs() которая принимает неориентированный graph матрицы смежности и root метки узла в качестве параметров. Метка узла будет просто числовым значением узла между 0 и n - 1 , где n - общее количество узлов на графике. Ваша функция должна выводить массив всех узлов, доступных из root .