[자료구조] Graph(그래프)

 

 

다룰 내용

• 그래프란 무엇인가?
• 그래프의 종류
• 그래프를 표현할 수 있는 방법

---

 

그래프란 무엇인가?

정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조를 의미합니다.

 

 

그래프의 종류

• 무향그래프: 간선의 방향이 없는 그래프입니다.
• 유향그래프: 간선의 방향이 있는 그래프입니다.
• 가중치 그래프: 정점에서 정점으로 이어진 간선에 가중치가 있는 그래프입니다.
• 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph): 사이클이 존재하지 않는 유향 그래프를 말합니다.
• 완전 그래프: 정점들에 대해 가능한 모든 간선들을 가진 그래프입니다.  M개의 정점을 가지는 완전 그래프는 최대 M(M - 1) / 2 간선 수를 가집니다.
• 부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프입니다.

 

가중치 그래프

완전 그래프

 

부분 그래프

 

---

 

그래프를 표현할 수 있는 방법

• 인접 행렬(Adjacent Matrix): 정점 * 정점 크기의 2차원 배열로 간선 정보를 저장하는 방법입니다.
• 인접 리스트(Adjacent List): 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장하는 방법입니다.
• 간선 리스트(Edge List): 간선을 배열이나 리스트에 저장하는 방법입니다.  최소 비용 신장 트리(MST)를 만드는 경우는 간선 정보가 입력으로 들어오는 경우가 많아서 간선 리스트로 관리하는 것이 유리한 경우가 많습니다.

 

그렇다면 어떤 방법으로 구현을 하는 것이 좋은가?

2차원 배열 형태로 들어오는 경우 인접 행렬로 그대로 사용하는 것이 데이터 변경이 없으므로 편리합니다.

 

만약 정점들의 연결 정보가 

1    2 3 5

2    1 4 5

3    2 

4    2 5

5    1 2 4

 

위와 같이 어떠한 한 정점과 연결된 다른 정점들의 리스트가 입력으로 들어온다면 인접 리스트로 관리하는 것이 편합니다.

 

만약 간선 정보가

1 2 10

2 3 20

3 5 40

 

위와 같이 정점 A, 정점 B, 가중치와 같은 방식으로 들어온다면 간선 리스트로 구성하는 것이 편합니다.

 

문제를 잘 읽고 정점의 수와 간선의 수를 고려해서 유리한 방식으로 구성을 해야합니다.

 

인접 행렬

두 정점을 연결하는 간선이 있는지 없는지 유무를 저장해서 연결 관계를 표현합니다.

결국은 정점 * 정점 정방 행렬의 모습을 보이게 됩니다.

단순하게 인접 여부만 저장한다면 boolean형 2차원 배열로, 만약 가중치를 표현할 거라면 int형 2차원 배열로 구성할 수 있습니다.

 

무향 그래프인 인접 행렬의 경우 대각선을 중심으로 대칭이 되어야 합니다. 

유향 그래프의 인접 행렬의 경우 행 i의 합 - Vi의 진출 차수를 의미하고, 열 i의 합 - Vi의 진입 차수를 의미합니다.

 

인접 행렬의 단점은?

정점 * 정점의 크기만큼 메모리를 기본적으로 사용하는데 연결 정보를 표현하는 간선 수가 많지 않은 경우 사용하는 공간보다 사용하지 않는 공간이 더 많기 때문에 공간의 낭비가 심하다는 단점이 있습니다.

 

 

인접 리스트

각 정점에 대한 인접 정점들을 순차적으로 표현합니다. 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장할 수 있습니다.

 

무향 그래프인 인접 리스트의 경우 서로의 정점에 연결 정보를 등록해주어야 합니다. 즉 입력이 a정점 b정점으로 가는 간선이 있다면 a에 b를, b에는 a를 등록해주어야 합니다. 

유향 그래프의 경우 무향 그래프처럼 두 개의 정점 모두에 등록해주지 않습니다.