그래프 순회

실생활 예시

*Peer to peer networking(P2P)

=> 개인 대 개인 통신망 (중앙 서버 없이 컴퓨터끼리 서버,클라이언트 역할 -> 서로 연결해서 파일 주고 받기)

https://ko.wikipedia.org/wiki/P2P

가장 가까운 것을 찾거나 최단 거리 검색

GPS, 미로 풀기, AI

 

 

DFS(깊이 우선 탐색)

재귀와 순회의 순서는 다름 -> 그래프를 리스트로 나타냈을 때 재귀는 배열의 앞부분부터 노드가 빠지도록 동작을 하지만

순회는 pop메서드로 인해서 배열의 뒷부분이 먼저 빠진다

1) 재귀

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

2) 순회

  depthFirstIterative(start){
    const stack=[start];
    const result=[]
    const visited={};
    visited[start]=true;
    let currentVertex
    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
  }

BFS(너비 우선 탐색)

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

    while(queue.length){
      currentVertex=queue.shift()
      result.push(currentVertex)
      //slice().reverse()로 하게되면 순서 반대
      this.adjacencyList[currentVertex].forEach(neighbor=>{
        if(!visited[neighbor]){
          visited[neighbor]=true
          queue.push(neighbor)
        }
      })
    }
    return result
  }