그래프

노드나 노드들의 연결을 모은 것

사용 예시

1. SNS
2. 위치 찾기
3. 구글 지도
4. 라우팅
5. 넷플릭스 영화추천

용어

• Vertex (정점) : 노드
• Edge(간선) : 노드 사이의 연결
• Weighted(가중)/Unweighted(비가중) : 간선에 가중치를 부여한것(최단경로를 계산할때 사용)과 안한것
• Directed(방향)/Undirected(무방향) : 간선에 방향이 표시된것(양방향,단방향)과 방향이 없는 무방향

그래프 정렬

인접 행렬

정점 사이에 간선이 있는지 체크하여 행렬을 만든다. 보통 있으면 1, 없으면 0을 사용한다.

인접 리스트

각 정점들의 간선을 리스트로 저장한다, 이때 정점이 숫자가 아니거나 숫자 사이에 큰 차이가 있을 경우 맵을 이용하여 다음과 같이 저장 할 수 있다.

비교

인접리스트가 인접 행렬에 비해 차지 하는 공간이 적다.

• 희소 그래프(정점의 개수에 비해 간선의 개수가 매우적은 그래프) : 인접 리스트
• 완전 그래프(모든 정점간에 간선이 존재하는 경우) : 인접 행렬
• 모든 간선을 순환하고 싶은 경우 : 인접 리스트
• 특정 간선이 있는지 확인하고 싶은 경우 : 인접 행렬
  

인접 리스트를 사용한 그래프 구현 (무방향 그래프)

class Graph{
  constructor(){
    this.adjaceneyList = {}
  }
}

정점 추가

1. 정점의 이름을 인접 리스트의 키로 입력하고, 값은 빈 배열로 저장한다.

addVertex(vertex){
  if(!this.adjaceneyList[vertex]) this.adjaceneyList[vertex] = []
}

간선 추가

1. 정점1, 정점2를 인자로 받는다.
2. 리스트에서 정점1에 정점2를 삽입 해주고 정점2에 정점1을 삽입해준다.

addEdge(vertex1,vertex2){
  if(this.adjaceneyList[vertex1]) this.adjaceneyList[vertex1].push(vertex2)
  if(this.adjaceneyList[vertex2]) this.adjaceneyList[vertex2].push(vertex1)
}

간선 제거

1. 정점1, 정점2를 인자로 받는다.
2. 리스트에서 정점1에 정점2를 제거 해주고 정점2에 정점1을 제거해준다.

removeEdge(vertex1,vertex2){
  if(this.adjaceneyList[vertex1]){
      this.adjaceneyList[vertex1] = this.adjaceneyList[vertex1].filter(v=> v !== vertex2)
  } 
  if(this.adjaceneyList[vertex2]){
      this.adjaceneyList[vertex2] = this.adjaceneyList[vertex2].filter(v=> v !== vertex1)
  }
}

정점 제거

1. 제거하는 정점을 인자로 받는다
2. 제거하는 정점과 연결된 모든 정점에 대해 루프를 돌며 연결된 간선을 제거 한다.
3. 모두 제거한뒤 리스트에서 정점을 제거한다.

removeVertex(vertex){
  if(this.adjaceneyList[vertex]){
      this.adjaceneyList[vertex].forEach(v=>{
          this.removeEdge(vertex,v)
      })
      delete this.adjaceneyList[vertex]
  }
}