Освоение алгоритма BFS: Пошаговое руководство с реальными примерами на JavaScript
Breadth-First Search (BFS) — это фундаментальный алгоритм в информатике, используемый для обхода или поиска древовидных или графовых структур данных. BFS исследует все узлы на текущем уровне глубины, прежде чем переходить к узлам на следующем уровне глубины.
Зачем изучать BFS?
- Кратчайший путь: BFS может найти кратчайший путь в невзвешенном графе.
- Обход порядка уровней: идеально подходит для обхода порядка уровней в древовидных структурах данных.
- Связность: Помогает находить связные компоненты в графах.
Пример из реального мира: Предложения друзей в социальной сети
Представьте, что вы пользуетесь социальной сетью и хотите найти предложения друзей. Сайт может использовать BFS для изучения вашей сети и эффективного поиска друзей.
Сценарий
Рассмотрим граф социальной сети, где узлы представляют пользователей, а ребра - дружеские отношения. Вы начинаете с пользователя (корневой узел) и изучаете его друзей (первый уровень), затем друзей друзей (второй уровень) и так далее.
Принципы работы BFS
- Очередь: Используйте очередь для отслеживания узлов, которые необходимо исследовать.
- Старт: Начните с корневого узла (текущего пользователя). Зарегистрируйте его и отметьте как посещенный.
- Исследование: Снимите очередь с узла, зачислите его соседей и отметьте как посещенные.
- Повтор: Продолжайте, пока все узлы не будут исследованы.
Пример
Давайте представим граф социальной сети:
Graph:
Alice
/ \
Bob Charlie
/ \ \
Dan Emma FrankЦель: пройти по графу, начиная с Алисы.
Шаги
- Начните с Алисы и зачислите её. И пометьте её как посещенную.
- Выпишите Алису, отметьте её соседей Боба и Чарли как посещенных и выпишите их.
- Выпишите Боба, посетите его, отметьте её соседей Дэна и Эмму как посещенных и зачислите их.
- Выпишите Чарли, посетите его, отметьте её соседа Фрэнка как посещенного и выпишите его.
- Выпишите Дэна (нет соседей, которых можно выписать).
- Выпишите Эмму, (нет соседей, которых можно выписать).
- Выпишите Фрэнка (нет соседей, которых можно выписать).
Порядок обхода BFS
Порядок посещения узлов будет таким: Алиса -> Боб -> Чарли -> Дэн -> Эмма -> Фрэнк.
Алгоритм BFS на JavaScript
Вот как можно реализовать BFS в JavaScript:
class Graph {
constructor() {
this.adjacencyList = {};
}addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
bfs(start) {
const queue = [start];
const result = [];
const visited = {};
visited[start] = true;
while (queue.length) {
const vertex = queue.shift();
result.push(vertex);
this.adjacencyList[vertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return result;
}
}
const g = new Graph();
g.addVertex("Alice");
g.addVertex("Bob");
g.addVertex("Charlie");
g.addVertex("Dan");
g.addVertex("Emma");
g.addVertex("Frank");
g.addEdge("Alice", "Bob");
g.addEdge("Alice", "Charlie");
g.addEdge("Bob", "Dan");
g.addEdge("Bob", "Emma");
g.addEdge("Charlie", "Frank");
console.log("BFS Traversal starting from Alice:", g.bfs("Alice"));Объяснение
Graph Class: Представляет граф с помощью списка смежности.addVertex: Добавляет вершину в граф.addEdge: добавляет ребро между двумя вершинами.bfs: Выполняет BFS-обход, начиная с заданной вершины.
Сложность
- Временная сложность: O(V + E), где V - количество вершин (пользователей), а E - количество ребер (дружеских связей).
- Пространственная сложность: O(V), что связано с хранением очереди и списка посещений.
Когда стоит использовать BFS?
- Поиск кратчайшего пути: В невзвешенном графе.
- Обход порядка уровней: В древовидных структурах данных.
- Поиск связных компонентов: В неориентированном графе.
BFS - это универсальный алгоритм, широко используемый в различных приложениях, от социальных сетей до маршрутизации и многого другого. Поняв и реализовав BFS, вы сможете эффективно решать задачи, связанные с обходом и связностью графов.
