Реализации алгоритмов/Поиск в ширину

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

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

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

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

Python[править]

adj = [    
#список смежности
    [1,3], # 0
    [0,3,4,5], # 1
    [4,5], # 2
    [0,1,5], # 3
    [1,2], # 4
    [1,2,3] # 5
]

level = [-1] * len(adj) 
#список уровней вершин

def bfs(s):
    global level
    level[s] = 0
# уровень начальной вершины
    queue = [s]
 # добавляем начальную вершину в очередь
    while queue:
 # пока там что-то есть
        v = queue.pop(0)
 # извлекаем вершину
        for w in adj[v]: 
# запускаем обход из вершины v
            if level[w] == -1: 
# проверка на посещенность
                queue.append(w) 
# добавление вершины в очередь
                level[w] = level[v] + 1 
# подсчитываем уровень вершины

for i in range(len(adj)):
    if level[i] == -1:
        bfs(i)
 # на случай, если имеется несколько компонент связности

print(level[2]) 
# уровень вершины 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;
    }
  }
}