Процедура поиска в глубину в графе, заданном списками инцидентности - Pascal ABC
Формулировка задачи:
Нужна помощь знающего Паскаль человека, по заданию:
Напишите и используйте в программе процедуру поиска в глубину в графе, заданном списками инцидентности. Выведите на экран номера вершин в том порядке, в котором они просматриваются процедурой.
Буду очень признателен за помощь!
Решение задачи: «Процедура поиска в глубину в графе, заданном списками инцидентности»
textual
Листинг программы
Program P62; Const MAX_VERT = 100; Var LstS : Array[1..MAX_VERT,1..MAX_VERT] of integer; Var Chk : Array[1..MAX_VERT] of integer; Var CurrN : integer; Var finp : Text; Var i,j,l,k : integer; Var Stri,s,tmp : String; Function isBound(i,j : integer) : Boolean; Var k : integer; Begin for k:=1 to CurrN Do if LstS[i,k]=j Then Begin isBound:=True; exit; End; For k:=1 to CurrN Do if LstS[j,k]=i Then Begin isBound:=True; exit; End; isBound:=False; End; Procedure DFS(n : integer); Var i : integer; Begin Chk[n]:=1; for i:=1 to CurrN Do if (Chk[i]=0) And (isBound(i,n)) Then Begin writeln(n,' - ',i); DFS(i); end; End; Begin for i:=1 to MAX_VERT Do Begin Chk[i]:=0; for j:=1 to MAX_VERT Do Lsts[i,j]:=0; end; assign(finp,'graph.txt'); reset(finp); readln(finp,CurrN); for i:=1 to CurrN Do Begin readln(finp,Stri); Stri:=Stri+','; l:=length(Stri); tmp:=''; k:=1; for j:=1 to l Do Begin s:=Stri[j]; if s <> ' ' then if s = ',' then Begin if tmp <> '' then Begin Lsts[i,k]:=strToint(tmp); tmp:=''; k:=k+1; End; End Else tmp:=tmp+s; End; End; Close(finp); DFS(1); writeln; End.
Объяснение кода листинга программы
- В программе объявлены три переменные: LstS, Chk и CurrN. LstS - это массив, который представляет собой список инцидентности для графа. Chk - это массив, который используется для отслеживания посещенных вершин в процессе обхода графа. CurrN - это переменная, которая хранит текущую вершину, которую мы исследуем.
- В функции isBound проверяется, является ли текущая вершина (i) соседней для вершины, которую мы исследуем (n). Если это так, то функция возвращает True и выходит из цикла. Если нет, то функция проверяет, является ли вершина n соседней для вершины i. Если это так, то она также возвращает True и выходит из цикла. Если ни одно из этих условий не выполняется, функция возвращает False.
- В процедуре DFS вызывается функция isBound для проверки того, что все вершины до текущей вершины были исследованы. Если это так, то текущая вершина записывается в файл вместе с ее индексом. Затем вызывается рекурсивно DFS для исследования всех соседних вершин.
- В начале программы создаются два массива: LstS и Chk. Затем считывается количество вершин из файла и сохраняется в переменной CurrN. Для каждой вершины в массиве LstS считывается значение и сохраняется в массиве Stri. Значение каждой вершины в Stri накапливается, пока не достигнется пробел или запятая, после чего оно преобразуется в целое число и сохраняется в массиве LstS.
- Затем вызывается функция DFS, передавая ей 1 в качестве аргумента. Это означает, что мы начинаем обход графа с вершины 1. В процессе обхода каждая соседняя вершина исследуется рекурсивно.
- В конце программы вызывается функция isBound для проверки того, что все вершины были исследованы. Если это так, то все вершины считаются посещенными, и программа завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д