связный гpаф

From

Alex Lisenko (2:465/4.8)

To

Vlad Zinchenko ()

Date

2000-02-22T16:33:53Z

Area

RU.ALGORITHMS

          Здравствуй Vlad!

 Среда март 26 2036, а Vlad Zinchenko пишет All вот что:

 VZ> Поделитесь ссылками, где можно о пpогpаммиpовании гpафов почитать. В
 VZ> частности, мне тpебyется опpеделить является ли данный гpаф связным.

        Вот исходник.

>--- Begin [GRAF4.PAS] ---<

Program Conected;
{ * For BP7
  * Проверка: связен ли Граф?
  * Как проверить работает ли АЛГ?
  * Выберите какой вам нужен из нижепреведенных Граф
  * (записав имя массива в указанном месте (* <= *) )
  * N присвойте значение N4 или N5 - какое нужно
  * A1, A2 - для N4;    - матрицы смежности
  * A3, A4 - для N5;}

CONST
  N2=2;
  N4=4;
  N5=5;
  AA:Array[1..N2,1..N2]of Integer=((0,1),(1,0));
  A1:Array[1..N4,1..N4]of Integer=((0,1,0,0),{не связен}
                                   (1,0,0,0),
                                   (0,0,0,1),
                                   (0,0,1,0));
  A2:Array[1..N4,1..N4]of Integer=((0,1,1,0),{связен}
                                   (1,0,1,0),
                                   (1,1,0,1),
                                   (0,0,1,0));
  A3:Array[1..N5,1..N5]of Integer=((0,1,0,0,0),{не связен}
                                   (1,0,1,0,0),
                                   (0,1,0,0,0),
                                   (0,0,0,0,1),
                                   (0,0,0,1,0));
  A4:Array[1..N5,1..N5]of Integer=((0,1,0,0,0),{ связен}
                                   (1,0,1,0,0),
                                   (0,1,0,1,0),
                                   (0,0,1,0,1),
                                   (0,0,0,1,0));
VAR
  D:Array[1..N5]of Integer;
  N,I,J:Integer;
  A:Boolean;
BEGiN
  Writeln('Определение связности Графа');
  Writeln('Инструкцию читать в исходнике ;)');
  Writeln('Нажмите ENTER');
  Readln;
  N:=N4;
  For I:=1 to N do D[i]:=0;
  D[1]:=1;{начинаем с первого пункта}
  (*----------------------*)
  For I:=1 to N do
  If D[i]=1 then
   For J:=1 to N do
    begin
     If A1(* <= *)[i,J]=1 then D[j]:=1;
    end;
  (*----------------------*)
  A:=True;
  For i:=1 to N do
   if D[i]=0 then A:=False;
  If A then Writeln('Данный Граф связен')
   else Writeln('Данный Граф не связен');
END.

>---  End [GRAF4.PAS]  ---<

        Всего хорошего,
              Alex Lisenko.

---
 * Origin: Origin sugarfree! (2:465/4.8)