Графовый поиск в JS: поиск в глубину — 3

Алгоритм поиска в глубину — это рекурсивный алгоритм для поиска всех вершин графа или древовидной структуры данных, который исследует агрессивно и откатывается только тогда, когда необходимо. Обход означает посещение всех узлов графа. В этой статье мы узнаем, как реализовать это в JavaScript. Прочитайте Graph Search in JavaScript для предыдущих ссылок, которые будут использоваться в этой статье.

Используется для;

• Для поиска пути
• Чтобы проверить, является ли граф двудольным
• Для поиска компонентов сильной связи графа
• Для обнаружения циклов в графике

Выполнение

Рекурсивный подход

1- DFS(graph G, start vertex S)
2- mark s as explored
3- for every edge (s, v):
   -if v unexplored
     -DFS(G, V)

Давайте реализуем это в JavaScript, сначала мы создадим наш график, как описано в первой статье.

const list = new AdjacencyList(GraphType.DIRECTED);
const vertices = ["S", "A", "B", "C", "D"];
for (let i = 0; i < vertices.length; i++) {
  list.addVertex(vertices[i]);
}
// adding edges
list.addEdge("S", "A");
list.addEdge("S", "B");
list.addEdge("A", "C");
list.addEdge("A", "B");
list.addEdge("B", "D");
list.addEdge("C", "E");
list.addEdge("C", "D");
list.addEdge("D", "E");

… и время для реализации DFS в JavaScript

class DFS {
  private explored: string[] = [];
  private list: Map<string, string[]>;
  constructor(list: AdjacencyList) {
    this.list = list.getList();
  }
  
  execute(startNode: string) {
    // print the vertex
    console.log(startNode);
    // push vertex to explored vertices array
    this.explored.push(startNode);
    const neighbors = this.list.get(startNode);
    if (neighbors) {
      for (let neighbor of neighbors) {
        // run DFS in not explored
        if (!this.explored.includes(neighbor))
          this.execute(neighbor);
      }
    }
  }
}

Это наш рекурсивный подход. Временная сложность этого алгоритма составляет O(V).

Итеративный подход

При итеративном подходе мы будем использовать структуру данных Stack (LIFO), чтобы не забыть получить следующую вершину для начала поиска, когда на любой итерации возникает тупик.

1- DFS(graph G, start vertex S)
2- let T = stack data structure (LIFO)
3- Mark S as explored
4- Push S to T
5- while T not empty:
   - pop vertex from T, call it V
   - for each (V, W):
     - if W not explored
       - push to T
     - mark W as explored

Вот и все! Намного сложнее не так ли?

Наша реализация стека выглядит так

class Stack {
  private nodes: string[] = [];
  constructor() {}
  push(node: string) {
    this.nodes.push(node);
  }
  pop() {
    return this.nodes.pop();
  }
  get length() {
    return this.nodes.length;
  }
}

Мы объявляем наш стек в классе DFS

private s = new Stack();

затем реализуем нашу функцию выполнения

execute(startNode: string) {
  this.s.push(startNode);
  this.explored.push(startNode);
  while (this.s.length) {
    const v = this.s.pop() || "";
    console.log(v);
    const neighbors = this.list.get(v);
    if (neighbors) {
      for (let neighbor of neighbors) {
        if (!this.explored.includes(neighbor))
          this.s.push(neighbor);
      this.explored.push(neighbor);
      }
    }
  }
}

Заключение

Оба метода будут печатать следующее:

const dfs = new DFS(list);
dfs.execute("S");
/*
S
A
C
E
D
B
*/