Реализации алгоритмов/Поиск в ширину
Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе.
Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника .
Рассмотрим все рёбра , выходящие из узла . Если очередной узел является целевым узлом, то поиск завершается; в противном случае узел добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла , из очереди извлекается следующий узел , и процесс повторяется.
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
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]
}
}
$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;
}
}
}
// 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 добраться невозможно
}