]] 1 6
[1,2,6] gt; bfs [[1,2], [0,2,3,4], [0,1,5,6], [1], [1], [2], [2]] 2 4
[2,1,4] gt; bfs [[1,2], [0,3,4], [0,5,6], [1], [1], [2], [2]] 2 4
[2,0,1,4]
С ++
# include stdafx. h #include lt; iostream gt; 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 lt; n; i ++) queue [i]=0;=0; head=0; [count ++]=unit; [unit]=true; (head lt; count) {unit=queue [head ++]; lt; lt; unit + 1 lt; lt; raquo ;; (i=0; i lt; n; i ++) if (GM [unit] [i] amp; amp ;! visited [i]) {queue [count ++]=i; [i]=true;
}} delete [] queue;
}//головна функція void main () {setlocale (LC_ALL, Rus ); start; lt; lt; Стартова вершина gt; gt; raquo ;; cin gt; gt; start; * visited=new bool [n]; lt; lt; Матриця суміжності графа: lt; lt; endl; (i=0; i lt; n; i ++) {visited [i]= false; (j=0; j lt; n; j ++) cout lt; lt; lt; lt; GM [i] [j]; lt; lt; endl;
} cout lt; lt; Порядок обходу: raquo ;; (visited, start - 1); [] visited; ( pause gt; gt; 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 lt; count do:=head + 1;
_ unit:=queue [head]; (_ unit, ); i:=1 to n do (GM [_unit, i] lt; gt; 0) and (not visited [ i]) then:=count + 1; [count]:=i; [i]:=true ;;;;;
{основний блок програми}; ( Стартова вершина gt; gt; ); read (start); ( Матриця суміжності графа: ); i:=1 to n do [i]:=false; j:=1 to n do ( raquo ;, GM [i, j]) ;;; ( Порядок обходу: ); (visited, start);.
У двох цих програмах використовується граф, зображений на попередньому малюнку, точніше його матриця суміжності. На введення може піддаватися тільки одне з 4 значень, тому в якості стартової можливо вказати лише одну з 4 наявних вершин (програми не передбачають некоректних вхідних даних):
Вхідні данниеВиходние данние11 2 3 422 3 4 133 1 4 244 2 3 1
Граф представлений матрицею суміжності, і щодо ефективності це не найкращий варіант, тому що час, витрачений на її обхід, оцінюється в O (| V | 2), а скоротити його можна до O (| V | + | E |), використовуючи список суміжності.
алгоритм пошук ширина граф
Висновок
Пошук в ширину реалізується за допомогою структури чергу. Для цього занесемо в чергу вихідну вершину. Потім будемо працювати, поки черга не спорожніє, таким чином: виберемо елемент з черги і додамо всі суміжні йому елементи, які ще не використані.
Список літератури
1. Кузнєцов О.П., Адельсон-Бєльський Г.М. Дискретна математика для інженерів.- М .: Вища школа, 1988. - 480 с.
. Коршунов Ю.М. Математичні основи кібернетики: Учеб. Посібник для вузів.- 3-е изд. перераб. і доп.- М .: Вища школа, 1987. - 496 с .: ил.
. Новиков Ф.А. Дискретна математика для програмістів.- Спб: Пітер, 2000. - 304 с .: ил.
. Яблонський С.В. Введення в дискретну математику: Навчальний посібник для Вузів/Під ред.В.А. Садовничого - 3-е изд. стер.- М .: Вища. шк., 2001. - 384 с.
. Липський В. Комбінаторика для програмістів. М .: Світ, 1988. - 213 С.
. Крістофідес Р. Теорія графів. Алгоритмічний підхід. М .: Світ, 1978. - 432 с.
