Алгоритм поиска в ширину

Содержание

Введение

1. Работа алгоритма поиска в ширину

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

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

2. Схема алгоритма поиска в ширину

3. Примеры реализации

Заключение

Список литературы

Введение

Алгоритм - набор инструкций <https://ru.wikipedia.org/wiki/%D0%9E%D0%BF%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%28%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29>, описывающих порядок действий исполнителя для достижения результата решения задачи <https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87> за конечное число действий. В старой трактовке вместо слова "порядок" использовалось слово "последовательность", но по мере развития параллельности в работе компьютеров слово "последовательность" стали заменять более общим словом "порядок". Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Ранее часто писали "алгорифм", сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм <https://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%84%D0%BC> Маркова <https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2,_%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B9_%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B5%D0%B2%D0%B8%D1%87_%28%D0%BC%D0%BB%D0%B0%D0%B4%D1%88%D0%B8%D0%B9%29>).

Часто в качестве исполнителя выступает некоторый механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма необязательно относится к компьютерным программам <https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0>, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.

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

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

Рисунок 1 - Поиск в ширину

1. Работа алгоритма поиска в ширину

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

Поиск в ширину или 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 будет хранить задействованные узлы. Напомним, что структура данных "очередь" работает по принципу "первый пришел - первый вышел". Рассмотрим разбитый на этапы процесс обхода графа:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекурсивная формулировка:

BFS (start_node, goal_node) {

return BFS' ({start_node}, ∅, goal_node);

}' (fringe, visited, goal_node) {

if (fringe == ∅) {

// Целевой узел не найден

return false;

}

if (goal_node ∈ fringe) {

return true;

}

return BFS' ({child | x ∈ fringe, child ∈ expand (x) } \ visited, visited ∪ fringe, goal_node);

}

Итеративная формулировка:

BFS (start_node, goal_node) {

for (all nodes i) visited [i] = false; // изначально список посещённых узлов пуст

queue. push (start_node); // начиная с узла-источника

visited [start_node] = true;

while (! queue. empty ()) { // пока очередь не пуста

node = queue. pop (); // извлечь первый элемент в очереди

if (node == goal_node) {

return true; // проверить, не является ли текущий узел целевым

foreach (child in expand (node)) { // все преемники текущего узла,.

if (visited [child] == false) { //. которые ещё не были посещены.

queue. push (child); //. добавить в конец очереди.

visited [child] = true; //. и пометить как посещённые

}

}

}

return false; // Целевой узел недостижим

}

2. Схема алгоритма поиска в ширину

Алгоритм

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

Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т.д.

Граф схема алгоритма поиска в ширину

3. Примеры реализации

Python

BFS (s,Adj):

level = { s: 0 }= { s: None }= 1= [s]frontier:= []u in frontier:v in Adj [u]:v not in level:[v] = i[v] = u. append (v)= next+= 1

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'));bfs ($graph, $startNode = 'A')

{

$visited = array ();

$queue = array ();

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

$visited [$startNode] = true;(count ($queue) > 0)

{

$currentNodeAdj = array_pop ($queue);($currentNodeAdj as $vertex)

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

{_unshift ($queue, $graph [$vertex]);

}

$visited [$vertex] = true;

}

}

}

С++

#include <vector>

#include <stdio. h>

#include <queue>

#include <iostream>namespace std;main ()

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

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

// чтение графаAdj [n] [n] = {

{0,1,0,0},

{1,0,1,0},

{0,1,0,1},

{0,0,1,0} };(int i = 0; i < n; i++)

{. push_back (vector<int> ());(int j = 0; j < n; j++)

{[i]. push_back (0);[i] [j] =Adj [i] [j];

}

}<int> q;. push (s);<bool> used (n);<int> d (n), p (n);[s] = true;[s] = - 1;(! q. empty ())

{v = q. front ();(size_t i = 0; i < g [v]. size (); ++i)

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

{[i] = true;. push (i);

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

p [i] = v; // parent;

}

}. pop ();

}(int i = 0; i < n; i++)<< d [i] << " ";<< endl;(int i = 0; i < n; i++)<< p [i] << " ";<< endl;

system ("pause");0;

}

Pascal

const= 1000;i,j,n, consp,cur,st,fin: integer; way,q: array [1. l] of integer;: array [1. l] of integer;: array [1.100] of array [1.100] of integer;: array [1. l] of integer;,e: integer;add (var i: integer);i < l then i: =i+1 else i: =1;;i: =1 to l do[i]: =0;[i]: =0;;(n);i: =1 to n doj: =1 to n do(m [i,j]);(st,fin);: =1;: =b+1;[b]: =st;(cur<>fin) do: =q [b];(b);[cur]: =1;(b<>e) and (cur <> fin) theni: =1 to n do( (m [i,cur] =1) and (was [i] =0)) then

begin

add (e);[e]: =i;[i]: =cur;;;;: =1;[1]: =fin;(cur <> st) do[i]: =cur;(i);: =pred [cur];;i: =1 to i do(way [i]);;;

end.

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

public class WideAlgo {static void main (String [] args) {theGraph = new Graph ();. addVertex ('A'); // 0. addVertex ('B'); // 1. addVertex ('C'); // 2. addVertex ('D'); // 3. addVertex ('E'); // 4. addEdge (0, 1); // AB. addEdge (1,2); // BC. addEdge (0,3); // AD. addEdge (3,4); // DE. out. print ("Посещения: ");. bfs ();. out. println ();

}class Queue {final int SIZE = 20;int [] queArray;int front;int rear;Queue () {= new int [SIZE];= 0;= - 1;

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

{(rear == SIZE - 1)= - 1;[++rear] = j;

{temp = queArray [front++];(front == SIZE)= 0;temp;

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

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

}

}class Vertex {char label; // labelboolean wasVisited;Vertex (char l) {= l;= false;

}

}class Graph {final int MAX_VERTS = 20;Vertex vertexList []; // list of verticesint adjMat [] []; // adjacency matrixint nVerts; // current number of verticesQueue theQueue;Graph () {= new Vertex [MAX_VERTS];

// adjacency matrix= new int [MAX_VERTS] [MAX_VERTS];= 0;(int j = 0; j < MAX_VERTS; j++)

// set adjacency(int k = 0; k < MAX_VERTS; k++)

// matrix to 0[j] [k] = 0;= new Queue ();

}void addVertex (char l) {[nVerts++] = new Vertex (l);

}void addEdge (int start, int end) {[start] [end] = 1;[end] [start] = 1;

}void displayVertex (int v) {. out. print (vertexList [v]. label);

}

// breadth-first searchvoid bfs ()

{ // begin at vertex 0[0]. wasVisited = true; // mark it(0); // display it. insert (0); // insert at tailv2;(! theQueue. isEmpty ()) // until queue empty,

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

// until it has no unvisited neighbors( (v2 = getAdjUnvisitedVertex (v1))! = - 1) { // get one,[v2]. wasVisited = true; // mark it(v2); // display it. insert (v2); // insert it

}

}

// queue is empty, so we're done(int j = 0; j < nVerts; j++)

// reset flags[j]. wasVisited = false;

}

// returns an unvisited vertex adj to vint getAdjUnvisitedVertex (int v) {(int j = 0; j < nVerts; j++)(adjMat [v] [j] == 1 && vertexList [j]. wasVisited == false)

return j;- 1;

}

}

}

Perl

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

{

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

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

$state{$key} = "SERIY"; # метим её, как просмотренную(0. scalar @{$graph{$key}} - 1) # бежим по смежным вершинам

{

$p = shift @queue; # извлекаем 1-ую вершину@queue, $graph{$key} [$_]; # добавляем смежные вершины($state{$graph{$key} [$_] } eq "SERIY") # если мы уже просматривали вершину, то существует цикл

{ "cicle"

}

{

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

}

}

}

}

Java

package problemresolver. algorithm. base;

import problemresolver. world. Path;

public interface TreeSearchContainer

{

void push (Path path); pop (); 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

{saModel =. castToSingleAgentAlgorithmModel (model); . checkSingleAgentAlgorithmModel (saModel); agent = saModel. getAgentLocation ();

agent. setMark (WorldElement. MarkType. Visited);

fringe = createContainer ();

setRuned (true);

}

protected abstract TreeSearchContainer createContainer ();

@Override

protected void safeDoStep ()

throws AlgorithmException, AlgorithmRuntimeException

{

if (fringe. isEmpty ())

{();

return;

}path = fringe. pop ();

Collection<Path> successors = expand (path);

for (Path successor: successors)

{successorTail = successor. tail (); successorResident = successorTail. getResident ();

if (successorResident! = null &&

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

{();

successor. mark (WorldElement. MarkType. Step);

}

else

{

successorTail. setMark (WorldElement. MarkType. Visited);

if (successorResident == null ||

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

{. 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); 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 из нулей).

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

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

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

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

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

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

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

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

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

) перходим к 1

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

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

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

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

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

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

newV:: [[Int]] - > Int - > [Int] - > [Int] - > [Int]g n chk que = (filter (\ x - > (chk!! x) == 0) (g!! n))

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

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

setP:: [Int] - > Int - > [Int] - > [Int]pth n [] = pthpth n (f: fs) = setP (mark pth f n) n fs

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

помещенной в очередь que':: [[Int]] - > [Int] - > [Int] - > [Int] - > [Int]' g [] chk pth = pth' g que chk pth = (bfs' g (tq ++ nV) (setP chk 1 nV) (setP pth hq nV))tq= (tail que); hq= (head que); nV= (newV g hq chk tq);

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

showPath:: [Int] - > Int - > [Int]pth n | (pth!! n) == negate 1 = [n]

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

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

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

bfs:: [[Int]] - > Int - > Int - > [Int]g n m = reverse $ showPath (bfs' g [n] (mark chk n 1) pth) mchk= (take k (repeat 0)); pth= (mark chk n (negate 1)); k=length g

Проврка:> bfs [[1,2], [0,2,3,4], [0,1,5,6], [1], [1], [2], [2]] 1 6

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

[2,1,4]> 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;int n=4;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];count, head;(i=0; i<n; i++) queue [i] =0;=0; head=0;[count++] =unit;[unit] =true;(head<count) { unit=queue [head++];<<unit+1<<" ";(i=0; i<n; i++) if (GM [unit] [i] &&! visited [i]) { queue [count++] =i;[i] =true;

} } delete [] queue;

} // главная функция void main () { setlocale (LC_ALL, "Rus");start;<<"Стартовая вершина >> "; cin>>start;*visited=new bool [n];<<"Матрица смежности графа: "<<endl;(i=0; i<n; i++) { visited [i] =false;(j=0; j<n; j++) cout<<" "<<GM [i] [j];<<endl;

} cout<<"Порядок обхода: ";(visited, start-1);[] visited;("pause>>void");

}

Pascal

program BreadthFirstSearch;crt;n=4;=array [1. n, 1. n] of integer;=array [1. n] of boolean;, j, start: integer;: MassivBool;

{матрица смежности графа}GM: MassivInt = (

(0, 1, 1, 0),

(0, 0, 1, 1),

(1, 0, 0, 1),

(0, 1, 0, 0));

{поиск в ширину}BFS (visited: MassivBool; _unit: integer);: array [1. n] of integer;, head: integer;i: =1 to n do queue [i]: =0;: =0; head: =0;: =count+1;[count]: =_unit;[_unit]: =true;head<count do: =head+1;

_unit: =queue [head];(_unit, ' ');i: =1 to n do(GM [_unit, i] <>0) and (not visited [i]) then: =count+1;[count]: =i;[i]: =true;;;;;

{основной блок программы};('Стартовая вершина >> '); read (start);('Матрица смежности графа: ');i: =1 to n do[i]: =false;j: =1 to n do(' ', GM [i, j]);;;('Порядок обхода: ');(visited, start);.

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

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

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

Заключение

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

Список литературы

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Энергоатомиздат, 1988. - 480 с.

. Коршунов Ю.М. Математические основы кибернетики: Учеб. Пособие для вузов. - 3-е изд. перераб. и доп. - М.: Энергоатомиздат, 1987. - 496 с.: ил.

. Новиков Ф.А. Дискретная математика для программистов. - Спб: Питер, 2000. - 304 с.: ил.

. Яблонский С.В. Введение в дискретную математику: Учебное пособие для Вузов/ Под ред.В.А. Садовничего - 3-е изд. стер. - М.: Высш. шк., 2001. - 384 с.

. Липский В. Комбинаторика для программистов. М.: Мир, 1988. - 213 С.

. Кристофидес Р. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432 с.