Теория хорошо описана на Вики. Суть в этой гифке ниже.
Моя скромная реализация для представления графа в виде матрицы смежности. Ноль в матрице смежности означает отсутствие ребра между вершинами. Единица – наличие. В основе обхода в ширину – такая структура как очередь. Первым вошел, первым вышел.
Своими словами (самое ценное, когда своими словами).
1 Берем стартовую вершину. Добавляем ее в очередь.
2 Ищем у этой вершины все инцидентные ребра. Добавляем их в очередь.
3 При добавлении каждой вершины что-то делаем.
4 Первая вершина отработала, удаляем ее из очереди.
5 Берем следующую по очереди вершину (в моей реализации left+1) и повторяем с п. 2
|
1 |
type TAdjencyMatrix=array of array of Integer; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
procedure TMain.BFS(AAdjencyMatrix: TAdjencyMatrix; AsizeOfAdjMatrix, AStartNode: integer ); var i, leftIndex, rightIndex:integer; isVisitedArray : array of boolean; queue : array of integer; sizeOfAdjMatrix:Integer; begin // initialization //AAdjencyMatrix must be inited before //randomInitAdjMatrix(AsizeOfAdjMatrix); SetLength(isVisitedArray,sizeOfAdjMatrix); for i := 0 to High(isVisitedArray) do isVisitedArray[i]:=false; SetLength(queue,sizeOfAdjMatrix); // max possible count of direct children for i := 0 to High(queue) do queue[i]:=0; leftIndex:=1; rightIndex:=1; queue[rightIndex]:=AStartNode; isVisitedArray[AStartNode]:=true; while leftIndex<=rightIndex do begin for i := 0 to sizeOfAdjMatrix-1 do if AAdjencyMatrix[AStartNode,i]<>0 then // all direct children begin Inc(rightIndex); queue[rightIndex]:=i; // adding to queue new element isVisitedArray[i]:=true; // do something else end; Inc(leftIndex); // removing from queue left element AStartNode:=queue[leftIndex]; // setting new start node end; end; |
Также рандомная инициализация BFS
|
1 2 3 4 5 6 7 8 9 10 |
procedure TMain.randomInitAdjMatrix( var AAdjencyMatrix:TAdjecyMatrix; AsizeOfAdjMatrix:integer ); // to init random values of AdjMatrix var i,j:integer; begin SetLength(AAdjencyMatrix,AsizeOfAdjMatrix,AsizeOfAdjMatrix); for i := 0 to High(AsizeOfAdjMatrix) do begin for j := 0 to High(AsizeOfAdjMatrix) do begin AAdjencyMatrix[i,j]:=Random(1); end; end; end; |
Список источников, которые мне помогли)