Реализация процедуры поиска в ширину в графах - 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] - это индекс вершины, которая будет следующей для обхода.
Процесс работы процедуры следующий:
- Инициализируются начальная и конечная позиции очереди q и visited[].
- Вершина V помещается в очередь q.
- Пока очередь q не пуста, происходит следующее:
- Перебираются все вершины i, связанные с V.
- Если i не посещено и A[V, i] != 0, то:
- Вершина i добавляется в очередь q.
- Устанавливается значение visited[i] = TRUE.
- Значение v обновляется на значение q[ps].
- Процесс повторяется до тех пор, пока очередь q не опустеет. Таким образом, процедура BFS последовательно обходит все вершины графа, начиная с корневой, и помечает их как посещенные.