그래프 (Graph)

용어

• 정점 : 현상이나 사물들
• 간선 : 정점들간에 관계
• 인접 정점 : 간선으로 연결된 정점 (1개의 간서으로 바로 연결된 정점)
• 차수 : 인접 정점의 개수 (6은 5, 8, 7과 인접 정점으로 연결되어 있으므로 차수가 3이다.)
• 가중치 : 한 정점에서 다른 정점으로 가는데 발생하는 비용
• 경로 : 연속된 정점, 간선으로 연결된 정점들을 순서대로 나열한 것
• 단순 경로 : 반복된 정점을 포함하지 않는 경로
• 사이클 : 처음과 마지막 정점이 같은 단순 경로 ( <-> 비사이클)

방향 / 무방향 그래프

• 방향 그래프 : 간선들이 한쪽으로 방향을 가진 그래프
  • 두 정점이 양방향으로 경로를 갖고 있을 때 강결합되었다라고 한다.
• 무방향 그래프 : 간선에 방향이 없다.

그래프를 나타내는 방법

1. 인접행렬 (adjacency matrix)

각 노드에 정수형의 배열 인덱스를 세팅한다. 그리고 정점 간 연결 상태는 2차원 배열의 값으로 표시하는데 배열[i][j] === 1 은 인덱스 i인 노드와 인덱스 j인 노드 사이 간선이 존재함을 의미하며, 그외에는 0이다.

단점 : 위 그림을 보면 0이 많은 것을 볼 수 있듯이 존재하지 않는 간선을 표시하기 위해 메모리를 많이 점유한다.

2. 인접리스트 (adjacency list)

각 정점별로 인접 정점들의 리스트를 저장하는데 이를 자료구조로 표현하는 방법은 배열, 연결리스트, 해시 맵, 딕셔너리중 택할 수 있다.

인접행렬과 달리 존재하지 않는 간선은 표현상에 나타나지 않는다.

단점 : 리스트를 만드는데 많은 비용이 발생, 정점간 간선 유무 확인을 위해 리스트를 차례로 훓어야한다.

3. 근접행렬 (Incidence Matrix)

그래프의 정점을 행으로, 간선은 열로 표시하고 두 정점간 연결 상태는 2차원 배열로 나타내는 방법이다. 배열[v][e] === 1은 정점 v가 간선 e에 근접해 있음을 의미하며 그외는 0이다.

간선이 많은 그래프에서 저장 공간과 메모리를 절약하기 위해 사용