그래프

WooBuntu·2020년 8월 26일
그래프자료구조자바스크립트
0

자바스크립트 자료구조

목록 보기
6/8


- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)

  • 그래프는 기본적으로 노드와 노드 간의 연결로 표현되는 자료 구조이다.
    (대부분의 자료 구조는 그래프의 하위 자료 구조 정도로 볼 수 있겠다)

  • 그래프의 예시

    • SNS

    • Location/Mapping

    • Routing

    • Visual Hierarchy

    • File System Optimizations

    • 추천 알고리즘

  • 용어

    • Vertex : 노드

    • Edge : 노드 간의 '연결'

    • 무지향성 그래프

    • 지향성 그래프

  • 그래프의 구현 방식

    1. 인접 행렬

    2. 인접 리스트

  • 인접 행렬과 인접 리스트의 시간 복잡도

    • 인접 리스트가 메모리도 덜 소모하고, 모든 edge를 순회하는데 있어서 더 빠르다.
    • 다만, 특정 edge를 찾는 것에 있어서는 인접 행렬이 더 효율적이다.

인접 리스트를 활용한 무지향성 그래프의 구현

const Graph = {
  init: function () {
    this.adjacencyList = {};
    this.length = 0;
  },
};

addVertex

const Graph = {
  // 생략
  addVertex: function (vertex) {
    if (!this.adjacencyList.hasOwnProperty(vertex)) {
      this.adjacencyList[vertex] = [];
      this.length++;
    }
  },
};

addEdge

const Graph = {
  // 생략
  addEdge: function (vertex1, vertex2) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);
    this.adjacencyList[vertex1].push(vertex2);

    // 지향성 그래프를 만들고자 한다면 아래 작업을 생략하면 된다.
    this.adjacencyList[vertex2].push(vertex1);
        
    return this.adjacencyList;
  },
};

removeEdge

const Graph = {
  // 생략
  removeEdge: function (vertex1, vertex2) {
    if (!this.adjacencyList.hasOwnProperty(vertex1)) {
      return `There's no ${vertex1}`;
    }
    if (!this.adjacencyList.hasOwnProperty(vertex2)) {
      return `There's no ${vertex2}`;
    }

    function removeHelper(v1, v2) {
      const originLength = this.adjacencyList[v1].length;
      this.adjacencyList[v1] = this.adjacencyList[v1].filter((vertex) => {
        return vertex != v2;
      });
      if (this.adjacencyList[v1].length == originLength) {
        return `There's no edge between ${v1} and ${v2}`;
      }
      if (this.adjacencyList[v1].length == 0) {
        delete this.adjacencyList[v1];
        this.length--;
      }
    }

    removeHelper.call(this, vertex1, vertex2);
    removeHelper.call(this, vertex2, vertex1);

    return this.adjacencyList;
  },
};

removeVertex

const Graph = {
  // 생략
  removeVertex: function (vertex) {
    if (!this.adjacencyList.hasOwnProperty(vertex)) {
      return `There's no ${vertex}`;
    }
    const edges = this.adjacencyList[vertex];
    edges.forEach((v) => {
      this.removeEdge(v, vertex);
    });
    return this.adjacencyList;
  },
};

그래프 순회

  • 그래프 순회의 예시

    • peer to peer networking

    • web cralwers

    • 최단 경로 탐색

      • GPS 네비게이션

      • 미로 풀기

      • AI
        (게임에서 이길 수 있는 최단 경로)

DFS

DFS(재귀문)

const Graph = {
  // 생략
  DFSbyRecursion: function (start) {
    if (this.length == 0) {
      return;
    }
    const visitedHash = {};
    const visitedList = [];

    function traverse(node) {
      visitedHash[node] = true;
      visitedList.push(node);
      if (visitedList.length == this.length) {
        return;
      }
      const neighbors = this.adjacencyList[node];
      for (let i = 0; i < neighbors.length; i++) {
        const currentNode = neighbors[i];
        debugger;
        if (!visitedHash.hasOwnProperty(currentNode)) {
          traverse.call(this, currentNode);
        }
      }
    }

    traverse.call(this, start);
    return visitedList;
  },
};

const graph = Object.create(Graph);
graph.init();

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

graph.DFSbyRecursion("A");

  • A는 visited에 반영된 상태이며, A의 이웃인 B와 C 중 B를 바라보고 있다.

  • visited에 B가 없었기에 traverse의 인자로 B를 넘겨줘, B 역시 visited에 반영시켰다.

  • 이제 B의 이웃인 A와 D중 A를 바라보고 있다.

  • 하지만 A는 이미 visited에 반영되어 있는 상태기 때문에 traverse를 호출하지 않고 넘어간다.

  • 그럼 B의 나머지 이웃인 D로 넘어가는데, D는 visited에 반영되어 있지 않다.

  • 따라서 taverse의 인자로 D를 넘겨 호출한다.

  • D가 이제 visited에 반영되었으며, D의 이웃인 B, E, F 중 B를 바라보고 있다.

  • 그러나 B는 visited에 반영되어 있으므로 그냥 넘어간다.

  • D의 다음 이웃인 E를 바라보고 있다.

  • E는 visited에 반영되어 있지 않으므로, traverse의 인자로 E를 넘겨 호출한다.

  • 이제 E가 visited에 반영되었으며, E의 이웃인 C, D, F중 C를 바라본다.

  • C가 visited에 반영되어 있지 않으므로, traverse의 인자로 C를 넘겨 호출한다.

  • C가 이제 visited에 반영되었으며, C의 이웃인 A와 E중 A를 바라본다.

  • A는 이미 visited에 반영되었으므로, 그냥 넘어간다.

  • E 또한 이미 visited에 반영되었으므로, 그냥 넘어간다.

  • 앞서 4의 초반부에서 E의 이웃 중 C에 대하여 호출한 traverse가 종료되어 콜 스택에서 사라졌다.

  • 그러니 3에서 E에 대하여 호출된 traverse는 E의 나머지 이웃인 D와 F에 대하여 마저 실행해야 한다.

  • D는 이미 visited에 반영되어 있으니 넘어간다.

  • F는 아직 visited에 반영되어 있지 않으므로, traverse의 인자로 F를 넘겨 호출한다.

  • F를 인자로 호출받은 travers가 F를 visited에 등록함으로써 재귀의 기저 조건을 충족했고, 이후로는 쌓여있던 콜스택들을 차례로 종료하는 절차만 남았다.

DFS(반복문)

const Graph = {
  // 생략
  DFSbyLoop: function (start) {
    if (this.length == 0) {
      return;
    }
    const stack = [start];
    const visitedHash = {};
    const visitedList = [];

    while (stack.length) {
      const current = stack.pop();
      if (visitedHash.hasOwnProperty(current)) {
        continue;
      }
      visitedHash[current] = true;
      visitedList.push(current);
      const neighbors = this.adjacencyList[current];
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const node = neighbors[i];
        debugger;
        if (!visitedHash.hasOwnProperty(node)) {
          stack.push(node);
        }
      }
    }
    return visitedList;
  },
};

const graph = Object.create(Graph);
graph.init();

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

graph.DFSbyLoop("A");

BFS

const Graph = {
  // 생략
  BFSbyLoop: function (start) {
    if (this.length == 0) {
      return;
    }

    const queue = [start];
    const visitedHash = {};
    const visitedList = [];

    while (visitedList.length != this.length) {
      const current = queue.shift();
      if (visitedHash.hasOwnProperty(current)) {
        continue;
      }

      visitedHash[current] = true;
      visitedList.push(current);

      const neighbors = this.adjacencyList[current];
      debugger;
      queue.push(...neighbors);
    }
    return visitedList;
  },
};

const graph = Object.create(Graph);
graph.init();

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

graph.BFSbyLoop("A");

전체 코드

const Graph = {
  init: function () {
    this.adjacencyList = {};
    this.length = 0;
  },
  addVertex: function (vertex) {
    if (!this.adjacencyList.hasOwnProperty(vertex)) {
      this.adjacencyList[vertex] = [];
      this.length++;
    }
  },
  addEdge: function (vertex1, vertex2) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);
    this.adjacencyList[vertex1].push(vertex2);

    // 지향성 그래프를 만들고자 한다면 아래 작업을 생략하면 된다.
    this.adjacencyList[vertex2].push(vertex1);

    return this.adjacencyList;
  },
  removeEdge: function (vertex1, vertex2) {
    if (!this.adjacencyList.hasOwnProperty(vertex1)) {
      return `There's no ${vertex1}`;
    }
    if (!this.adjacencyList.hasOwnProperty(vertex2)) {
      return `There's no ${vertex2}`;
    }

    function removeHelper(v1, v2) {
      const originLength = this.adjacencyList[v1].length;
      this.adjacencyList[v1] = this.adjacencyList[v1].filter((vertex) => {
        return vertex != v2;
      });
      if (this.adjacencyList[v1].length == originLength) {
        return `There's no edge between ${v1} and ${v2}`;
      }
      if (this.adjacencyList[v1].length == 0) {
        delete this.adjacencyList[v1];
        this.length--;
      }
    }

    removeHelper.call(this, vertex1, vertex2);
    removeHelper.call(this, vertex2, vertex1);

    return this.adjacencyList;
  },
  removeVertex: function (vertex) {
    if (!this.adjacencyList.hasOwnProperty(vertex)) {
      return `There's no ${vertex}`;
    }
    const edges = this.adjacencyList[vertex];
    edges.forEach((v) => {
      this.removeEdge(v, vertex);
    });
    return this.adjacencyList;
  },
  DFSbyRecursion: function (start) {
    if (this.length == 0) {
      return;
    }
    const visitedHash = {};
    const visitedList = [];

    function traverse(node) {
      visitedHash[node] = true;
      visitedList.push(node);
      if (visitedList.length == this.length) {
        return;
      }
      const neighbors = this.adjacencyList[node];
      for (let i = 0; i < neighbors.length; i++) {
        const currentNode = neighbors[i];
        debugger;
        if (!visitedHash.hasOwnProperty(currentNode)) {
          traverse.call(this, currentNode);
        }
      }
    }

    traverse.call(this, start);
    return visitedList;
  },
  DFSbyLoop: function (start) {
    if (this.length == 0) {
      return;
    }
    const stack = [start];
    const visitedHash = {};
    const visitedList = [];

    while (visitedList.length != this.length) {
      const current = stack.pop();
      if (visitedHash.hasOwnProperty(current)) {
        continue;
      }
      visitedHash[current] = true;
      visitedList.push(current);
      const neighbors = this.adjacencyList[current];

      for (let i = neighbors.length - 1; i >= 0; i--) {
        const node = neighbors[i];
        debugger;
        if (!visitedHash.hasOwnProperty(node)) {
          // 다음 반복문에서 걸러지기 때문에 굳이 필요한 조건은 아니나,
          // 걸러질 걸 알면서도 굳이 stack에 추가하는 것도 이상해서 걸어놓은 조건
          stack.push(node);
        }
      }
    }
    return visitedList;
  },
  BFSbyLoop: function (start) {
    if (this.length == 0) {
      return;
    }

    const queue = [start];
    const visitedHash = {};
    const visitedList = [];

    while (visitedList.length != this.length) {
      const current = queue.shift();
      if (visitedHash.hasOwnProperty(current)) {
        continue;
      }

      visitedHash[current] = true;
      visitedList.push(current);

      const neighbors = this.adjacencyList[current];
      debugger;
      queue.push(...neighbors);
    }
    return visitedList;
  },
};

const graph = Object.create(Graph);
graph.init();
profile
WooBuntu
이전 포스트

힙

다음 포스트

최단 경로 탐색(Dijkstra's Algorithm)

0개의 댓글