Реализация процедуры поиска в ширину в графах - Turbo Pascal

Узнай цену своей работы

Формулировка задачи:

помогите пожалуйста написать программу на тему:реализация процедуры поиска в ширину в графах

Решение задачи: «Реализация процедуры поиска в ширину в графах»

textual
Листинг программы
procedure BFS(A : Matrix; N, V : integer); //обход в ширину (V - корневая вершина)
var i, ps, pe : integer;
visited : array [1..MaxN] of boolean; //массив посещённости вершин
q : array [1..MaxN] of integer; //"очередь" вершин
begin //в качестве списка очередных вершин будем использовать структуру "очередь"
    ps := 1; //начало очереди
    pe := 1; //конец очереди
    q[pe] := v; //в очередь помещается исходная вершина. На каждом шаге в очередь будем заносить всех преемников данной вершины (назовём их 1-го уровня, т.е. до которых можно дойти напрямую). Затем просматриваем в очереди занесённые ранее вершины 1-го уровня и добавляем в конец очереди вершины 2-го уровня и так далее до опустошения очереди.
    visited[v] := TRUE; //вершина V посещена
    while ps <= pe do //пока очередь не пуста
    begin
        for i := 1 to n do if (A[v, i] <> 0) and (not visited[i]) then //перебираем все связные с V вершины
        begin
            inc(pe); //и добавляем в очередь
            q[pe] := i; 
            visited[i] := true; //отмечаем вершину I пройденной
        end;
        inc(ps); //переходим к следующей вершине в очереди
        v := q[ps]; //и делаем её корневой
    end;
end;

Объяснение кода листинга программы

Код реализует процедуру поиска в ширину (BFS) для графа, представленного в виде матрицы. В процедуре используются следующие переменные:

  • A: матрица графа, где A[i, j] указывает, что между вершинами i и j есть ребро.
  • N: количество вершин в графе.
  • V: индекс корневой вершины.
  • visited: массив, где visited[i] = TRUE, если вершина i посещена, и FALSE в противном случае.
  • q: массив, где q[i] - это индекс вершины, которая будет следующей для обхода. Процесс работы процедуры следующий:
    1. Инициализируются начальная и конечная позиции очереди q и visited[].
    2. Вершина V помещается в очередь q.
    3. Пока очередь q не пуста, происходит следующее:
      • Перебираются все вершины i, связанные с V.
      • Если i не посещено и A[V, i] != 0, то:
      • Вершина i добавляется в очередь q.
      • Устанавливается значение visited[i] = TRUE.
      • Значение v обновляется на значение q[ps].
    4. Процесс повторяется до тех пор, пока очередь q не опустеет. Таким образом, процедура BFS последовательно обходит все вершины графа, начиная с корневой, и помечает их как посещенные.

Оцени полезность:

15   голосов , оценка 4.067 из 5
Похожие ответы