Главная Поділітся з нами... - Форум Регистрация Вход
[ Скачать фильмы бесплатно · Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Сторінка 1 з 1
  • 1
Модератор форуму: DRON  
Форум » Навчання!!! » Програмування » Поділітся з нами... (Алгоритми.)
Поділітся з нами...
VictorisДата: Неділя, 10.02.2008, 00:11 | Повідомлення # 1
$Victoris$
Група: Пользователи
Повідомлень: 423
Репутація: 15
Статус: Offline
Поділіться з нами алгоритмами.

Z342770612618
R259915377912
E855291308018
U293132702812
 
SlayerДата: Неділя, 10.02.2008, 00:41 | Повідомлення # 2
Заговори, щоб я тебе побачив
Група: Администраторы
Повідомлень: 35561
Репутація: 4
Статус: Offline
Алгоритм пошуку у ширину.
Пошук у ширину - один з базових алгоритмів теорії графів. Він являється основою для багатьох інших алгоритмів. Нехай задано граф і зафіксована початкова вершина s. Алгоритм пошуку в ширину перечислює усі досяжні з s (якщо іти по ребрам) вершини у порядку зростання відстані від s. У процесі пошуку із графа виділяється частина, яка зветься деревом пошуку в ширину з коренем у s. Вона містить всі досяжні з s вершини (і лише їх). Для наочності вважатимемо, що в процесі роботи алгоритму вершини графа можуть бути білими, сірими і чорними. Спочатку вони всі білі, а в ході роботи алгоритму біла вершина може стати сіру, сіра - чорною, але не навпаки. Зустрівши нову вершину, алгоритм пошуку фарбує її, так що сірі і чорні вершини - вже виявлені вершини. Спочатку дерево пошуку в ширину складається тільки з початкової вершини s. Як тільки алгоритм знаходить нову вершину v, суміжну з раніше знайденою вершиной u, вершина v разом з ребром (u,v) додається до дерева пошуку і стає нащадком u. Кожна вершина виявляється тільки один раз, так що двох батьків у вершини бути не може. Оцінюючи складність роботи цього алгоритму помічаємо, що вершини тільки темніють, тобто кожна вершина обробляється тільки один раз, тобто обчислювальна складність алгоритму O(V+E).
Реалізація на мові Паскаль:
Code

var
   Q:array[1..100] of byte;   {Черга}
   left,right:byte;
procedure Enqueue(x:word); {процедура додавання в чергу вершини}
  begin
    Q[right]:=x;
    if right=100 then right:=1 else inc(right);
  end;
procedure Dequeue;              {процедура видалення з черги вершини}
  begin
    if left=100 then left:=1 else inc(left);
  end;
var
   G:array[1..100,1..100] of word;  {граф}
   i,j,k,h:word;
   d:array[1..100] of word;             {масив відстаней}
   p:array[1..100] of word;             {масив нащадків}
   color:array[1..100] of byte;         {масив кольорів}
   n:word;
   fin:text;
   beg:word;                    {початкова вершина}
begin
   k:=0;
  {зчитування графа з файлу, ім'я котрого - перший параметр командної стрічки}  
   assign(fin,paramstr(1)); reset(fin);
   read(fin,n); readln(fin,beg);
   while not EOF(fin) do
     begin
       read(fin,i); readln(fin,j);
       g[i,j]:=1; g[j,i]:=1;
     end;
   close(fin);
  {кінець зчитування з файла}
  {ініціалізація масивів}
   for i:=1 to n do
     begin
       color[i]:=0;
       d[i]:=65535;
       p[i]:=0;
     end;
  {кінець ініціалізації масивів}
  color[beg]:=1;
  d[beg]:=0;
  p[beg]:=0;
  left:=1;
  right:=1;
  Enqueue(beg);             {Додавання першої вершини в чергу}
  while left<>right do      {Поки черга не порожня}
    begin
      k:=Q[left];
      for i:=1 to n do        {для всіх вершин...}
        if g[k,i]=1 then       {...суміжних з k...}
        begin
          if color[i] = 0 then {...якщо ми її ще но обробляли...}
            begin
              color[i]:=1;       {...зробити колір сірим...}
              d[i]:=d[k]+1;    {...вказати відстань...}
              p[i]:=k;             {...вказати нащадка...}
              EnQueue(i);      {...додати в чергу}
            end;
        end;
      Dequeue;                {видалити з черги}
      color[k]:=2;             {зробити колір чорним: вершина повністю оброблена}
    end;
   
  {вивід на екран відстаней від s до всіх вершин, які можна досягнути з неї}
  for i:=1 to n do
    write(d[i],' ');
    writeln;
end.


♥♥♥ 1000001 1001100 1001100 100000 1001001 100000 1001100 1001111 1010110 1000101 100000 1001001 1010011 100000 1000001 1001100 1001100 100000 1001001 100000 1001000 1000001 1010100 1000101 100001 100001 100001 ♥♥♥
 
VictorisДата: Неділя, 10.02.2008, 01:17 | Повідомлення # 3
$Victoris$
Група: Пользователи
Повідомлень: 423
Репутація: 15
Статус: Offline
http://algolist.ru - Тут ви знайдете багато алгоритмів у тому й числі нові.

Z342770612618
R259915377912
E855291308018
U293132702812


Повідомлення відредагував Victoris - Вівторок, 12.02.2008, 00:54
 
Форум » Навчання!!! » Програмування » Поділітся з нами... (Алгоритми.)
  • Сторінка 1 з 1
  • 1
Пошук:


Старокостянтинівська гімназія © 2018
Безкоштовний конструктор сайтів - uCoz