Поиск в ширину и глубину

tux 2012.09.30 Графы https://tux.org.ua/?p=757 4558 0

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

Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.

Поиск в ширину выполняется в следующем порядке:

Началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы.

Procedure BFS(v: integer);
Var q: array[1..n] of integer;
    start, finish, i, j: integer;
Begin
  fillchar(q, sizeof(q), 0);
  start := 0; finish := 0;
  inc(finish);
  q[finish] := v;
  marked[v] := true;
  while(start < finish) do
  begin
    inc(start);
    v := q[start];
    {WriteLn(v);}
    For j := 1 to n do
      if (a[v, j] <> 0) and (not marked[j]) then
      begin
        inc(finish);
        q[finish] := j;
        marked[j] := true;
      end;
  end;
End;

Procedure BFS(v: integer);

Var q: array[1..n] of integer;

start, finish, i, j: integer;

Begin

fillchar(q, sizeof(q), 0);

start := 0; finish := 0;

inc(finish);

q[finish] := v;

marked[v] := true;

while(start < finish) do

begin

inc(start);

v := q[start];

{WriteLn(v);}

For j := 1 to n do

if (a[v, j] <> 0) and (not marked[j]) then

begin

inc(finish);

q[finish] := j;

marked[j] := true;

end;

End;

Поиск в глубину

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

Поиск в глубину

Поиск в глубину (Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

Из множества всех белых вершин выберем любую вершину, обозначим её v1.
Выполняем для неё процедуру DFS(v1).
Перекрашиваем её в чёрный цвет.
Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

const
  MAX_N = 10;
var
  graph:   array [1..MAX_N, 1..MAX_N] of boolean;
  visited: array [1..MAX_N] of boolean;

procedure dfs(v: integer);
var
  i: integer;
begin
  visited[v] := true;

  for i := 1 to MAX_N do
    if graph[v, i] and not visited[i] then
      dfs(i);
end;

const

MAX_N = 10;

var

graph: array [1..MAX_N, 1..MAX_N] of boolean;

visited: array [1..MAX_N] of boolean;

procedure dfs(v: integer);

var

i: integer;

begin

visited[v] := true;

for i := 1 to MAX_N do

if graph[v, i] and not visited[i] then

dfs(i);

end;

графы, поиск в глубину, поиск в ширину, программирование

Алгоритм Дейкстры

Эйлеров и Гамильтонов графы

#:

Поиск в ширину и глубину

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

Поиск в глубину

Похожие материалы:

Оставить комментарий