자료구조_Graph

Graph💡

자료구조의 그래프는 아래의 그림처럼 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가지고 있다.
출처 https://yeolco.tistory.com/66

그래프는 여러개의 점들이 서로복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 한다.

Graph 실사용 예재💡

포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션 (길찾기) 등에서 사용하는 자료구조가 바로 그래프입니다. 세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있다. 세 가지 중에서 내비게이션 시스템이 어떤 방식으로 자료구조 그래프를 사용하는지 살펴보자.

서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다. 이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 한다. 대전에 살고 있는 친구 C도 B의 결혼식에 참석을 한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동을 하려고 한다.

위의 예제 에서는 3개의 정점이 존재한다: A, B, C가 사는 각각의 도시(서울, 부산, 대전)를 그래프의 정점으로 삼을 수 있다. 그리고 이 3개의 정점은 서로 이어지는 간선(관계)을 가지고 있다.

let isConnected = {
seoul: {
  busan: true,
  daejeon: true
},
daejeon: {
  seoul: true,
  busan: true
},
busan: {
  seoul: true,
  daejeon: true
}
}

console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true