графы, алгоритмы на графах Опции

[virt]

Графы можно представлять в виде множества вершин и множества соединяющих их ребер. (Города и дороги их соединяющие)

1. Просмотр вершин графа в некотором фиксированном порядке.

общие структуры данных :

const Maxn=100;
var a:array[1..Maxn,1..Maxn]of integer;
    Nnew:array[1..Maxn]of boolean;
    n,i,j:integer;

поиск в глубину :

{ рекурсивный вариант }
procedure Pg(v:integer);
var i:integer;
begin
   Nnew[v]:=false;
   write(v:2);
   for i:=1 to n do
      if (a[v,i]<>0) and Nnew[i] then Pg(i);
end;

{ нерекурсивный вариант }
procedure Pg_nonrec(v:integer);
var St:array[1..Maxn]of integer;
    yk:integer;
    t,j:integer;
    pp:boolean;
begin
   fillchar(St,sizeof(St),0);
   yk:=1;
   St[yk]:=v;Nnew[v]:=false;
   write(v:2);
   while yk <> 0 do
      begin
         t:=St[yk];j:=0;pp:=false;
         repeat
            if (a[t,j+1] <> 0) and Nnew[j+1] then pp:=true
               else inc(j);
         until pp or (j >= n);
         if pp then
            begin
               inc(yk);St[yk]:=j+1;Nnew[j+1]:=false;
               write(j+1:2);
            end else
               dec(yk);
      end;
end;

Поиск в ширину:

procedure Pw(v:integer);
var Og:array[1..Maxn]of 0..Maxn;
    yk1,yk2:integer;
    j:integer;
begin
   fillchar(Og,sizeof(Og),0);yk2:=0;
   yk1:=1;Og[yk1]:=v;Nnew[v]:=false;
   while yk2 < yk1 do
      begin
         inc(yk2);v:=Og[yk2];
         write(v:2);
         for j:=1 to n do
            if (a[v,j] <> 0) and Nnew[j] then
               begin
                  inc(yk1);Og[yk1]:=j;Nnew[j]:=false;
               end;
      end;
end;

2. Каркасы (стягивающие деревья)

const Maxn=100;
var a:array[1..Maxn,1..Maxn]of byte;
    Nnew:array[1..Maxn]of boolean;
    Tree:array[1..2,1..Maxn]of integer;
    n,i,j:integer;
    yk:integer;

Построение стягивающего дерева поиском в глубину:

procedure Tree_Depth(v:integer);
var i:integer;
begin
   Nnew[v]:=false;
   for i:=1 to n do
      if (a[v,i] <> 0) and Nnew[i] then
         begin
            inc(yk);Tree[1,yk]:=v;Tree[2,yk]:=i;
            Tree_Depth(i);
         end;
end;

Построение стягивающего дерева поиском в ширину:

procedure Tree_Width(v:integer);
var Turn:array[1..Maxn]of integer;
    yr,yw,i:integer;
begin
   fillchar(Turn,sizeof(Turn),0);yr:=0;
   yw:=1;Turn[yw]:=v;Nnew[v]:=false;
   while yw <> yr do
      begin
         inc(yr);v:=Turn[yr];
         for i:=1 to n do
            if (a[i,j] <> 0) and Nnew[i] then
               begin
                  inc(yw);Turn[yw]:=i;Nnew[i]:=false;
                  inc(yk);Tree[1,yk]:=v;Tree[2,yk]:=i;
               end;
      end;
end;

Построение всех каркасов графа:

const Maxn=100;
var a:array[1..Maxn,1..Maxn]of byte;
    Nnew:array[1..Maxn]of boolean;
    Tree:array[1..2,1..Maxn]of integer;
    Turn:array[1..maxn]of integer;
    n,i,j:integer;
    numb:integer;
    down,up:integer;

..............

procedure solve(v,q:integer);
var j:integer;
begin
   if down >= up then exit;
   j:=q;
   while (j <= n) and (numb < n-1) do
       begin
          if (a[v,j] <> 0) and Nnew[j] then
             begin
                Nnew[j]:=false;
                inc(numb);
                Tree[1,numb]:=v;Tree[2,numb]:=j;
                Turn[up]:=j;inc(up);
                solve(v,j+1);
                dec(up);Nnew[j]:=true;dec(numb);
             end;
          inc(j);
       end;
   if numb = n-1 then
      begin
         writeln;
         for i:=1 to numb do
            write(Tree[1,i],' ',Tree[2,i],'  ');
         exit;
      end;
   if j = n+1 then
      begin
         inc(down);
         solve(Turn[down],1);
         dec(down);
      end;
end;

Построение минимального каркаса методом Краскала:
(Исправлено. Присоединенный архив перезалит)

Граф задан списком ребер с указанием их весов:

program minim_tree_kraskal;
const maxn=100;
var p:array[1..3,1..maxn*(maxn-1) div 2]of integer;
    Mark:array[1..maxn]of integer;
    k,i,t:integer;
    m,n:integer;{m - rebra;n - vershini }

procedure Change_Mark(l,m:integer);
var i,t:integer;
begin
   if m < l then
      begin
         t:=l;l:=m;m:=t;
      end;
   for i:=1 to n do
      if Mark[i]=m then Mark[i]:=l;
end;

begin
   readln(n,m);
   for i:=1 to m do
      read(p[1,i],p[2,i],p[3,i]);
   for i:=1 to m-1 do
      for t:=i+1 to m do
         if p[3,i] > p[3,t] then
            begin
               k:=p[1,i];p[1,i]:=p[1,t];p[1,t]:=k;
               k:=p[2,i];p[2,i]:=p[2,t];p[2,t]:=k;
               k:=p[3,i];p[3,i]:=p[3,t];p[3,t]:=k;
            end;
   for i:=1 to n do mark[i]:=i;
   k:=0;t:=m;
   while k < n-1 do
      begin
         i:=1;
         while (i <= t) and (Mark[p[1,i]] = Mark[p[2,i]]) and (p[1,i] <> 0) do inc(i);
         inc(k);

         if p[1, i] * p[2, i] <> 0 then begin { Добавлена проверка на ненулевые вершины }
            write(p[1,i],' ',p[2,i],'  ');
            change_Mark(Mark[p[1,i]],Mark[p[2,i]]);
         end;
      end;
end.

Построение минимального каркаса методом Прима:

procedure solve;
var sm,sp:set of 1..maxn;
    min,i,j,l,t:integer;
begin
   min:=maxint;
   sm:=[1..n];sp:=[];
   for i:=1 to n-1 do
      for j:=i+1 to n do
         if (a[i,j] < min) and (a[i,j] <> 0) then
            begin
               min:=a[i,j];
               l:=i;t:=j;
            end;
   sp:=[l,t];sm:=sm-[l,t];
   write(l,' ',t ,'  ');
   while sm <> [] do
      begin
         min:=maxint;
         l:=0;t:=0;
         for i:=1 to n do
            if not (i in sp) then
               for j:=1 to n do
                  if (j in sp) and (a[i,j] < min) and (a[i,j] <> 0) then
                     begin
                        min:=a[i,j];
                        l:=i;t:=j;
                     end;
         sp:=sp+[l];sm:=sm-[l];
         write(l,' ',t,'  ');
      end;
end;

Сообщение отредактировано: volvo - 13.01.2009 11:36

[Perfez]

Топологическая Сортировка Графа

Рассмотрим ациклический направленный граф содержащий N узлов (вершин). Топологической сортировкой узлов (также известной как RPO-нумерация или N-нумерация) ациклического графа называется алгоритм, присваивающий узлам графа номера от 1 до N таким образом, что все предшественники узла с номером M имеют номера меньше M. Граф , как обычно, задаётся смежным массивом. Алгоритм представляет собой простейшую модификацию алгоритма поиска в глубину, также указанной вверху (Смотри пост virt-а).

Внизу представлена реализация Топологической Сортировки:

const
 limit=100;
var
 a:array [1..limit,1..limit] of longint; {Сам граф, реализуемый в виде смежного массива}
 b,c,d:array [1..limit] of longint;
 i,l,u,v,n,m,x,y:longint;
Procedure Check; {Процедура проверяющая ацикличность графа}
 Begin
  If (x<>u) and (y<>v) and (u<>v) and (x<>v) and (y<>u) then Inc(l,2);
  If (u=v) and (x<>u) and (y<>u) then Inc(l);
  x:=u;
  y:=v;
 End;
Procedure DFS(u:longint); {Процедура слегка изменённого поиска в глубину}
 var
  j:longint;
 Begin
  b[u]:=1;
  For j:=1 to c[u] do
   If b[a[u,j]]=0 then DFS(a[u,j]);
  Inc(l);
  d[l]:=u;
 End;
Begin
 Repeat
  ReadLn(n,m); {Задаётся количество вершин и рёбер соответственно}
 Until m>n;
 For i:=1 to m do
  Begin
   Read(u,v); {Ввод рёбер}
   If i=1 then
    Begin
     If u<>v then Inc(l,2)
     else Inc(l);
     x:=u;
     y:=v;
    End
   else Check;
   Inc(c[u]);
   a[u,c[u]]:=v;
  End;
 If l<>n then {Проверка на цикличность графа}
  Begin
   WriteLn('В графе есть цикл!');
  End
 else
  Begin
   l:=0;
   For i:=1 to n do
    If b[i]=0 then DFS(i); {Рекурсия самой сортировки}
   For i:=n downto 1 do Write(d[i]:3); {Вывод вершин графа после сортировки}
  End;
End.

Сообщение отредактировано: Perfez - 21.07.2007 8:26