Перехід по графу за допомогою JavaScript | BFS та DFS

Графи є фундаментальною структурою даних в інформатиці, що використовуються для моделювання взаємозв'язків між об'єктами. В JavaScript графи зазвичай представляються за допомогою списку суміжності, де кожна вершина (або вузол) має список своїх сусідів.

Тут ми розглянемо дві важливі техніки обходу графів: пошук в ширину (BFS) та пошук в глибину (DFS).

Що таке граф?

Граф складається з двох основних компонентів:

1. Вершини (вузли): Це точки або об'єкти в графі.
2. Ребра: Це зв'язки між вершинами.

Графи можуть бути:

• Орієнтовані: Ребра мають напрямок, наприклад, від вершини A до вершини B.
• Неорієнтовані: Ребра є двосторонніми, наприклад, від вершини A до вершини B і навпаки.

Графи можна представляти в JavaScript за допомогою списку суміжності або матриці суміжності.
Тут ми будемо використовувати представлення графа через список суміжності.

Представлення графів в JavaScript

Ось простий граф, реалізований за допомогою списку суміжності в JavaScript:

class Graph {  
 constructor(noOfVertices) {  
 this.v = noOfVertices;  
 this.adj = new Array(noOfVertices).fill(null).map(() => []);  
 this.vertices = []; // Для зберігання назв вершин  
 }  

 addVertex(vertex) {  
 this.vertices.push(vertex);  
 }  

 addEdge(v1, v2) {  
 const v1Index = this.vertices.indexOf(v1);  
 const v2Index = this.vertices.indexOf(v2);  

 if (v1Index === -1 || v2Index === -1) {  
 console.error("Одна або обидві вершини не знайдені.");  
 return;  
 }  

 // Додавання ребер для неорієнтованого графа  
 this.adj[v1Index].push(v2Index);  
 this.adj[v2Index].push(v1Index);  
 }  

 BFS(start) {  
 const startIndex = this.vertices.indexOf(start);  
 if (startIndex === -1) {  
 console.error("Стартову вершину не знайдено.");  
 return [];  
 }  

 let visited = new Array(this.v).fill(false);  
 let res = [];  
 let q = [startIndex];  
 visited[startIndex] = true;  

 while (q.length > 0) {  
 const vertexIndex = q.shift();  
 res.push(this.vertices[vertexIndex]);  
 for (let neighbor of this.adj[vertexIndex]) {  
 if (!visited[neighbor]) {  
 visited[neighbor] = true;  
 q.push(neighbor);  
 }  
 }  
 }  
 return res;  
 }  

 DFS(start) {  
 const startIndex = this.vertices.indexOf(start);  
 if (startIndex === -1) {  
 console.error("Стартову вершину не знайдено.");  
 return [];  
 }  

 let visited = new Array(this.v).fill(false);  
 let res = [];  
 let stack = [startIndex];  
 visited[startIndex] = true;  

 while (stack.length > 0) {  
 const vertexIndex = stack.pop();  
 res.push(this.vertices[vertexIndex]);  

 for (let neighbor of this.adj[vertexIndex]) {  
 if (!visited[neighbor]) {  
 visited[neighbor] = true;  
 stack.push(neighbor);  
 }  
 }  
 }  

 return res;  
 }  

}  

let graph = new Graph(6); // Створення графа  

// Додавання вершин з іменами у вигляді рядків  
graph.addVertex('A');  
graph.addVertex('B');  
graph.addVertex('C');  
graph.addVertex('D');  
graph.addVertex('E');  
graph.addVertex('F');  

// Додавання ребер між вершинами  
graph.addEdge('A', 'B');  
graph.addEdge('A', 'D');  
graph.addEdge('B', 'C');  
graph.addEdge('B', 'E');  
graph.addEdge('D', 'E');  
graph.addEdge('E', 'F');  

// Виконання BFS, починаючи з 'A'  
console.log("BFS - ", graph.BFS('A'));  
console.log("DFS - ", graph.DFS('A'));

Результат:

BFS - ['A', 'B', 'D', 'C', 'E', 'F']  
DFS - ['A', 'D', 'E', 'F', 'B', 'C']




Перекладено з: [Traversal in Graph using JavaScript | BFS & DFS](https://medium.com/@janhavinagalkar13/traversal-in-graph-using-javascript-bfs-dfs-a95334f0c903?source=rss------javascript-5)