자바스크립트 12. 자료구조(Data Structure) - 그래프 (graph)

오늘은 자료구조 그래프에 대해서 기록해보자!

부산교통공사에서 제공하는 부산지하철 노선도🚇

📕그래프(Graph) 개념

그래프는 마치 지하철 노선도와 비슷한 것같다. 하나의 정점(vertex 또는 노드)에서 다른 vertex들과 연결이 되어있다. 정점은 방향성이 없을 수도 있고, 한 방향을 가질 수도 있고, 양방향을 가질 수 있다. 그리고 자기 자신을 가르키는 정점가 존재하기도 한다. 그래서 정점들의 관계를 나타내고 표현이 가능한 자료 구조이다. 트리는 부모와 자식의 관계지만, 그래프는 순환과 비순환으로 나뉜다.

방향성이 있는 그래프

방향성이 없는 그래프

---

📍그래프(Graph) 메소드

이번 코드스테이츠 스프린트에서 구현한 메소드는 총 6가지 이다.

• addNode(node) - 그래프에 노드를 추가합니다.

• addEdge(fromNode, toNode) - fromNode와 toNode사이의 간선을 추가합니다.

• removeNode(node) -  그래프에서 노드를 삭제합니다.

• removeEdge(fromNode, toNode) - fromNode와 toNode사이의 간선을 삭제합니다.

• hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재여부를 반환합니다.

• contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.

---

🖐🏻그래프(Graph) 메소드 구현에 앞서서

먼저 구현에 앞서서 주어진 스프린트의 내용에는 그래프의 노드는 객체안의 키와 값으로 노드 연결을 표현해 주었다. 이렇게 말하면 이해가 어렵다 사진을 보자!

이렇게 노드의 연결되어 있는 상태를 이런식으로 표현해서 메소드를 구현할 예정이다.

---

💻그래프(Graph) 메소드 구현

class Graph {
  constructor() {
    this.nodes = {};
  }

1. addNode(node)

- 코드스테이츠에서 이미 구현해 놓으셨다! ٩( ᐛ )و

  addNode(node) { 
    this.nodes[node] = this.nodes[node] || [];
  }

2. addEdge(fromNode, toNode)

- fromNode값을 가진 노드에는 toNode를 푸쉬해주고, 반대로 toNode를 가진 노드에게는 fromNode를 푸쉬해준다.

3. removeNode(node)

- 먼저 해당하는 노드를 삭제해주고, 해당하는 노드가 있다면, splice와 indexOf를 활용해서 해결해 주었다,

4. removeEdge(fromNode, toNode)

- addEdge와 마찬가지로 해주었고, splice와 indexOf를 활용해서 구현해 주었다.

5 .hasEdge(fromNode, toNode)

- 노드들의 fromNode들 안에 toNode가 있는지 확인해서 있으면 true, 없으면 false를 반환해주었다.

6 .contains(node)

- 해당하는 노드에 값이 있는지 확인한다. 

 

드디어 배운 자료구조는 여기로 끝.... 안녕 자료구조..... 다음에는 무엇을 기록해볼까요오오~