Процедура поиска в глубину в графе, заданном списками инцидентности - 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.

Объяснение кода листинга программы

  1. В программе объявлены три переменные: LstS, Chk и CurrN. LstS - это массив, который представляет собой список инцидентности для графа. Chk - это массив, который используется для отслеживания посещенных вершин в процессе обхода графа. CurrN - это переменная, которая хранит текущую вершину, которую мы исследуем.
  2. В функции isBound проверяется, является ли текущая вершина (i) соседней для вершины, которую мы исследуем (n). Если это так, то функция возвращает True и выходит из цикла. Если нет, то функция проверяет, является ли вершина n соседней для вершины i. Если это так, то она также возвращает True и выходит из цикла. Если ни одно из этих условий не выполняется, функция возвращает False.
  3. В процедуре DFS вызывается функция isBound для проверки того, что все вершины до текущей вершины были исследованы. Если это так, то текущая вершина записывается в файл вместе с ее индексом. Затем вызывается рекурсивно DFS для исследования всех соседних вершин.
  4. В начале программы создаются два массива: LstS и Chk. Затем считывается количество вершин из файла и сохраняется в переменной CurrN. Для каждой вершины в массиве LstS считывается значение и сохраняется в массиве Stri. Значение каждой вершины в Stri накапливается, пока не достигнется пробел или запятая, после чего оно преобразуется в целое число и сохраняется в массиве LstS.
  5. Затем вызывается функция DFS, передавая ей 1 в качестве аргумента. Это означает, что мы начинаем обход графа с вершины 1. В процессе обхода каждая соседняя вершина исследуется рекурсивно.
  6. В конце программы вызывается функция isBound для проверки того, что все вершины были исследованы. Если это так, то все вершины считаются посещенными, и программа завершается.

Оцени полезность:

8   голосов , оценка 4.125 из 5
Похожие ответы