Algoritm - Graph Traversal (DFS, BFS)

Graph Traversal

• Visting / Updating / Checking each vertex in a graph

Usuage of Graph Traversal

• 소셜 네트워크 (SNS)
• 웹페이지 탐색 (an webpage => other webpage)
• 가장 근접한 값 또는 추천을 찾기
• 가장 짧은 경로 탐색
  • GPS Navigation
  • Solving mazes
  • AI (shorest path to win the game)

Depth First Graph Traversal (DFS)

• DFS : backtracking 전에 가능한 브랜치를 모두 탐색함

Depth First Graph Traversal - Recursive

• DFS (Recursive) 함수 구현 방법
  1. 시작할 vertex를 인수로 받음
  2. 최종 결과가 저장될 result 배열을 생성함
  3. 방문한 vertices를 저장할 visited 객체를 생성함
  4. vertex를 인수로 받는 helper function을 정의함
     • helper function은 vertex가 비어 있으면 early return함 (base case)
     • helper function은 visited 객체와 result 배열에 vertex를 추가함
     • vertex에 대한 adjacency list 안의 vertex들에 대해서 반복문을 실행함
     • adjacency list 안에 방문하지 않은 vertex가 있다면, 그 vertex에 대해서 helper function을 재귀적으로 호출함
  5. 시작할 vertex에 대해서 helper function을 호출함
  6. result 배열을 반환함

class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  
  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }
  
  removeEdge(vertex1,vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2);
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1);
  }
  
  removeVertex(vertex) {
    while(this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
  
  depthFirstRecursive(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;
    
    (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    })(start);
    
    return result;
  }
}

let g = new Graph();

g.addVertex("A")
g.addVertex("B")
g.addVertex("C")
g.addVertex("D")
g.addVertex("E")
g.addVertex("F")


g.addEdge("A", "B")
g.addEdge("A", "C")
g.addEdge("B","D")
g.addEdge("C","E")
g.addEdge("D","E")
g.addEdge("D","F")
g.addEdge("E","F")
g.depthFirstRecursive("A")

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

Depth First Graph Traversal - Iterative

• DFS(Interative) 함수 구현 방법
  1. 시작할 vertex를 인수로 받음
  2. vertices를 추적할 stack 배열을 생성함
  3. 최종 결과가 저장된 result 배열을 생성함
  4. 방문할 vertex를 저장할 visited 객체를 생성함
  5. 시작할 vertex를 stack 배열에 추가하고, visited 객체에 그 vertex를 키로 가진 true 값을 추가함
  6. stack의 길이가 0이 아닐 때, 아래 과정을 반복함
     • stack에서 다음 vertex를 pop함
       • 다음 vertex에 대한 adjacency list에서 모든 이웃 vertex에 다음 조건문을 실행함
       • 이웃 vertex가 visited 객체에 없을 경우, visited 객체에 이웃 vertex를 키로 가진 true 값으로 저장하고 stack에 이웃 vertex를 추가함
  7. result 배열을 반환함

class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  
  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }
  
  removeEdge(vertex1,vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2);
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1);
  }
  
  removeVertex(vertex) {
    while(this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
  
  depthFirstIterative(start) {
    const result = [];
    const stack = [start];
    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;
  }
}

let g = new Graph();

g.addVertex("A")
g.addVertex("B")
g.addVertex("C")
g.addVertex("D")
g.addVertex("E")
g.addVertex("F")


g.addEdge("A", "B")
g.addEdge("A", "C")
g.addEdge("B","D")
g.addEdge("C","E")
g.addEdge("D","E")
g.addEdge("D","F")
g.addEdge("E","F")
g.depthFirstIterative("A")

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

Breadth First Graph Traversal (BFS)

• BFS : 현재 첫 번째 깊이의 이웃들을 방문함

• BFS 함수 구현 방법

  1. 시작할 vertex를 인수로 받음
  2. queue 배열을 생성하고, queue 배열에 시작할 vertex를 넣음
  3. 방문한 vertex를 저장할 result 배열을 생성함
  4. 방문한 vertex를 저장할 visited 객체를 생성함
  5. visited 객체에 시작할 vetex를 키로 가지는 true 값을 저장함
  6. queue의 길이가 0이 아닌 경우 아래 과정을 반복함
     • queue에서 첫 번째 vertex를 빼내서, result 배열에 추가하고, visited 객체에 true 값으로 저장함
     • 빼낸 vertex에 대한 adjacency list 안에 있는 모든 이웃 vetex를 순회함
     • 이웃 vertex가 visited 객체에 없을 경우, 이웃 vertex를 visited 객체에 true 값으로 저장하고 queue에 이웃 vertex를 추가함
  7. result 배열을 반환함

class Graph {
  constructor(){
    this.adjacencyList = {};
  }
  
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  
  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }
  
  removeEdge(vertex1,vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2);
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1);
  }
  
  removeVertex(vertex) {
    while(this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
  
  breadthFirst(start) {
    const result = [];
    const queue = [start];
    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;
  }
}

let g = new Graph();

g.addVertex("A")
g.addVertex("B")
g.addVertex("C")
g.addVertex("D")
g.addVertex("E")
g.addVertex("F")


g.addEdge("A", "B")
g.addEdge("A", "C")
g.addEdge("B","D")
g.addEdge("C","E")
g.addEdge("D","E")
g.addEdge("D","F")
g.addEdge("E","F")
g.breadthFirst("A")

//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F