VPF::Тем кто рубит в DELPHI - Форум программистов

McMasloFF

Дата 15.6.2005, 23:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 15.6.2005

Репутация: нет
Всего: нет

Большое всем уважение!
Прошу помочь и дать дельный совет по курсачу.Сроки поджемают, времени в обрез,а дельного совета нет.
Тема курсача звучит, как "ПОИСК ВСЕХ ЦИКЛОВ В ГРАФЕ". У мя есть немного недоделанный поиск фундоментальных(т.е. простых) циклов реализован на DELPHI. Но мне нужно чтобы матрица вводилась,как с клавы, как из файла, так забивалась Random'ом.
Тут типа надо реализовать такуй тему, перебераем все возможные сочетания фундаментальных циклов, имеющих хотя бы одно общее ребро.Четное количество общих ребер дает пустое ребро, а нечетное - сохраняет это ребро в результате операции.В полученном результате следует разделить так называемые “псевдоциклы”, состоящие из нескольких простых циклов соединенных общей вершиной и исключить повторяющиеся циклы.
Если, кто понял то прошу помочь.Заранее благодарен.
З.Ы.В долгу не останусь...

Код


unit del;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Grids;  // подключение модулей

type
  TForm2 = class(TForm)
    Button1: TButton;
    ListBox1: TListBox;
    StringGrid1: TStringGrid;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
  const n=6;     // константа показывающая количество вершин в графе.

var //объявление глобальных переменных.
  Form2: TForm2;
  d,num,l:integer;
  stek,wgn:array [1..n] of integer;
  m:array [1..n,1..n] of integer;


 implementation


 procedure cikl(v:integer); //процедура осуществляющая поиск циклов
   var str:String;  //строка в которой хранится цикл перед выводом.
   var u,i,j,k,t,h,g: Integer;//объявление числовых переменных
   var a: boolean;
   var f:array [1..1000,1..n] of integer; //массив в котором хранятся все циклы
begin
   a:=true;
   d:=d+1;                 //увеличиваем номер элемента масива
   stek[d]:=v;             //запоминаем вершину в массив
   num:=num+1;
    wgn[v]:=num;          //ставим метки на пройденные вершины
    for j:=1 to n do     //осуществляем поиск не пройденных вершин инцидентных v
     begin
       if m[v,j]=1 then //если в матрице смежности стоит 1=> вершина j достижима из v.
       begin
       u:=j;// записываем номер этой вершины
       if (u<>0) then
        if wgn[u]=0  then
         cikl(u)    //если вершина не пройдена ,выполняем процедуру cikl для неё
          else if (u<>stek[d-1])and (wgn[u]=1)  then //если вершина пройдена и не равна предыдущей
                                                     // чтобы избежать циклов состоящих из одного ребра
                                                     // то цикл замкнут
          begin
           inc(l);// при каждом проходе увеличиваем l
           str:=''; // очищаем строку.
           for i:=l to 1000 do
            begin
            for k:=1 to n do
            f[i,k]:= stek[k];//заносим номера вершин цикла в массив
            break;
          end;
            for i:=1 to l-1 do  // проверка цикла на повтор
            begin
            h:=0;     //обнуление для использования в качестве счётчика
            for k:=1 to d do
            for t:=1 to d do
            if stek[t]=f[i,k] then inc(h);
            if h=d then
            begin
            a:= false; // если такой цикл уже найден , то мы его не выводим
            break;
            end;
            end;

            if a then // если такой цикл ещё не найден , производим вывод
            for i:=1 to d do
            str:=str+IntToStr(stek[i]);
          if str<>'' then Form2.ListBox1.Items.Add(str);//выводим цикл
          end;
        end;
     end;
   d:=d-1;// убираем добавленую вершину
end;

{$R *.dfm}

procedure TForm2.Button1Click(Sender: TObject);
var i, j : Integer;
begin
 randomize(); // подключаем генератор случайных чисел
 Form2.ListBox1.Clear; //очищаем окно вывода при каждом новом графе
 for i:=1 to n do
   for j:=i+1 to n do
   begin
     m[i,j]:=random(2);
     if m[i,j]>=1 then m[i,j]:=1 else m[i,j]:=0;//производим генерацию матрици смежности графа
     m[j,i]:=m[i,j];
     Form2.StringGrid1.Cells[j-1,i-1]:=IntToStr(m[i,j]);
     Form2.StringGrid1.Cells[i-1,j-1]:=IntToStr(m[j,i]);
                                      //т.к граф не ориентирован ,то матрица смежности симметрична
   end;
    for i:=1 to n do
    begin
    m[i,i]:=0;     // убираем  "1" с главной диагонали
    Form2.StringGrid1.Cells[i-1,i-1]:=IntToStr(m[i,i]);
    end;
  l:=0;
  stek[1]:=0;
 for j:=1 to n do
 begin
     for i:=1 to n do
     wgn[i]:=0; // обнуляем  метки вершин при каждом новом поиске
     d:=0;
     num:=0; // инициализируем первоначальное значение
    cikl(j); // подключаем процедуру для вершины j
   end;
end;

end.

Это сообщение отредактировал(а) McMasloFF - 16.6.2005, 22:02

Alex

Дата 15.6.2005, 23:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 4147
Регистрация: 25.3.2002
Где: Москва

Репутация: нет
Всего: 162

Модератор: Название темы должно отражать ее суть!

--------------------

Написать можно все - главное четко представлять, что ты хочешь получить в конце.

Pakshin A. S.

Дата 16.6.2005, 08:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: 5
Всего: 61

М	Действительно! В следующий раз сразу в мусорку тема пойдет!!!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »