Graph ( 그래프 )

✅Graph(그래프)

그래프(Graph)는 노드(Node, 정점)와 간선(Edge, 연결선)으로 이루어진 자료구조입니다. 이는 현실 세계의 관계를 모델링하는 데 많이 사용됩니다. 예를 들어,

• SNS 친구 관계 → 사람(노드)들이 친구(간선)로 연결
• 지하철 노선도 → 역(노드)들이 선(간선)으로 연결
• 지도 네비게이션 → 도시(노드)들이 도로(간선)로 연결

그래프는 탐색 알고리즘을 사용해 특정 노드를 찾거나, 최단 경로를 구할 수 있습니다. 대표적인 탐색 방법으로 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)이 있습니다.

---

1️⃣ 그래프의 기본 요소

그래프는 두 가지 주요 요소로 구성됩니다.

1. 노드(Node, 정점): 데이터를 저장하는 기본 단위입니다.
2. 간선(Edge): 노드 간의 관계를 나타내는 연결선입니다.

🔹 노드(Node)란?

위 이미지에서 둥근 원들이 노드입니다. 예를 들어, DFS, BFS 그림의 최상단 원은 루트 노드(root node)이며, 각각의 원이 하나의 노드로 작용합니다.

노드는 SNS에서 한 사람, 지하철 노선에서 하나의 역, 네트워크에서 하나의 서버를 의미할 수 있습니다.

 

🔹 간선(Edge)이란?

간선은 노드와 노드를 연결하는 선입니다.

• 양방향 간선: 서로 오고 갈 수 있는 연결 (예: 친구 관계, 무방향 그래프)
• 단방향 간선: 한쪽 방향으로만 갈 수 있는 연결 (예: 트위터 팔로우, 방향 그래프)

 

🔹 양방향 간선과 단방향 간선의 차이

• 양방향 간선 (Undirected Edge): 노드 A와 B가 연결되면 A에서 B로, B에서 A로 자유롭게 이동할 수 있습니다.
  • 예시: SNS 친구 관계 (서로 친구 추가하면 양방향 연결)
  • 예시: 지하철 노선 (두 역 사이에 왕복 가능할 때)
• 단방향 간선 (Directed Edge): A에서 B로만 이동 가능하고, B에서 A로는 갈 수 없습니다.
  • 예시: 트위터 팔로우 관계 (한 사람이 팔로우해도 상대방이 팔로우하지 않으면 단방향 연결)
  • 예시: 웹페이지 링크 (한 웹페이지에서 다른 웹페이지로 이동 가능하지만 반대 방향은 보장되지 않음)

 

🔹 노드 간의 연결이란?

노드들이 서로 연결되어 있다는 것은 어떤 규칙을 가지고 관계를 형성한다는 의미입니다. 예를 들어,

• SNS에서 두 사람이 친구라면, 서로 연결된 간선을 가짐
• 지하철 노선도에서 두 역이 직행 노선으로 연결되어 있다면, 간선으로 연결됨
• 컴퓨터 네트워크에서 서버 간 데이터 전송 경로가 있다면, 간선이 존재함

그래프에서는 이러한 연결을 통해 데이터가 이동하고, 탐색할 수 있는 경로가 결정됩니다.

노드 간의 연결은 연결 여부(0 또는 1) 또는 가중치(비용, 거리 등)를 통해 나타낼 수 있습니다.

---

2️⃣그래프 표현 방법

그래프는 두 가지 방식으로 표현할 수 있습니다.

🔹인접 행렬 (Adjacency Matrix)

• 2차원 리스트(배열)로 그래프를 표현
• 노드 개수가 N이면 N x N 크기의 행렬을 사용
• graph[i][j] = 1 → i번 노드에서 j번 노드로 갈 수 있음

✅ 예제 (무방향 그래프)

# 그래프 표현 (0번 노드, 1번 노드, 2번 노드 연결)
graph = [
    [0, 1, 1],  # 0번 노드 → 1, 2번 노드 연결
    [1, 0, 1],  # 1번 노드 → 0, 2번 노드 연결
    [1, 1, 0]   # 2번 노드 → 0, 1번 노드 연결
]

✅ 장점: 노드 간 연결 여부를 빠르게 확인 가능 (O(1))
✅ 단점: 메모리를 많이 사용 (O(N^2))

---

🔹인접 리스트 (Adjacency List)

• 연결된 노드만 저장하는 방식
• 메모리를 절약할 수 있음

✅ 예제 (위와 같은 그래프)

graph = {
    0: [1, 2],  # 0번 노드는 1, 2번과 연결
    1: [0, 2],  # 1번 노드는 0, 2번과 연결
    2: [0, 1]   # 2번 노드는 0, 1번과 연결
}

✅ 장점: 메모리 효율적 (O(N + E))
✅ 단점: 특정 노드 간 연결 여부 확인 속도가 느림 (O(N))