November 16, 2021 https://www.youtube.com/watch?v=cWNEl4HE2OE

1. Graph (Map 활용)

// DATA
const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const routes = [
    ['PHX', 'LAX'],
    ['PHX', 'JFK'],
    ['JFK', 'OKC'],
    ['JFK', 'HEL'],
    ['JFK', 'LOS'],
    ['MEX', 'LAX'],
    ['MEX', 'BKK'],
    ['MEX', 'LIM'],
    ['MEX', 'EZE'],
    ['LIM', 'BKK'],
];

// The graph
const adjacencyList = new Map();

// Add node
function addNode(airport) {
    adjacencyList.set(airport, []);
}

// Add edge, undirected
function addEdge(origin, destination) {
    adjacencyList.get(origin).push(destination);
    adjacencyList.get(destination).push(origin);
}

// Create the Graph
airports.forEach(addNode);
routes.forEach(route => addEdge(...route))

console.log(adjacencyList);

2. BFS (가까운 노드 우선 탐색)

시간 복잡도 : O(v+e) ⇒ Nodes + Edges

// BFS Breadth First Search
function bfs(start) {
  const visited = new Set(); //방문한 곳 관리

  const queue = [start]; //시작 지점

  while (queue.length > 0) {
    const airport = queue.shift(); // mutates the queue

    const destinations = adjacencyList.get(airport);

    for (const destination of destinations) {
      if (destination === "BKK") {
        console.log(`BFS found Bangkok!`);
      }

      if (!visited.has(destination)) {
        visited.add(destination);
        queue.push(destination);
        console.log(destination)
      }
    }
  }
}
bfs("PHX");

3. DFS (깊은 부분 우선 탐색)

시간 복잡도 : O(v+e) ⇒ Nodes + Edges

function dfs(start, dfsVisited = new Set()) {
  //중복 방문을 방지 하기 위해 Set 사용
  dfsVisited.add(start);

  const destinations = adjacencyList.get(start);

  for (const destination of destinations) {
    if (destination === "BKK") {
      console.log(`DFS found Bangkok`);
      return;
    }
    if (!dfsVisited.has(destination)) {
      console.log(Array.from(dfsVisited));
      dfs(destination, dfsVisited);
    }
  }
}
dfs("PHX");