알고리즘 14 그래프 | Graph | JS

1. 그래프

• 개체(object)들 간의 이진관계를 표현
• 그래프는 vertex와 edge로 구성된 한정된 자료구조
• vertex는 정점, edge는 정점과 정점을 연결하는 간선
  (vertex = node, edge = link)

1-1. 그래프의 종류

• 방향 그래프: 엣지가 방향을 가짐
• 가중치 그래프: 엣지마다 가중치가 지정

1-2. 그래프의 표현

인접행렬 | adjacency matrix

인접리스트 | adjacency list

1-3. 종류 x 표현

방향 그래프의 표현

• 인접행렬은 비대칭
• 인접 리스트는 m개의 노드를 가짐

가중치 그래프의 표현

• 엣지의 존재를 나타내는 값으로 1대신 엣지의 가중치를 저장
• 엣지가 없을 때 혹은 대각선
  : 특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서
  : ex) 가중치가 거리 혹은 비용을 의미하는 경우라면 엣지가 없으면 무한, 대각선(self)은 0
  : ex) 만약 가중치가 용량을 의미한다면 엣지가 없을 때 0, 대각선(self)은 무한.

1-3. 경로와 연결성

• 무방향 그래프에서 노드와 노드를 연결하는 경로가 존재할 때, 서로 연결되어 있다고 표현함
• 모든 노드 쌍들이 서로 연결된 그래프를 연결된 그래프라고 표현함
• 연결요소(connected component)

📚 참고

YOUTUBE | 2015 봄학기 알고리즘 | 권오흠

Photo by Michael Dziedzic on Unsplash