알고리즘 기초 - 그래프 종류/ 표현 방식

---

그래프란?

---

 

그래프(Graph)는 점과 선으로 이루어진 그림 같은 구조예요.

• 정점(Vertex, Node): 점에 해당 (사람, 도시, 컴퓨터 같은 대상).
• 간선(Edge): 점과 점을 연결하는 선 (친구 관계, 도로, 네트워크 연결).

즉, 그래프는 “무엇과 무엇이 연결되어 있는지”를 표현하는 도구예요.

 

기본 구성 요소(용어)

• 인접하다 (Adjacent): 두 점이 간선으로 직접 연결되어 있으면 인접.
• 차수(Degree): 한 점에 연결된 선의 개수. (예: 친구가 3명이면 차수=3)
• 경로(Path): 한 점에서 다른 점으로 이동할 수 있는 길.

 

---

그래프의 종류

---

 

 

- 무방향 그래프: 선에 방향이 없음 (A와 B가 친구라면 A↔B 똑같음).

 

- 방향 그래프: 선에 방향이 있음 (예: A가 B를 팔로우해도, B가 A를 팔로우하지 않을 수 있음).

 

- 가중치 그래프: 선마다 숫자(거리, 비용 등)가 붙음. (예: 지도에서 A→B까지 10km

 

 

---

그래프 표현 방식

---

그래프는 컴퓨터에서 보통 두 가지 방식으로 표현해요.

 

1) 인접 행렬 (Adjacency Matrix)

• 2차원 표(배열)로 표현.
• A와 B가 연결되어 있으면 1, 아니면 0으로 표시.
• 장점: 연결 여부 확인이 빠름.
• 단점: 공간(메모리)을 많이 차지함.

예) 

graph_matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 1],
    [0, 1, 0, 1],
    [1, 1, 1, 0]
]

2) 인접 리스트 (Adjacency List)

• 각 점마다 연결된 점들의 목록을 저장.
• 장점: 공간을 효율적으로 사용.
• 단점: 특정 연결이 있는지 확인하려면 시간이 조금 걸릴 수 있음.

예)

graph_list = {
    0: [1, 3],
    1: [0, 2, 3],
    2: [1, 3],
    3: [0, 1, 2]
}

 

 

 

 

---

마무리

---

 

 

• 그래프의 종류: 방향 유무, 가중치 유무에 따라 달라짐.
• 그래프 표현 방식: 인접 행렬(빠른 확인, 공간 낭비) vs 인접 리스트(효율적 저장).

👉 상황에 따라 어떤 방식이 더 유리할지 선택하는 것이 중요합니다!