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

Поиск в ширину или BFS (breadth-first search, поиск "сначала в ширину") - это метод обхода графа, по которому после стартовой вершины сначала отмечаются все вершины смежные с ней, то есть все достижимые за один шаг, а потом все достижимые за два (смежные с предыдущими и не смежные со стартовой), а потом за три шага и т.д. Это напоминает распространение волны, по этому поиск в ширину называет методом волны.

Пример поиска в ширину

Поиск в ширину (обход по уровням) - один из алгоритмов обхода графа. Метод лежит в основе некоторых других алгоритмов близкой тематики. Поиск в ширину подразумевает поуровневое исследование графа: вначале посещается корень - произвольно выбранный узел, затем - все потомки данного узла, после этого посещаются потомки потомков и т.д. Вершины просматриваются в порядке возрастания их расстояния от корня.

Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника .

Рассмотрим все рёбра , выходящие из узла . Если очередной узел является целевым узлом, то поиск завершается; в противном случае узел добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла , из очереди извлекается следующий узел , и процесс повторяется.

Пусть задан граф G= (V, E) и корень s, с которого начинается обход. После посещения узла s, следующими за ним будут посещены смежные с s узлы (множество смежных с s узлов обозначим как q; очевидно, что q?V, то есть q - некоторое подмножество V). Далее, эта процедура повториться для вершин смежных с вершинами из множества q, за исключением вершины s, т.к. она уже была посещена. Так, продолжая обходить уровень за уровнем, алгоритм обойдет все доступные из s вершины множества V. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения наличествующего условия.

Рассматривая следующий пример, будем считать, что в процессе работы алгоритма каждая из вершин графа может быть окрашена в один из трех цветов: черный, белый или серый. Изначально все вершины белые. В процессе обхода каждая из вершин, по мере обнаружения, окрашивается сначала в серый, а затем в черный цвет. Определенный момент обхода описывает следующие условие: если вершина черная, то все ее потомки окрашены в серый или черный цвет.

Имеем смешанный граф (см. рис.) с |V| = 4 и |E| = 5. Выполним обход его вершин, используя алгоритм поиска в ширину. В качестве стартовой вершины возьмем узел 3. Сначала он помечается серым как обнаруженный, а затем черным, поскольку обнаружены смежные с ним узлы (1 и 4), которые, в свою очередь, в указанном порядке помечаются серым. Следующим в черный окрашивается узел 1, и находятся его соседи - узел 2, который становится серым. И, наконец, узлы 4 и 2, в данном порядке, просматриваются, обход в ширину завершается.

Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах. Дать понять это был призван смешанный граф, используемый в примере. Стоит отметить, в неориентированном связном графе данный метод обойдет все имеющиеся узлы, а в смешанном или орграфе это необязательно произойдет. К тому же, до сих пор рассматривался обход всех вершин, но вполне вероятно, достаточным окажется, например просмотр определенного их количества, либо нахождение конкретной вершины. В таком случае придется немного приспособить алгоритм, а не изменять его полностью или вовсе отказаться от использования такового.

Теперь перейдем к более формальному описанию алгоритма поиска в ширину. Основными объектами - тремя структурами данных, задействованными в программе, будут:

· матрица смежности графа GM;

· очередь queue;

· массив посещенных вершин visited.

Две первые структуры имеют целочисленный тип данных, последняя - логический. Посещенные вершины, заносятся в массив visited, что предотвратит зацикливание, а очередь queue будет хранить задействованные узлы. Напомним, что структура данных "очередь" работает по принципу "первый пришел - первый вышел". Рассмотрим разбитый на этапы процесс обхода графа:

1. массив visited обнуляется, т.е. ни одна вершина графа еще не была посещена;

2. в качестве стартовой, выбирается некоторая вершина s и помещается в очередь (в массив queue);

3. вершина s исследуется (помечается как посещенная), и все смежные с ней вершины помещаются в конец очереди, а сама она удаляется;

4. если на данном этапе очередь оказывается пустой, то алгоритм прекращает свою работу; иначе посещается вершина, стоящая в начале очереди, помечается как посещенная, и все ее потомки заносятся в конец очереди;

5. пункт 4 выполняется пока это возможно.

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

1.1 Неформальное описание

1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.

2. Извлечь из начала очереди узел и пометить его как развёрнутый.

o Если узел является целевым узлом, то завершить поиск с результатом "успех".

o В противном случае, в конец очереди добавляются все преемники узла , которые ещё не развёрнуты и не находятся в очереди.

3. Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом "неудача".

4. Вернуться к п.2.

Рисунок 1.1 - Белый - вершина, которая еще не обнаружена. Серый - вершина, уже обнаруженная и добавленная в очередь. Черный - вершина, извлечённая из очереди

1.2 Формальное описание

PHP

$graph = array ('A' => array ('B','C','D','Z'), 'B' => array ('A','E'), 'C' => array ('A','F','G'), 'D' => array ('A','I'), 'E' => array ('B','H'), 'F' => array ('C','J'), 'G' => array ('C'), 'H' => array ('E','Z'), 'I' => array ('D'), 'J' => array ('J'), 'Z' => array ('A','H'));

function bfs ($graph, $startNode = 'A')

{

$visited = array ();

$queue = array ();

$queue [] = $graph [$startNode];

$visited [$startNode] = true;

while (count ($queue) > 0)

{

$currentNodeAdj = array_pop ($queue);

foreach ($currentNodeAdj as $vertex)

{

if (! array_key_exists ($vertex,$visited))

{

array_unshift ($queue, $graph [$vertex]);

}

$visited [$vertex] = true;

}

}

}

С++

#include <vector>

#include <stdio. h>

#include <queue>

#include <iostream>

using namespace std;

int main ()

{

vector < vector<int> > g; // граф

const int n = 4; // число вершин

int s = 0; // стартовая вершина (вершины везде нумеруются с нуля)

// чтение графа

int Adj [n] [n] = {

{0,1,0,0},

{1,0,1,0},

{0,1,0,1},

{0,0,1,0} };

for (int i = 0; i < n; i++)

{

g. push_back (vector<int> ());

for (int j = 0; j < n; j++)

{

g [i]. push_back (0);

g [i] [j] =Adj [i] [j];

}

}

queue<int> q;

q. push (s);

vector<bool> used (n);

vector<int> d (n), p (n);

used [s] = true;

p [s] = - 1;

while (! q. empty ())

{

int v = q. front ();

for (size_t i = 0; i < g [v]. size (); ++i)

{

if (! used [i] && g [v] [i])

{

used [i] = true;

q. push (i);

d [i] = d [v] + 1; // расстояние;

p [i] = v; // parent;

}

}

q. pop ();

}

for (int i = 0; i < n; i++)

cout << d [i] << " ";

cout << endl;

for (int i = 0; i < n; i++)

cout << p [i] << " ";

cout << endl;

system ("pause");

return 0;

}

Pascal

const

l = 1000;

var i,j,n, consp,cur,st,fin: integer; way,q: array [1. l] of integer;

was: array [1. l] of integer;

m: array [1.100] of array [1.100] of integer;

pred: array [1. l] of integer;

b,e: integer;

procedure add (var i: integer);

begin

if i < l then i: =i+1 else i: =1;

end;

begin

For i: =1 to l do

begin

was [i]: =0;

q [i]: =0;

end;

readln (n);

For i: =1 to n do

For j: =1 to n do

read (m [i,j]);

read (st,fin);

b: =1;

e: =b+1;

q [b]: =st;

while (cur<>fin) do

begin

cur: =q [b];

add (b);

was [cur]: =1;

if (b<>e) and (cur <> fin) then

begin

For i: =1 to n do

if ( (m [i,cur] =1) and (was [i] =0)) then

begin

add (e);

q [e]: =i;

pred [i]: =cur;

end;

end;

end;

i: =1;

way [1]: =fin;

while (cur <> st) do

begin

way [i]: =cur;

inc (i);

cur: =pred [cur];

end;

For i: =1 to i do

write (way [i]);

readln;

readln;

end.

Код Java (TM) 2 Platform Standard Edition 5.0

public class WideAlgo {

public static void main (String [] args) {

Graph theGraph = new Graph ();

theGraph. addVertex ('A'); // 0

theGraph. addVertex ('B'); // 1

theGraph. addVertex ('C'); // 2

theGraph. addVertex ('D'); // 3

theGraph. addVertex ('E'); // 4

theGraph. addEdge (0, 1); // AB

theGraph. addEdge (1,2); // BC

theGraph. addEdge (0,3); // AD

theGraph. addEdge (3,4); // DE

System. out. print ("Посещения: ");

theGraph. bfs ();

System. out. println ();

}

static class Queue {

private final int SIZE = 20;

private int [] queArray;

private int front;

private int rear;

public Queue () {

queArray = new int [SIZE];

front = 0;

rear = - 1;

}

public void insert (int j) // put item at rear of queue

{

if (rear == SIZE - 1)

rear = - 1;

queArray [++rear] = j;

}

public int remove () // take item from front of queue

{

int temp = queArray [front++];

if (front == SIZE)

front = 0;

return temp;

}

public boolean isEmpty () // true if queue is empty

{

return (rear + 1 == front || (front + SIZE - 1 == rear));

}

}

static class Vertex {

public char label; // label

public boolean wasVisited;

public Vertex (char l) {

label = l;

wasVisited = false;

}

}

static class Graph {

private final int MAX_VERTS = 20;

private Vertex vertexList []; // list of vertices

private int adjMat [] []; // adjacency matrix

private int nVerts; // current number of vertices

private Queue theQueue;

public Graph () {

vertexList = new Vertex [MAX_VERTS];

// adjacency matrix

adjMat = new int [MAX_VERTS] [MAX_VERTS];

nVerts = 0;

for (int j = 0; j < MAX_VERTS; j++)

// set adjacency

for (int k = 0; k < MAX_VERTS; k++)

// matrix to 0

adjMat [j] [k] = 0;

theQueue = new Queue ();

}

public void addVertex (char l) {

vertexList [nVerts++] = new Vertex (l);

}

public void addEdge (int start, int end) {

adjMat [start] [end] = 1;

adjMat [end] [start] = 1;

}

public void displayVertex (int v) {

System. out. print (vertexList [v]. label);

}

// breadth-first search

public void bfs ()

{ // begin at vertex 0

vertexList [0]. wasVisited = true; // mark it

displayVertex (0); // display it

theQueue. insert (0); // insert at tail

int v2;

while (! theQueue. isEmpty ()) // until queue empty,

{

int v1 = theQueue. remove (); // remove vertex at head

// until it has no unvisited neighbors

while ( (v2 = getAdjUnvisitedVertex (v1))! = - 1) { // get one,

vertexList [v2]. wasVisited = true; // mark it

displayVertex (v2); // display it

theQueue. insert (v2); // insert it

}

}

// queue is empty, so we're done

for (int j = 0; j < nVerts; j++)

// reset flags

vertexList [j]. wasVisited = false;

}

// returns an unvisited vertex adj to v

public int getAdjUnvisitedVertex (int v) {

for (int j = 0; j < nVerts; j++)

if (adjMat [v] [j] == 1 && vertexList [j]. wasVisited == false)

return j;

return - 1;

}

}

}

Perl

while (! @queue) # пока очередь не пуста

{

for my $key (keys %graph) # бежим по ключам (вершина - ключ)

{

push @queue, $key; # добавляем 1-ую вершину (стартовую) и так далее (2,3,4)

$state{$key} = "SERIY"; # метим её, как просмотренную

for (0. scalar @{$graph{$key}} - 1) # бежим по смежным вершинам

{

$p = shift @queue; # извлекаем 1-ую вершину

push @queue, $graph{$key} [$_]; # добавляем смежные вершины

if ($state{$graph{$key} [$_] } eq "SERIY") # если мы уже просматривали вершину, то существует цикл

{

print "cicle"

}

else

{

$state{$graph{$key} [$_] } = "SERIY"; # иначе метим вершину

}

}

}

}

Java

package problemresolver. algorithm. base;

import problemresolver. world. Path;

public interface TreeSearchContainer

{

void push (Path path);

Path pop ();

Path peek ();

boolean isEmpty ();

}

package problemresolver. algorithm. base;

import edu. uci. ics. jung. graph. util. Pair;

import problemresolver. algorithm. *;

import problemresolver. algorithm. model. *;

import problemresolver. algorithm.runtime. *;

import problemresolver. world. *;

import java. util. ArrayList;

import java. util. Collection;

public abstract class TreeSearch

extends Algorithm

{

private TreeSearchContainer fringe;

@Override

protected void safeRun (AlgorithmModel model)

throws AlgorithmException, AlgorithmRuntimeException

{

SingleAgentAlgorithmModel saModel =

AlgorithmModelRuntimeUtils. castToSingleAgentAlgorithmModel (model);

AlgorithmModelRuntimeUtils. checkSingleAgentAlgorithmModel (saModel);

WorldVertex agent = saModel. getAgentLocation ();

agent. setMark (WorldElement. MarkType. Visited);

fringe = createContainer ();

fringe. push (new Path (agent));

setRuned (true);

}

protected abstract TreeSearchContainer createContainer ();

@Override

protected void safeDoStep ()

throws AlgorithmException, AlgorithmRuntimeException

{

if (fringe. isEmpty ())

{

finishFail ();

return;

}

Path path = fringe. pop ();

Collection<Path> successors = expand (path);

for (Path successor: successors)

{

WorldVertex successorTail = successor. tail ();

Unit successorResident = successorTail. getResident ();

if (successorResident! = null &&

successorResident. getType () == Unit. Type. Goal)

{

finishSuccess ();

successor. mark (WorldElement. MarkType. Step);

}

else

{

successorTail. setMark (WorldElement. MarkType. Visited);

if (successorResident == null ||

successorResident. getType ()! = Unit. Type. Obstacle)

{

fringe. push (successor);

}

}

}

}

private Collection<Path> expand (Path path) throws AlgorithmException

{

Collection<Path> result = new ArrayList<> ();

WorldVertex tail = path. tail ();

Collection<WorldEdge> edges = getWorld (). getOutEdges (tail);

for (WorldEdge edge: edges)

{

Pair<WorldVertex> endpoints = getWorld (). getEndpoints (edge);

WorldVertex nextVertex = endpoints. getFirst () == tail?

endpoints. getSecond (): endpoints. getFirst ();

if (nextVertex. getMark () == WorldElement. MarkType. Visited)

continue;

result. add (path. addElementToCopy (edge, nextVertex));

}

return result;

}

@Override

protected void safeAbort ()

{

}

}

Haskell

Поиск в ширину. Решение не претендует на лаконичность, но работает.

Сначала выработаем рациональную схему представления графа. Будем хранить граф как список списков целых (кортежи и строки ни к чему!). Каждая вершина графа будет списком вершин, с которыми данная вершина связана. Так например, в графе [[1,2,5],.]

нулевая вершина связана с первой, второй и пятой. Вершины удобно нумеровать с нуля. Пусть число вершин графа = n

Нам понадобится три служебных списка:

que - для очереди (первоначально пуст);

pth - для восстановления пути (список длины n из нулей. В позиции стартовой вершины - 1);

chk - для отметки посещенности вершины (список длины n из нулей).

Алгоритм состоит из следующих шагов:

0) положить стартовую вершину в очередь que

1) если очередь que пуста - конец

2) взять первый элемент очереди que (k); поместить в que все еще не посещенные вершины, связанные с k и пометить их как посещенные; занести k в список pth в позиции с номерами вершин, связанных с k-й;

3) перейти на п.1

После работы алгоритма в списке pth находится информация о путях. Если нужно найти путь из стартовой вершины (с которой проработал алгоритм, описанный выше), в какую либо вершину j, то поступаем так:

0) полагаем i=j

1) берем i-й элемент списка pth. Присоединяем i к результату Если i-й элемент == - 1 - конец

2) полагаем i = i-му элементу pth

3) перходим к 1

После работы этого алгоритма результат будет равен пути из стартовой вершины в заданную.

Теперь реализуем это на HASKELL:

занесение в список chk в позицию n значения m

mark:: [Int] - > Int - > Int - > [Int]

mark chk n m | (n == 0) = m: (tail chk)

| otherwise = (head chk): (mark (tail chk) (n-1) m)

добавить в хвост очереди que все вершины графа g,

связанные с вершиной n и еще не посещенные

newV:: [[Int]] - > Int - > [Int] - > [Int] - > [Int]

newV g n chk que = (filter (\ x - > (chk!! x) == 0) (g!! n))

Занести в список pth значение n в позиции,

номера которых перечислены в списке f

setP:: [Int] - > Int - > [Int] - > [Int]

setP pth n [] = pth

setP pth n (f: fs) = setP (mark pth f n) n fs

Обход в ширину графа g с вершины, предварительно

помещенной в очередь que

bfs':: [[Int]] - > [Int] - > [Int] - > [Int] - > [Int]

bfs' g [] chk pth = pth

bfs' g que chk pth = (bfs' g (tq ++ nV) (setP chk 1 nV) (setP pth hq nV))

where tq= (tail que); hq= (head que); nV= (newV g hq chk tq);

Восстановление пути из стартовой вершины в заданную

showPath:: [Int] - > Int - > [Int]

showPath pth n | (pth!! n) == negate 1 = [n]

| otherwise = n: (showPath pth (pth!! n))

"Парадная" функция. Берет граф g и две вершины n и m

возвращает путь из n в m

bfs:: [[Int]] - > Int - > Int - > [Int]

bfs g n m = reverse $ showPath (bfs' g [n] (mark chk n 1) pth) m

where chk= (take k (repeat 0)); pth= (mark chk n (negate 1)); k=length g

Проврка:

Main> bfs [[1,2], [0,2,3,4], [0,1,5,6], [1], [1], [2], [2]] 1 6

[1,2,6]

Main> bfs [[1,2], [0,2,3,4], [0,1,5,6], [1], [1], [2], [2]] 2 4

[2,1,4]

Main> bfs [[1,2], [0,3,4], [0,5,6], [1], [1], [2], [2]] 2 4

[2,0,1,4]

С++

#include "stdafx. h" #include <iostream> using namespace std;

const int n=4;

int i, j;

// матрица смежности графа int GM [n] [n] = { {0, 1, 1, 0}, {0, 0, 1, 1}, {1, 0, 0, 1}, {0, 1, 0, 0} };

// поиск в ширину void BFS (bool *visited, int unit) { int *queue=new int [n];

int count, head;

for (i=0; i<n; i++) queue [i] =0;

count=0; head=0;

queue [count++] =unit;

visited [unit] =true;

while (head<count) { unit=queue [head++];

cout<<unit+1<<" ";

for (i=0; i<n; i++) if (GM [unit] [i] &&! visited [i]) { queue [count++] =i;

visited [i] =true;

} } delete [] queue;

} // главная функция void main () { setlocale (LC_ALL, "Rus");

int start;

cout<<"Стартовая вершина >> "; cin>>start;

bool *visited=new bool [n];

cout<<"Матрица смежности графа: "<<endl;

for (i=0; i<n; i++) { visited [i] =false;

for (j=0; j<n; j++) cout<<" "<<GM [i] [j];

cout<<endl;

} cout<<"Порядок обхода: ";

BFS (visited, start-1);

delete [] visited;

system ("pause>>void");

}

Pascal

program BreadthFirstSearch;

uses crt;

const n=4;

type

MassivInt=array [1. n, 1. n] of integer;

MassivBool=array [1. n] of boolean;

var

i, j, start: integer;

visited: MassivBool;

{матрица смежности графа}

const GM: MassivInt = (

(0, 1, 1, 0),

(0, 0, 1, 1),

(1, 0, 0, 1),

(0, 1, 0, 0));

{поиск в ширину}

procedure BFS (visited: MassivBool; _unit: integer);

var

queue: array [1. n] of integer;

count, head: integer;

begin

for i: =1 to n do queue [i]: =0;

count: =0; head: =0;

count: =count+1;

queue [count]: =_unit;

visited [_unit]: =true;

while head<count do

begin

head: =head+1;

_unit: =queue [head];

write (_unit, ' ');

for i: =1 to n do

begin

if (GM [_unit, i] <>0) and (not visited [i]) then

begin

count: =count+1;

queue [count]: =i;

visited [i]: =true;

end;

end;

end;

end;

{основной блок программы}

begin

clrscr;

write ('Стартовая вершина >> '); read (start);

writeln ('Матрица смежности графа: ');

for i: =1 to n do

begin

visited [i]: =false;

for j: =1 to n do

write (' ', GM [i, j]);

writeln;

end;

write ('Порядок обхода: ');

BFS (visited, start);

end.

В двух этих программах используется граф, изображенный на предыдущем рисунке, точнее его матрица смежности. На ввод может поддаваться только одно из 4 значений, т.к. в качестве стартовой возможно указать лишь одну из 4 имеющихся вершин (программы не предусматривают некорректных входных данных):

Граф представлен матрицей смежности, и относительно эффективности это не самый лучший вариант, так как время, затраченное на ее обход, оценивается в O (|V|²), а сократить его можно до O (|V|+|E|), используя список смежности.

алгоритм поиск ширина граф

Заключение