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

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

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

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

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

popa

Go

package main

const (
	// Start - стартовая вершина
	Start = 2
	// Vert - кол-во вершин
	Vert = 7
)

func main() {
	graph := [Vert][]int{
		{1, 2},
		{0, 2},
		{0, 1, 3, 4, 5},
		{2},
		{2, 6},
		{2, 6},
		{4, 5},
	}

	q := make([][]int, 0, len(graph))
	q = append(q, graph[Start])

	used := make(map[int]bool, len(graph))
	used = map[int]bool{Start: true}

	for len(q) > 0 {
		for _, key := range q[len(q)-1] {
			if _, ok := used[key]; !ok {
				q = append(q, graph[key])
			}
			used[key] = true
		}
		q = q[:len(q)-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'));

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;
    }
  }
}

JavaScript

//           A
//         /   \
//        B     C
//      /  \   / \
//     D    E F   G

let graph = {}
graph["A"] = ['B', 'C']
graph["B"] = ['D', 'E']
graph["C"] = ['F', 'G']
graph["D"] = []
graph["E"] = []
graph["F"] = []
graph["G"] = []

function bfs(graph, s, t) {
	let queue = [] // инициализируем очередь

	queue.push(s) // добавляем начальную вершину в очередь
	s.visited = true // // помечаем начальную вершину как посещенную вершину во избежание повторного добавления в очередь
	while(queue.length > 0) { // Пока в очереди есть элементы
		let v = queue.shift() // удаляем первый (верхний) элемент из очереди
		for(let i of graph[v]) { // abj[v] - соседи v
			if(!i.visited) { // если сосед не посещался
				queue.push(i) // добавляем его в очередь
				i.visited = true // помечаем вершину как посещенную
				if(i === t) // если сосед является пунктом назначения
                    return true // вершина найдена
			}
		} 
	}
	return false // если от s до t добраться невозможно
}