# [DSA] Graph Traversal

# Giới thiệu

Có 2 cách duyệt Graph:

* Depth First Search (DFS)
    
* Breadth First Search (BFS)
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1752495633691/93a15f0f-405d-4cb9-b358-6461d5747a85.png align="center")

# Depth First Search (DFS)

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

* Dùng đệ quy
    
* Dùng vòng lặp
    

## DFS Recursive

```jsx
 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

```jsx
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)

```jsx
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;
  }
```