Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
While fHead^.ArcList<>nil do begin
|
|
Arc: =fHead^.ArcList; fHead^.ArcList: = Arc^.NextArc;
Dispose(Arc);
end;
Node: = fHead; fHead: = Node^.NextNode;
Dispose(Node);
end;
fArcsNumber: = 0; fNodesNumber: = 0;
end; //procedure tOrGraph.Clear
5. Обход ориентированного графа
При решении многих задач, связанных с графами, необходим эффективный способ систематического обхода всех узлов и дуг графа. Известны два способа обхода графов: обход в ширину и обход в глубину (в теории графов они называются поиском в глубину и поиском в ширину).
Способ обхода в глубину DFS (от depth-first search – поиск в глубину) составляет основу многих других эффективных алгоритмов работы с графами и состоит в следующем. Обход начинается с некоторого начального узла v графа g. Для каждого узла, смежного с узлом v и не посещавшегося ранее, рекурсивно применяется поиск в глубину. Когда все узлы, которые можно достичь из узла v, посещены, поиск заканчивается. Этот способ называется поиском в глубину, поскольку поиск непосещенных узлов идет в направлении вперед (вглубь) до тех пор, пока это возможно.
Для решения этой задачи необходимо переопределить тип tNode, включив в него дополнительное поле Visited логического типа – признак посещения узла. Начальное значение этого поля для всех узлов равно False. Приведенный ниже метод tOrGraph.DFS для обхода графа в глубину содержит внутреннюю рекурсивную процедуру DFSR, выполняющую обход в глубину от заданного узла Node. Посещение узла в данном методе заключается в выводе значения его содержательного поля Value в файл f.
procedure tOrGraph.DFS(StartNode: pNode; var f: Text);
// Обход в глубину, начиная с узла StartNode,
// с выводом значений узлов в файл f
procedure DFSR(Node: pNode);
// Внутренняя рекурсивная процедура обхода в глубину от узла Node
Var
Arc: pArc; // дуга графа
NextNode: pNode; // узел, следующий за узлом Node
Begin
Node^.Visited: =True; // отметка узла как посещенного
Write(f, Node^.Value, ' > '); // посещение узла - вывод его значения в файл f
Arc: =Node^.ArcList; // первая дуга из списка дуг, инцидентных узлу Node
while Arc< > Nil do begin // поиск всех узлов, смежных с Node
NextNode: =Arc^.RearNode; // узел, смежный с узлом Node
if not NextNode^.Visited
then DFSR(NextNode); // узел не посещен - поиск от него
Arc: =Arc^.NextArc; // переход к следующему узлу, смежному с Node
end;
end; //procedure DFSR
Var
Node: pNode;
Begin
Node: =fHead;
while Node< > nil do begin // отметка всех узлов графа как непосещенных
Node^.Visited: =False; Node: =Node^.NextNode;
end;
DFSR(StartNode); Writeln(f);
end; // procedure tOrGraph.DFS
Способ обхода в ширину BFS (от breadth-first search – поиск в ширину) получил свое название из-за того, что при достижении во время обхода любого узла v далее рассматриваются все узлы, смежные с узлом v. После того как посещены и отмечены все не посещенные ранее узлы, смежные с узлом v, выбирается один из этих узлов и обход в ширину начинается от него, затем процесс повторяется для оставшихся смежных с v узлов. Для реализации этого алгоритма необходимо запоминать посещенные смежные с v узлы и, рассматривая их в порядке посещения, начинать процесс посещения всех узлов, смежных с ними. Для этой цели хорошо подходит такая структура данных как очередь (действительно, посещённые узлы становятся в очередь для продолжения процесса поиска от них).
procedure tOrGraph.BFS(StartNode: pNode; var f: Text);
// Обход в ширину, начиная с узла StartNode, с выводом значений узлов в файл f
Var
Arc: pArc; // дуга графа
Node, NextNode: pNode; // очередной и следующий за ним узлы графа
q: tQueue; // экземпляр очереди с элементами типа pNode
Begin
Node: =fHead;
while Node< > nil do begin // отметка всех узлов графа как непосещенных
Node^.Visited: =False; Node: =Node^.NextNode;
end;
q: = tQueue.Create; // создание экземпляра очереди
StartNode^.Visited: =True; // отметка начального узла как посещенного
Write(f, StartNode^.Value, ' > '); // посещение начального узла
q.Insert(StartNode); // включение элемента StartNode в конец очереди
while not q.Empty do begin // пока очередь не пуста
Node: =q.Remove; // исключение первого элемента из очереди
Arc: =Node^.ArcList; // первая дуга из списка дуг, инцидентных узлу Node
while Arc< > nil do begin // поиск всех узлов, смежных с Node
NextNode: =Arc^.RearNode; // узел, смежный с узлом Node
if not NextNode^.Visited // если смежный узел не посещен,
|
|