[WEEK03] 그래프의 종류와 표현 방식

그래프의 정의

그래프(Graph)는 Vertex(=Node)로 이루어진 집합 V와 Edge(또는 Arc)으로 이루어진 집합이다.

• 정점(Vertex, Node) A와 B는 간선(Edge) e에 의해 연결되어 있다.
  • A와 B는 서로 인접하다(adjacent).
  • e는 A와 B에 결합되어 있다(incident on).
• 간선 e 외에도, A와 B는 호(Arc) a에 의해 연결되어 있다.
• C는 다른 정점들과 연결되어 있지 않아 고립되어 있다(Isolated).

그래프의 종류

① 무방향 그래프(Undirected Graph)

• 간선(Edge)에 방향이 없는 그래프
• 정점 A와 B가 연결되었다면, A→B 와 B→A가 동일
• 예: 친구 관계 네트워크

② 방향 그래프(Directed Graph, Digraph)

• 간선(Edge)에 방향이 있는 그래프
• A→B와 B→A가 다름
• 예: 팔로우 관계(SNS), 웹페이지 링크

③ 가중 그래프(Weighted Graph)

• 간선에 가중치(Weight)가 부여된 그래프
• 거리, 비용, 시간 등의 개념을 표현 가능
• 예: 도로망, 네트워크 흐름

---

그래프의 표현 방식

① 인접 행렬(Adjacency Matrix)

• N×N 크기의 2차원 배열 사용 (N은 정점 개수)
• 행렬의 값:
  • 무방향 그래프: A[i][j]=1 (연결됨), 0 (연결되지 않음)
  • 방향 그래프: A[i][j]=1 (방향 있음), 0 (없음)
  • 가중 그래프: A[i][j]= 가중치 값
• 장점: 구현이 간단하고, 간선 존재 여부를 O(1)에 확인 가능
• 단점: 공간복잡도가 O(N²)로 크며, 희소 그래프(Sparse Graph)에 비효율적

② 인접 리스트(Adjacency List)

• 리스트(또는 해시맵)로 각 정점이 연결된 노드를 저장
• 예: { A: [B, C], B: [A, D], C: [A], D: [B] }
• 장점: 공간 효율적 (O(N+E)), 연결된 정점만 저장
• 단점: 간선 존재 여부 확인이 O(N)으로 느릴 수 있음

---

💻 코드 구현

1️⃣ 인접 행렬 (Adjacency Matrix) 구현

• 2차원 리스트를 사용하여 그래프를 표현
• 간선이 있으면 1 (또는 가중치 값), 없으면 0

# 정점 개수
n = 4  

# 0으로 초기화된 n x n 행렬 생성
graph = [[0] * n for _ in range(n)]  

# 간선 추가 (무방향)
graph[0][1] = 1
graph[1][0] = 1
graph[1][2] = 1
graph[2][1] = 1
graph[2][3] = 1
graph[3][2] = 1

# 그래프 출력
for row in graph:
    print(row)

 

🔹 특징:

• 공간 복잡도: O(N²)
• 노드 연결 여부 확인: O(1)
• 모든 간선 탐색: O(N²) (비효율적)

2️⃣ 인접 리스트 (Adjacency List) 구현

• 딕셔너리 또는 리스트의 리스트를 사용
• 각 정점이 인접한 정점 목록을 저장

# 인접 리스트 방식
graph = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2]
}

# 그래프 출력
for node, neighbors in graph.items():
    print(f"{node}: {neighbors}")

 

🔹 특징:

• 공간 복잡도: O(N + E) (필요한 만큼만 저장)
• 노드 연결 여부 확인: O(N)
• 모든 간선 탐색: O(N + E) (효율적)

3️⃣ 가중 그래프 (Weighted Graph)

• 딕셔너리 또는 튜플 활용

# 인접 리스트 방식 (가중치 포함)
graph = {
    0: [(1, 10), (2, 5)],  # (노드, 가중치)
    1: [(2, 2)],
    2: [(3, 1)],
    3: []
}

# 그래프 출력
for node, edges in graph.items():
    print(f"{node}: {edges}")