[자구] 그래프(1)

이제 마지막으로, 그래프에 대해 알아보자.

이번 장에서는 그래프란 무엇인지 알아보고 다음장에선 그래프를 이용한 알고리즘을 학습하도록 하겠다.

1. 그래프란
2. 그래프 유형
3. 그래프 데이터 메모리 저장 방법

 

---

그래프란

그래프란 데이터 간의 연결 관계를 표현한 자료구조로 정점(vertex)라 불리는 데이터를 간선(edge) 혹은 링크로 연결되어있다.

이러한 연결 관계를 갖는 데이터는 우리 일상생활에서도 쉽게 찾아볼 수 있다. 예를 들어 지하철 노선, 통신 기기, 네트워크 등이 이에 해당한다.

따라서 그래프의 개념을 이해하는 것은 매우 중요하다

 

 

1️⃣ 트리와 그래프의 차이점

앞서 공부했던 트리도 노드와 노드를 간선으로 연결했었기에 그래프의 일종이라 볼 수 있다.

그러나 트리와 그래프는 명확한 차이를 가지고 있다.

• 트리: 사이클을 형성x, 연결된 노드 간에 상하 관계 o
• 그래프: 사이클을 형성o, 연결된 노드 간에 상하 관계 x

 

---

그래프 유형

 

1️⃣ 연결/비연결 그래프

• 연결 그래프: 2개의 아무 정점이나 골라 간선으로 서로 이을 수 있다면 연결 그래프이다.
• 비연결 그래프: 어떤 정점 사이에는 경로가 존재하지 않는 그래프

 

2️⃣ 방향/무방향 그래프

• 방향 그래프: 간선에 방향이 있는 그래프
• 무방향 그래프: 방향이 없는 그래프

3️⃣ 가중치 그래프

간선에 가중치를 할당하여 연결 강도까지 나타낼 수 있는 그래프.

• 예를 들어 지하털 역을 점점, 역과 역 사이를 연결하는 경로를 간선으로 본다면 역과 역 사이의 거리를 가중치로 부여할 수 있다.
• 양수등 음수든 모두 표현 가능하다.

 

 

4️⃣ 서브 그래프

특정 그래프의 정점과 간선의 일부분으로 이루어진 그래프

 

 

 

---

그래프 데이터 메모리 저장 방법

그래프는 상하관계가 없으며 같은 그래프라도 다른 모양을 띄울 수 있다. 그럼 지금까지 설명한 그래프들은 어떻게 구현하고, 어떻게 메모리에 저장할 수 있을까?

여기에는 크게 2가지 방법이 있다. 하나는 그래프를 인접행렬로 표현하는 방법이고 또 하나는 인접리스트로 표현하는 방법이다.

 

1️⃣ 인접 행렬 기반 그래프 표현

인접행렬이란, 그래프를 NxN 크기의 행렬로 그래프를 표현하는 방법으로, 이차원 배열을 사용한다.

• N: 정점의 개수
• <행, 열> : <출발 정점, 도착 정점>
• 연결되었을때는 1, 연결이 안되었을때는 0으로 표기

< 방향 그래프 >

 

N은 4가 되기 때문에 4x4 형태의 행렬로 표현할 수 있다.

 

<무방향 그래프>

 

 

무방향 그래프는 간선에 방향이 없기 때문에 인접 행렬로 표현할 경우 항상 대칭 행렬이 된다.

 

<가중치가 있는 경우>

가중치가 있는 경우에는 0과 1로 표시하는 대신, 해당 간선의 가중치 값을 저장한다

 

2️⃣ 인접 리스트 기반 그래프 표현

인접리스트 기반 그래프 표현은 그래프의 특정 정점과 연결된 정점들을 연결 리스트로 표현한 방법이다.

 

<방향 그래프>

• 1은 2
• 2는 4
• 3은 1,2
• 4는 3을 향하고 있다 .

 

 

<무방향 그래프>

• 1 → 2, 3
• 2→ 1, 4, 3
• 3→ 1, 2, 4
• 4→2, 3

<가중치 그래프>

하나의 노드를 포현하는 정보에 가중치 정보까지 포함하면 된다.

---

이제 다음 장에서는 그래프를 이용한 알고리즘에 대해 학습하도록 하겠다.