그래프(Graph)

 

 

무방향 그래프를 인접 리스트로 구현한 예시.

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) => !== vertex1);
  }

  removeVertex(vertex) {
    while(this.adjacencyList[vertex].length) { // 정점이 가진 배열의 길이가 0이 될 때까지 순회
      // 리스트에서 정점을 뽑아내어 그걸 대상 정점과 함께 간선제거 함수에 넘김으로서 상호 리스트 제거.
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];  // 객체에서 속성 삭제
  }


  /* DFS : 재귀 방식 사용: 로직이 간단하지만 깊이가 깊은 그래프라면 콜스택 스택오버플로우 위험 존재*/
  depthFirstRecursive(start) {
    if(!this.adjacencyList[start]) return null;

    const result = [];
    const visited = {};
     //즉시실행함수 내에서의 this를 사용하면 depthFirstRecursitve를 가리키는 문제 때문에 여기에 선언
    const adjacencyList = this.adjacencyList;

    (function dfs(vertex) {

      visited[vertex] = true; // 해당 정점을 방문했음을 객체에 true로 표시
      result.push(vertex);  // 결과배열에 넣기

      //여기가 핵심. 해당 정점이 가진 배열의 이웃들도 재귀적으로 dfs수행. (미방문 정점만 수행)
      adjacencyList[vertex].forEach((neighbor) => {
        if(!visited[neighbor]) {
          return dfs(neighbor);
        }
      })
    })(start);

    return result;
  }

  /* DFS: 순회 방식 사용 : 스택 오버플로우의 가능성은 없지만 코드가 복잡. 대규모의 그래프에서 권장*/
  depthFirstIterative(start) {
    if(!this.adjacencyList[start]) return null;

    // 재귀 대신 스택을 사용. 시작 정점을 미리 넣고 시작
    const stack = [start];
    const result = [];
    const visited = {};
    let currenVertex;

    visited[start] = true; // 시작 노드도 방문한 걸로 여김

    while(stack.length) {
      currenVertex = stack.pop();
      result.push(currenVertex);

      this.adjacencyList[currenVertex].forEach((neighbor) => {
        if(!visited[neighbor]) {  //미방문한 노드인 경우
          visited[neighbor] = true;
          stack.push(neighbor); // 스택에 넣어줌.
          //이 과정을 통해 스택에 계속해서 새로운 원소가 들어오는 것임.
        }
      })
    }

    return result;
  }

  /* 너비우선 탐색: 하나의 정점에서 갈 수 있는 모든 정점을 확인한 뒤에야 다음 정점으로 넘어감. */
  breadthFirst(start) {
    if(!this.adjacencyList[start]) return null;

    const queue = [start];
    const visited = {};
    const result = [];
    
    let currenVertex;

    visited[start] = true;

    while (queue.length) {

      currenVertex = queue.shift(); // 여기가 핵심로직

      this.adjacencyList[currenVertex].forEach((neighbor) => {
        if(!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      })

      result.push(currenVertex);
    }

    return result;

  }


}

 

 

가중치 그래프 예시는 다익스트라 알고리즘과 함께 설명

https://catnails.tistory.com/541

다익스트라(Dijkstra) 알고리즘