[JavaScrit] 4(완). 그래프 알고리즘

1. 그래프 데이터 구조

그래프는 일반적으로 인접 리스트 또는 인접 행렬로 표현되며, 인접 리스트를 사용한 방식은 다음과 같습니다.

class GraphData {
  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);
  }
}

---

2. 너비 우선 탐색 (BFS)

BFS에서 각 노드를 방문할 때마다 console.log()를 사용해 출력합니다.

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set();
  visited.add(start);

  console.log("BFS List:");

  while (queue.length > 0) {
    const vertex = queue.shift();
    console.log(vertex); // Now Node Coming

    for (const neighbor of graph.adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

---

3. 깊이 우선 탐색 (DFS)

스택을 사용한 DFS에서도 각 노드를 방문할 때마다 출력합니다.

function dfs(graph, start) {
  const stack = [start];
  const visited = new Set();
  visited.add(start);

  console.log("DFS (Stack) Come List:");

  while (stack.length > 0) {
    const vertex = stack.pop();
    console.log(vertex); // Now Node Come

    for (const neighbor of graph.adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
}

 

재귀를 사용한 DFS 에서도 각 노드를 방문할 때마다 출력합니다.

function dfsRecursive(graph, vertex, visited = new Set()) {
  visited.add(vertex);
  console.log(vertex); // Now coming Node

  for (const neighbor of graph.adjacencyList[vertex]) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited);
    }
    
  }
}

---

4. 사용 예시 

이제 그래프를 생성하고 각 탐색을 실행할 수 있습니다.

class GraphData {
  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);
  }
}

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set();
  visited.add(start);

  console.log("BFS List:");

  while (queue.length > 0) {
    const vertex = queue.shift();
    console.log(vertex); // Now Node Coming

    for (const neighbor of graph.adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

function dfs(graph, start) {
  const stack = [start];
  const visited = new Set();
  visited.add(start);

  console.log("DFS (Stack) Come List:");

  while (stack.length > 0) {
    const vertex = stack.pop();
    console.log(vertex); // Now Node Come

    for (const neighbor of graph.adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
}

function dfsRecursive(graph, vertex, visited = new Set()) {
  visited.add(vertex);
  console.log(vertex); // Now coming Node

  for (const neighbor of graph.adjacencyList[vertex]) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited);
    }
  }
}

const graph = new GraphData();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");

// BFS 실행
bfs(graph, "A");

// DFS 실행 (stack 사용)
console.log("DFS (Recursive) Come List");
dfsRecursive(graph, "A");

---

 

GitHub - Koras02/javascript-algorithm