Что такое обход в программировании
Перейти к содержимому

Что такое обход в программировании

  • автор:

Учебники. Программирование для начинающих.

Проектирование, изготовление и монтаж крафтовых заборов из камня в Московской области.. Соблюдение Вашей конфиденциальности важно для нас. По этой причине, мы разработали Политику Конфиденциальности, которая описывает, как мы используем и храним Вашу информацию. Пожалуйста, ознакомьтесь с нашими правилами соблюдения конфиденциальности и сообщите нам, если у вас возникнут какие-либо вопросы.

Programm.ws — это сайт, на котором вы можете почитать литературу по языкам программирования , а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..

Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.

Ассемблер — примеры и задачи

Глава 2. Сложные структуры данных

Обход узлов дерева

Возможны три варианта обхода дерева:

  • сверху вниз — корень, левое поддерево, правое поддерево;
  • слева направо — левое поддерево, корень, правое поддерево;
  • снизу вверх — левое поддерево, правое поддерево, корень.

Понятно, что процедура обхода рекурсивна. Под термином «обход дерева» понимается то, что в соответствии с одним из определенных выше вариантов посещается каждый узел дерева и с его содержательной частью выполняются некоторые действия. Для нашей задачи подходит только второй вариант, так как только в этом случае порядок посещения узлов будет соответствовать упорядоченному массиву. В качестве полезной работы будем извлекать значение из узла двоичного дерева и выводить его в массив в памяти. Отметим особенности функции LRBeat, производящей обход дерева. Во-первых, она рекурсивная, во-вторых, в ней для хранения адресов узлов используется свой собственный стек. Стек, поддерживаемый на уровне архитектуры микропроцессора, используется для работы процедурного механизма, и мы со своими проблемами только «путаемся у него под ногами».

:prg02_13.asm — программа обхода двоичного дерева поиска (слева направо). ;Вход: произвольный масиив чисел в памяти. :Выход: двоичное дерево в памяти.
объявления структур: nodejxee struc :узел дерева
ends
: для программного стека
desc_stk struc :дескриптор стека
ends
•.описание макрокоманд работы со стеком:
create_stk macro HandHead:REQ.descr:REQ.Si zeStk:=
¦.создание стека
endm
push_stk macro descr:REQ.rg_item:REQ
добавление элемента в стек
endm
pop_stkmacro descr:REQ. rg_item:REQ
извлечение элемента из стека
endm
.data
исходный массив:
masdb 37h.l2h,8h.65h.4h.54h.llh.02h.32h,5h,4h,87h.7h.21h.65h.45h.22h,llh.77h.
51h.26h.73h.35h.12h.49h.37h.52h l_mas=$-mas
упорядоченный массив (результат см. в отладчике): ordered array db 1 mas dup (0)
doubleWord_stkdesc_stk <> -.дескриптор стека
count call dd 0 :счетчик количества рекурсивного вызова процедуры
.code
BuildBinTree proc ;см. prg02_12.asm
:двоичное дерево поиска построено
ret
BuildBinTree endp LRBeat proc
:рекурсивная процедура обхода дерева — слева направо :(левое поддерево, корень, правое поддерево)
inc count_call ;подсчет количества вызовов процедуры
:(для согласования количества записей и извлечений из стека)
cmp ebx.O
je @@exit_p
mov ebx.[ebx].l_son
cmp ebx, 0
je @@ml
push_stk doubleWord_stk.ebx mini: call LRBeat
pop stkdoubleWord stk.ebx
r r_ —
jnc @@m2
:подчистим за собой стек и на выход raovecx.count_call
dec ecx
pop NewNode:pop «в никуда»
loop $-6
jmp @@exi t_p @@m2: moval,[ebx].simbol
stosb
mov ebx, [ebx]. r_son cmp ebx.O je @@ml push stk doubleWord stk.ebx
c’all LRBeat » @@exit_p: deccount_call
ret
LRBeat endp start proc near ;точка входа в программу:
call BuildBinTree :формируем двоичное дерево поиска ;обходим узлы двоичного дерева слева направо и извлекаем значения ;из содержательной части, нам понадобится свой стек (размер (256 байт) нас устроит. :но макроопределение мы подкорректировали)
create_stk Hand_Head.doubieWord_stk
push ds
pop es
lea edi.ordered_array
mov ebx.HeadTree push_stk doubleWord_stk.ebx указатель на корень в наш стек
call LRBeat

Еще одно замечание о рекурсивной процедуре. Реализация рекурсивное™ в программах ассемблера лишена той комфортности, которая характерна для языков высокого уровня. При реализации рекурсивной процедуры LRBeat возникает несбалансированность стека, в результате после последнего ее выполнения на вершине стека лежит не тот адрес и команда RET отрабатывает неверно. Для устранения подобного эффекта нужно вводить корректировочный код, суть которого заключается в следующем. Процедура LRBeat подсчитывает количество обращений к ней и легальных, то есть через команду RET, выходов из нее. При последнем выполнении анализируется счетчик обращений countcal 1 и производится корректировка стека.
Для полноты изложения осталось только показать, как изменится процедур;!. LRBeat для других вариантов обхода дерева.
Построенное выше бинарное дерево теперь можно использовать для дальнейших операций, в частности поиска. Для достижения максимальной эффективности поиска необходимо, чтобы дерево было сбалансированным. Так, дерево считается идеально сбалансированным, если число вершин в его левых и правых поддеревьях отличается не более чем на 1. Более подробные сведения о сбалансированных деревьях вы можете получить, изучая соответствующую литературу. Здесь же будем считать, что сбалансированное дерево уже построено. Разберемся с тем, как производить включение и исключение узлов в подобном, заранее построенном упорядоченном дереве.

Включение узла в упорядоченное бинарное дерево

Задача включения узла в дерево уже была решена нами при построении дерева. Осталось оформить соответствующий фрагмент программы в виде отдельной процедуры addNodeTree. Чтобы не дублировать код, разработаем рекурсивный вариант процедуры включения — addNodeTree. Он хоть и не так нагляден, как нерекурсивный вариант кода в программе prg_03.asm, но выглядит достаточно профессионально. Текст процедуры addNodeTree вынесен на дискету.
Работу процедуры addNodeTree можно проверить с помощью программы prgO2_ 13.asm (в ПРИМЕРе ей соответствует программа prgO2_14.asm).
В результате проведенных работ мы получили дублирование кода, строящего и дополняющего дерево. В принципе для строительства и включения в дерево достаточно одной процедуры addNodeTree. Но в учебных целях мы ничего изменять не будем, чтобы иметь два варианта строительства дерева — рекурсивный и не рекурсивный. При необходимости читатель сам определит, какой из вариантов более всего отвечает его задаче и в соответствии с этим доработает этот код.
Исключение узла из упорядоченного бинарного дерева
Эта процедура более сложная. Причиной тому то обстоятельство, что существует несколько вариантов расположения исключаемого узла в дереве: узел является листом, узел имеет одного потомка и узел имеет двух потомков. Самый непростой случай — последний. Процедура удаления элемента del NodeTree является рекурсивной и, более того, содержит вложенную процедуру del, которая также является рекурсивной. Текст процедуры del NodeTree вынесен на дискету.
Работу этой процедуры можно проверить с помощью программы prg02_13.asm (в ПРИМЕРе ей соответствует программа prg02_15.asm).
Графически процесс исключения из дерева выглядит так, как показано на рис. 2.20. Исключаемый узел помечен стрелкой.

Рис. 2.20. Исключение из дерева

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

Алгоритмы. Обход дерева

Давно я не писал, как то все времени не находилось. Мы говорили про деревья, давайте теперь поговорим про обход деревьев. Обходы деревьев нужны собственно для того чтоб оптимально быстрой найти необходимый элемент в дереве.

Собственно обход дерева, как и все обходы графов ( а дерево это обычный неориентированный граф ) делается двумя методами: в глубину (Depth-first) и в ширину (Breadth-first).

Какой из методов использовать?

На самом деле споров достаточно много, и если зайти на различные форумы — то вы получите огромное количество ответов, каждый из которых не факт что будет полезен для вас. Потому, для себя я решил таким образом( взято кстати с треда на stackoverflow):

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

Собственно, как я уже и писал, правильного ответа нет — потому надо пробовать разные варианты:) Эксперементировать всегда весело!

Так как мы будем пробовать на созданном бинарном дереве все алгоритмы, они редко бывают широкими, потому обсудим в начале поиск в глубь.

DFS. Алгоритмы в глубь имеют три типа обходов:

Pre-order стоит использовать именно тогда, когда вы знаете что вам нужно проверить руты перед тем как проверять их листья.

В результате Pre-order обхода мы получим такой порядок :

function preOrder(node) if (node == null) return; 
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
>

In-order обход используется как раз когда нам надо проверять в начале детей и только потом подыматься к родительским узлам.

В таком случае мы получаем просто: A,B,C,D,E,F,G,H,I

function inOrder(node) if (node == null) return; 
inOrder(node.left);
console.log(node.value);
inOrder(node.right);
>

Post-order самый забавный случай — это случай когда нам нужно начать-так сказать с листов и завершить главным узлом — тоесть разложить дерево на то, как оно строилось.

В таком случае мы полчаем: A, C, E, D, B, H, I, G,F

function postOrder(node) if (node == null) return; 
postOrder(node.left);
postOrder(node.right);
console.log(node.value);
>

Как видим — код очень похож:) просто разный порядок вызовов.

BFS точно такой же как и в графах. Все достаточно просто — мы бегаем в начале по рут ноде, потом по всем ее детям, потом по всем детям детей, и так далее.

function bfs(node) var queue = []; 
var values = [];
queue.push(node);
while(queue.length > 0) var tempNode = queue.shift();
values.push(tempNode.value);
if (tempNode.left) queue.push(tempNode.left);
>
if (tempNode.right) queue.push(tempNode.right);
>
>
return values;
>

Собственно на этом пока все:)

Как обычно: исходники примеров вы можете найти тут.

Методы программирования

Задание состоит из трех частей, первая и третья обязательны для выполнения, вторая выполняется по желанию студента. Срок сдачи задания — 17 октября.

Теория

Двоичное дерево задается следующей структурой:

typedef struct _t int data; /* данные в узле */
struct _t *left, *right; /* указатели на левого и правого сыновей */
> t;

t *root; /* корень дерева */

Таким образом, каждый элемент дерева содержит некоторые данные и два указателя на потомков (на левого сына и на правого). Сам узел будем называть отцом этих двух потомков. Определение дерева требует, чтобы у каждого узла, кроме корня, был ровно один отец. Указатель на корень дерева хранится в переменной root , она равна нулю, если дерево пусто.

Левым и правым поддеревьями узла t ( t != 0 ) будем называть деревья (возможно, пустые), корнями которых являются соответственно t->left и t->right .

Основные операции на деревьях: поиск элемента, добавление элемента, удаление элемента. Для поиска элемента в произвольном бинарном дереве необходимо обойти все элементы этого дерева. Существует два основных способа обхода дерева: в глубину и в ширину.

Обход дерева в глубину

Обход в глубину производится рекурсивно либо с использованием стека. В обоих случаях можно обходить узлы дерева в различной последовательности. Обход начинается от корня. Выделяют три наиболее важных порядка обхода в глубину:

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

В качестве примера рассмотрим следующее дерево:

Пример бинарного дерева

  • префиксный обход: A, B, D, H, E, C, F, I, J, G
  • инфиксный обход: D, H, B, E, A, I, F, J, C, G
  • постфиксный обход: H, D, E, B, I, J, F, G, C, A

Запишем в качестве примера рекурсивную процедуру, выводящую на экран узлы дерева в порядке префиксного обхода.

void prefix(t *curr)
if (!curr)
return;
printf(«%d «, curr->data);
prefix(curr->left);
prefix(curr->right);
>

Обход дерева в ширину

Обход в ширину производится с помощью очереди. Первоначально в очередь помещается корень, затем, пока очередь не пуста, выполняются следующие действия:

  • Из очереди выталкивается очередной узел;
  • Этот узел обрабатывается;
  • В очередь добавляются оба сына этого узла.

Узлы дерева на рисунке перечисляются в порядке обхода в ширину следующим образом: A, B, C, D, E, F, G, H, I, J. Заметим, что перечисление узлов происходит в порядке удаления от корня, что делает поиск в ширину удобным, например, для поиска узла дерева со значением k , наиболее близкого к корню, и т.д.

Приведем пример процедуры, которая выводит на экран узлы дерева в порядке обхода в ширину. Считаем, что определены три функции:

void add(t *elem); /* добавляет в конец очереди элемент elem */
t *del(); /* удаляет из очереди первый элемент и возвращает указатель на него */
int empty(); /* возвращает 1, если очередь пуста, и 0 в противном случае */

Тогда процедура обхода будет иметь следующий вид:

void width(t *root)
if (!root)
return;
add(root);
while (!empty()) t *curr = del();
printf(«%d «, curr->data);
if (curr->left)
add(curr->left);
if (curr->right)
add(curr->right);
>
>

Двоичные деревья поиска

Для поиска узла в таком дереве можно использовать как рекурсивную функцию, так и простой цикл. Ниже приведен пример функции, которая ищет узел со значением k в двоичном дереве поиска с корнем root . Этот код весьма напоминает обычный бинарный поиск:

t *search(t *root, int k)
t *curr = root;
while (curr) if (k == curr->data)
return (curr);
if (k < curr->data)
curr = curr->left;
else
curr = curr->right;
>
return (0);
>

Добавление узла в двоичное дерево поиска напоминает добавление элемента в середину связанного списка: выполняется проход по дереву с запоминанием указателя на узел, предшествующий текущему, и добавление узла к предыдущему, как только текущий указатель станет равным нулю. Необходимо отдельно обработать случай пустого дерева.

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

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

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

Сбалансированным деревом (AVL-деревом) называется двоичное дерево поиска, удовлетворяющее следующему условию: для любого узла глубина левого поддерева отличается от глубины правого поддерева не более чем на 1. В сбалансированном дереве поиск элемента выполняется за время O(log2N), где N — количество узлов (Адельсон-Вельский, Ландис, 1962). Алгоритм построения сбалансированных деревьев можно найти в сети и в литературе (Вирт, Кнут, . ), поэтому подробное описание его здесь не приводится.

Формулировка задания

а. Реализация простых двоичных деревьев поиска

Во входном файле input.txt в первой строке находится количество записей N , в следующих N строках находятся записи вида имя значение , причем имена могут повторяться. В файл output.txt выдать итоговые значения всех переменных в алфавитном порядке. Хранение записей организовать в виде двоичного дерева поиска.

Примеры
Ввод: input.txt
5
a 10
b 20
a 15
c 25
b 11
Вывод: output.txt
a 15
c 25
b 11
b. ** Реализация сбалансированных деревьев

Задание аналогично предыдущему, но требуется поддерживать дерево сбалансированным. Задание не является обязательным.

c. Реализация префиксного, инфиксного и постфиксного обходов двоичного дерева

Необходимо реализовать функции обхода дерева в порядке префиксного, инфиксного и постфиксного обходов. Дерево задается произвольным образом.

Что такое обход в программировании

DFS, или Depth First Search, — поиск в глубину, позволяющий найти маршрут от точки A до точки B. Используется в графах — особых структурах, состоящих из точек-вершин и ребер-путей. DFS ищет маршрут по графу “в глубину”: на каждом шаге “уходит” все дальше.

Освойте профессию «Data Scientist»

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

Пример использования алгоритма

Профессия / 24 месяца
Data Scientist

Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.

Group 1321314349 (1)

DFS ищет случайный путь. Существует еще один известный алгоритм BFS, о котором у нас есть статья: тот ищет самый короткий путь.

Кроме лабиринтов, DFS может “пройти” практически по любому графу или дереву.

Кто пользуется алгоритмом

  • Математики, которые работают с теорией графов для решения фундаментальных или практических задач.
  • Специалисты по анализу данных и по искусственному интеллекту, так как графы часто используются в Data Science или в машинном обучении.
  • Разработчики, которым бывает необходимо решать задачи поиска маршрутов, расчета потоков и другие подобные. Такие задачи могут встретиться во многих проектах: от картографического сервиса до онлайн-игры.
  • Сетевые инженеры, так как в виде графов представляют компьютерные сети, а многие сетевые протоколы основаны на алгоритмах работы с графами.
  • Иногда — другие специалисты, которым бывает нужно столкнуться с теорией графов. Вариации DFS используются в том числе в жизни.

Для чего нужен алгоритм DFS

  • Для поиска любого маршрута в лабиринте. В отличие от алгоритма BFS, поиск в глубину ищет не самый короткий, а случайный путь. Правило прохождения лабиринта в реальной жизни “Идти с левой рукой на стене и всегда поворачивать влево” — пример DFS вне программирования.
  • Для решения задач, связанных с построением маршрута: в сети, на карте, в сервисах покупки билетов и так далее. При этом непосредственно для поиска DFS используется не так часто — он чаще нужен для исследования топологии графа.
  • Как составная часть расчетов в более сложных алгоритмах, например для определения максимального транспортного потока.
  • Для решения ряда задач из теории графов, которые используются в программировании и математике: поиска циклов, сортировки и так далее. Мы подробно поговорим об этом ниже.

Модификации DFS

Алгоритм можно модифицировать, чтобы решить другие задачи из теории графов:

  • проверить граф на двудольность. Двудольным называется граф, вершины которого можно разбить на две группы так, чтобы концы каждого ребра принадлежали вершинам из разных групп;
  • найти в ориентированном графе цикл. Ориентированный граф — такой, у ребер которого есть направление. Об этом можно подробнее прочесть в нашей статье. Цикл — это замкнутый контур из вершин и ребер внутри графа: проходя по нему, в результате придешь в начальную точку;
  • отсортировать и упорядочить ориентированный граф, дать вершинам номера так, чтобы ребра шли от меньшего номера к большему;
  • преобразовать “синтаксическое дерево”, подвид графа, в строку;
  • найти в графе определенные точки, например, так называемые мосты или шарниры.

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

Станьте дата-сайентистом и решайте амбициозные задачи с помощью нейросетей

При чем тут рекурсия

Классическая реализация DFS — рекурсивная. Рекурсией называется процесс, когда какая-то функция вызывает себя же, но с другими аргументами. В результате одна и та же функция одновременно остается запущенной несколько раз, пока в одной из итераций не дойдет до финального решения. Тогда она вернет результат и закроется, а по каскаду закроются и все функции, приведшие к ее вызову.

С помощью рекурсии решают задачи, связанные с “глубоким” прохождением по данным. Очевидный пример — расчет чисел Фибоначчи, когда на каждом следующем шаге функция складывает два предыдущих числа. Задача DFS тоже классически решается с помощью рекурсивного алгоритма.

Но не всегда рекурсия оптимальна. Поддержка сразу нескольких запущенных одинаковых функций может отнимать много аппаратных ресурсов, поэтому существуют и нерекурсивные реализации. Их тоже нужно знать, чтобы избежать переполнения стека и других ситуаций, когда рекурсивная реализация может “упасть”.

Принцип обхода графа в глубину

Мы рассмотрим стандартный рекурсивный алгоритм обхода. О нерекурсивных реализациях поговорим ниже: их есть несколько, и у каждой свои особенности. Стандартный же принцип довольно простой для понимания, и его легко реализовать.

Первый шаг. Когда алгоритм начинает работу, все вершины считаются “белыми”, непосещенными. DFS начинает путь в заранее заданной вершине v и должен найти от нее путь до другой заданной вершины или же полностью составить карту графа.

Первое, что делает DFS, — красит вершину, в которой находится, в серый цвет. Это показывает, что алгоритм в ней уже был . Затем DFS проверяет соседей — вершины, которые соединены с той, где он находится.

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

Выбор соседа происходит случайно или по заранее заданным критериям — например, это может быть самая левая или самая правая вершина. Выше мы упоминали “правило левой руки”: оно по сути является таким критерием.

Если неисследованных соседей у вершины не осталось, она красится в черный цвет как полностью посещенная.

Завершение обхода. Алгоритм завершается, если достигает нужной точки. В таком случае все вызванные “экземпляры” функции поочередно завершаются: от последнего до первого вызванного. Если задача — полностью перебрать граф, то критерий для завершения другой: все вершины должны стать черными.

Нерекурсивные реализации

Так как рекурсия отнимает много программных ресурсов, есть несколько реализаций без ее использования. Они сложнее в написании, но могут сэкономить время работы программы.

Самый простой вариант — по-особому хранить в памяти посещенные вершины. Для этого используется такая структура данных, как стек, — о ней можно прочитать в нашей статье. В стек поочередно помещаются непосещенные вершины-соседки, и тот используется как “карта” для будущих посещений. Этот способ тоже нагружает программные ресурсы, но не так сильно.

Второй вариант — хранить в стеке не сами вершины, а их номера и номера смежных с ними вершин. Это сложнее и, по сути, является имитацией так называемого стека вызовов — участка памяти, где хранятся вызванные функции. Именно его может перегрузить рекурсия.

Третий способ — реализовать сам граф на указателях: помещать в каждой вершине указатели на предыдущие и номера смежных вершин.

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

Как реализовать алгоритм DFS

Самая простая рекурсивная реализация — создать граф в виде связанного списка или другой структуры данных, а потом написать функцию для его прохождения. Как реализовать сам граф — зависит от языка программирования: обычно используются типы, позволяющие хранить множество значений. Каждый элемент такого “комплексного” типа является вершиной, а внутри вершины хранятся ссылки на другие элементы или их номера — так реализованы пути.

Сама же функция, условно названная DFS (v), довольно простая и действует по следующей логике.

  1. На вход поступает белая вершина v.
  2. Вершина v окрашивается в серый.
  3. Ищется вершина w, смежная с v и белая.
  4. Изнутри DFS (v) рекурсивно вызывается DFS (w).
  5. Когда функция завершается, вершина v окрашивается в черный.

“Окрашивание” можно реализовать с помощью какой-либо переменной внутри вершины: например, значение 0 — белая, 1 — серая, и так далее.

Если сейчас часть информации кажется неочевидной — не страшно! Вы можете больше узнать про графы, рекурсию и использование DFS, если запишетесь на профессиональные курсы. Под контролем менторов вам будет легче разобраться в том, как это работает.

Data Scientist

Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.

картинка (74)

Статьи по теме:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *