[densi2009]

Привет всем. Есть вопросы по поводу алгоритма Форда-Фалкерсона.
Имеется матрица смежности. Как дальше программировать этот алгоритм (прикрепленный файл) для нахождения максимального потока?

[Physicist]

Вас интересует конкретная реализация на delphi? Сам алгоритм не может вызвать затруднений, обычный перебор вариантов: по матрице смежности находятся все пути, затем по каждому ребру увеличивается поток на величину минимальной разницы между потоками рёбер в одном пути. Теперь как минимум одно ребро становится насыщенным, после чего - всё сначала: находятся все пути по ненасыщенным рёбрам.

Думаю, что удобнее всего решение через связанные списки. Путь можно представить как массив с размерностью матрицы смежности. Элементы массива - нули и целые числа, ниже диагонали только нули. Целое число, это номер в порядке обхода графа. Один путь - один массив. У переменной типа запись одно из полей - этот массив. Т.о. после первой итерации можно освободить память того элемента, где путь по насыщенным рёбрам.

Алгоритм составления пути по матрице смежности: цикл

Код:

for i:=1 to n do
...
for j:=i to n do
...

т.к. матрица смежности симметричная.
После нахождения первой единицы (для конкретных ij) остальная часть строки в текущей матрице смежности обнуляется. В массиве пути в этом месте ставим порядковый номер, равной переменной внешнего цикла. Соответственно для следующего прохода обнуляются соответствующие элементы матрицы смежности.

[densi2009]

Интересует реализация только на Delphi. Меня интересует какой алгоритм для нахождения всех путей для матрицы смежности.

Просто с графами раньше не работал.

[Physicist]

Путь из S в исток J, который находится в этом графе: просматриваем по рёбрам (ненасыщенным) вершины S соседей: есть ли среди них J. Если нет, то заносим всех (обнаруженных впервые) соседей в стек для посещения. После просмотра всех соседей отмечаем нашу вершину, как уже посещённую. Достаем первую непосещённую вершину из стека и идем в неё. И так далее. Причём те вершины, в которых однажды побывали — пропускаем (обнуляются соответствующие элементы матрицы смежности). Если встречается J - путь составлен.

Если не секрет, вам к какому сроку надо?

Тут завалялась коллекция (однако, сам не проверял) исходников на Pascal (Delphi) и С++ различных алгоритмов на графах:

[densi2009]

В среду должна быть готовая программа. В программе дана матрица смежности. Сначала надо найти все возможные пути (как я понял) , просто как это прописать в Delphi?

[Physicist]

Фрагмент кода на паскале:

Код:

const
  maxn = 250;                           { максимальное количество вершин }

const
  queue_size = maxn;                    { размер очереди }

type
  item = integer;                       { тип элемента очереди }

  queue = record                        { очередь на базе массива }
    a: array [0..queue_size] of item;
    head, tail: integer;                { голова и хвост }
  end;

{ инициализация очереди }
procedure init_queue(var q: queue);
begin
  q.head := 0;
  q.tail := 0;
end;

{ положить в очередь }
procedure push_to_queue(var q: queue; x: item);
begin
  with q do
  begin
    a[tail] := x;
    tail := (tail + 1) mod queue_size;
  end;
end;

{ взять из очереди }
function pop_from_queue(var q: queue): item;
begin
  with q do
  begin
    pop_from_queue := a[head];
    head := (head + 1) mod queue_size;
  end;
end;

{ проверить пуста ли очередь }
function is_queue_empty(const q: queue): boolean;
begin
  is_queue_empty := q.head = q.tail;
end;


var
  a: array [1..maxn, 1..maxn] of boolean;       { матрица смежности }
  q: queue;                                     { очередь }
  visited: array [1..maxn] of boolean;          { посещена ли вершина }
  n: longint;

procedure init;
var
  i, x, y, nn: longint;
begin
  fillchar(a, sizeof(a), false);                { инициализация данных }
  fillchar(visited, sizeof(visited), false);

  assign(input, 'graph.in');                    { чтение данных }
  reset(input);

  read(n);
  read(nn);

  for i := 1 to nn do
  begin
    read(x, y);
    a[x, y] := true;
    a[y, x] := true;                    { если неориентированный граф }
  end;
end;

{ печать матрицы смежности }
procedure print;
var
  i, j: integer;
begin
  writeln;
  writeln('number of vertex : ', n);
  writeln('adjacency matrix');
  for i := 1 to n do
  begin
    for j := 1 to n do
      write(ord(a[i, j]));
    writeln;
  end;
end;

{ поиск в ширину }
{ v - вершина исток }
procedure bfs(v: longint);
var
  i: integer;
begin
  init_queue(q);
  push_to_queue(q, v);                   { положим верину v в очередь }
  visited[v] := true;                    { вершина v посещена }

  while not is_queue_empty(q) do         { пока очередь не пуста }
  begin
    v := pop_from_queue(q);              { достаем из очереди вершину }
    for i := 1 to n do                   { перебираем все вершниы }
      if a[v, i] and not visited[i] then { если вершина смежная и }
      begin                              { непосещенная }
        visited[i] := true;              { вершина i - посещена }
        push_to_queue(q, i);             { положим вершину i в очередь }
      end;
    write(v, ' ');                       { обработка вершины }
  end;
end;

var
  i: longint;

begin
  init;

  writeln('breath-first search (order)');
  for i := 1 to n do                     { для всех непосещенных вершин }
    if not visited[i] then
      bfs(i);                            { вызовем поиск в ширину }

  print;
end.

Если не секрет, когда было выдано задание?

[densi2009]

Задание было выдано неделю назад.
Может у тебя есть этот же фрагмент кода на Delphi. В качестве исходной матрицы Stringgrid.

[densi2009]

вот нашел исходник программы для нахождения максимального потока.
Можно ли переделать эту прорамму так , чтобы при запуске программы пользователь вводил матрицу смежности( на диагонали все нули).