Пошук у ширину

Раніше ми вже розглядали різноманітні пошукові алгоритми: пошук заданої інформації в одновимірному масиві, в мережі, у рядку.
Під час дослідження задач, що пов'язані з обробкою інформації, яку можна представити у вигляді графів, також постає питання пошуку. У першу чергу - це пошук шляху від однієї заданої вершини до іншої.

Існує два підходи до здійснення такого пошуку. Розглянемо перший із них - пошук у ширину.

Як відомо, одним із найпоширеніших способів представлення графа є матриця суміжності. Саме на перегляді цієї матриці і базується метод пошуку в ширину.

Для зручнішого пояснення цього методу розглянемо конкретний приклад графа, зображеного на малюнку 21, а та відповідній йому матриці суміжності (мал. 21, б).  Нехай також відомо, що необхідно визначити існування у даному графі шляху від вершини 1 до вершини 7.

Почнемо пошук шуканої вершини 7 із заданої вершини 1.

Дія	Вміст черги	Вже відвідувані вершини
Запишемо до черги номер вершини 1	1
Читаємо з черги номер вершини 1. Помічаємо вершину 1 як відвідувану		1
Перевіряємо у матриці суміжності суміжні з вершиною 1 вершини. Це вершини 2, 3, 4. Шуканої серед них немає. Ці вершини ще не відвідувані.		1
Поміщаємо до черги вершини 2, 3, 4	2,3,4	1
Читаємо з черги номер вершини 2. Помічаємо вершину 2 як відвідувану	3,4	1,2
Перевіряємо у матриці суміжності суміжні з вершиною 2 вершини. Це вершини 1,3,5,6. Шуканої серед них немає. Вершини 3,5,6 ще не відвідувані	3,4	1,2
Поміщаємо до черги вершини 3,5,6	3,4,3,5,6	1,2
Читаємо з черги номер вершини 3. Помічаємо вершину 3 як відвідувану	4,3,5,6	1,2,3
Перевіряємо у матриці суміжності суміжні з вершиною 3 вершини. Це вершини 1,2,4,5. Шуканої серед них немає. Вершини 4,5 ще не відвідувані	4,3,5,6	1,2,3
Поміщаємо до черги вершини 4,5	4,3,5,6, 4,5	1,2,3
Читаємо з черги номер вершини 4. Помічаємо вершину 4 як відвідувану	3,5,6, 4,5	1,2,3,4
Перевіряємо у матриці суміжності суміжні з вершиною 4 вершини. Це вершини 1,3. Шуканої серед них немає. Ці вершини вже відвідувані	3,5,6, 4,5	1,2,3,4
Читаємо з черги номер вершини 3. Помічаємо вершину 3 як відвідувану, хоч вона вже й так відмічена як відвідувана	5,6, 4,5	1,2,3,4
Перевіряємо у матриці суміжності суміжні з вершиною 3 вершини. Це вершини 1,2,4,5. Шуканої серед них немає.  Ці вершини вже відвідувані	5,6, 4,5	1,2,3,4
Читаємо з черги номер вершини 5. Помічаємо вершину 5 як відвідувану	6, 4,5	1,2,3,4,5
Перевіряємо у матриці суміжності суміжні з вершиною 5 вершини. Це вершини 2,3,7. Серед них є шукана.	6, 4,5	1,2,3,4,5
Виходимо з циклу. Виводимо повідомлення, що шлях знайдено

 Var

    queue:array[0..100] of integer;

    tail,head:integer;

procedure Put(x:integer);

begin

    head:=head+1;

    queue[head]:=x;

end;

function Get(var x:integer):boolean;

begin

    if tail>head then

        Get:=false //Черга порожня

    else begin

      Get:=true;  //Черга не порожня

      x:=queue[tail];

      tail:=tail+1;

    end;

end;

procedure TForm1.Button1Click(Sender: TObject);

const Nmax = 100;

var  v,r,a,b,x,i,j,p,k,n : Integer;

     matr:array[1..Nmax,1..Nmax] of Integer;

     s:string;

     vp:set of 1..Nmax;

     NoFound:boolean;

begin  

        n:=0;

        //Заповнюємо матрицю суміжності нулями

        For i := 1 To Nmax do

            For j := 1 To Nmax do

                matr[i,j]:=0;

        //Читаємо дані з Memo1 та заповнюємо матрицю суміжності

        For i := 0 To Memo1.Lines.Count - 1 do begin

            s := Memo1.Lines[i];

            s := Trim(s);

            while pos('  ',s)<>0 do delete(s,pos('  ',s),1);

            If (s <> '') and (pos(' ',s)<>0) Then begin

                x := pos(' ',s);

                a := StrToInt(copy(s,1,x-1));

                b := StrToInt(copy(s,x+1,Length(s)-x));

                matr[a, b] := 1;

                matr[b, a] := 1;

                If a > n Then n := a;

                If b > n Then n := b;

            end

        end;

        //Рахуємо кількість ребер

        r := 0;

        For i := 1 To n do begin

            For j := 1 To n do begin

                If matr[i, j] = 1 Then r := r + 1;

            end;

        end;

        r := r div 2;

        p:=StrToInt(Edit1.Text);

        k:=StrToInt(Edit2.Text);

        //'=================================================================='

        //                      Початок пошуку

        //'=================================================================='

        NoFound:=true;

        vp:=[];

        tail:=0;

        head:=-1;

        //Поміщаємо початкову вершину в чергу

        Put(p);

        //Запускаємо цикл поки черга не порожня та не знайдено кінцеву вершину

        While Get(v) And NoFound do begin

            //Командою  GetQueue(v) ми прочитали з черги до змінної v номер вершини

            //Після чого відмічаємо цю вершину як пройдену

            vp:=vp+[v];

            //Переглядаємо у матриці суміжності всі вершини, суміжні з нею

            For i := 1 To n do begin

                If matr[v, i] <> 0 Then begin

                    //Якщо знайдено суміжну вершину, то перевіряємо, чи не є вона шуканою

                    //і якщо це так, то змінній NoFound присвоюємо значення False

                    If i = k Then NoFound := False ;

                    //Якщо ця вершина не відвідувана, то ставимо її в чергу

                    If not (i in vp) Then Put(i);

                End;

            End;

        End;

        //Виводимо результат пошуку

        If NoFound Then

            Label4.Caption := 'Результат: шлях не знайдено'

        Else

            Label4.Caption := 'Результат: шлях знайдено'

end;

Даний алгоритм дозволяє перевірити існування шляху, а не виводить його.