Giới thiệu

Có 2 cách duyệt Graph:

• Depth First Search (DFS)

• Breadth First Search (BFS)

Depth First Search (DFS)

Có 2 cách để thực thi DFS

• Dùng đệ quy

• Dùng vòng lặp

DFS Recursive

 depthFirstRecursive(start) {
    const result = [];
    const visited = {};

    (function dfs(vertex) {
      if (!vertex) {
        return null;
      }

      visited[vertex] = true;
      result.push(vertex);
      console.log(this.adjacencyList[vertex]);
    })(start);
  }

DFS Iterative

depthFirstIterative(start) {
    const stack = [start];
    const result = [];
    const visited = {};
    let currentVertex;

    visited[start] = true;
    while (stack?.length) {
      currentVertex = stack.pop();
      result.push(currentVertex);

      this.adjacencyList[currentVertex]?.forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }

    return result;
  }

Breadth First Search (DFS)

breadthFirst(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex;

    visited[start] = true;
    while (queue?.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex]?.forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }

    return result;
  }