그래프

무방향 그래프(Undirected Graph)

• 간선에 방향이 없는 그래프야.
• 정점 A와 B 사이에 간선이 있으면, A에서 B로도 갈 수 있고 B에서 A로도 갈 수 있어.
• 그래프 구조 자체가 한 번 연결되면 양쪽으로 갈 수 있음을 전제로 해.

예를 들어:

A --- B

이건 A에서 B로 갈 수 있고, B에서도 A로 갈 수 있어. 하나의 간선으로 양방향 이동이 가능하다는 거야.

---

양방향 그래프(Bidirectional Graph)

• 이건 **방향 그래프(Directed Graph)**에서 양쪽으로 모두 간선이 있는 경우를 말해.
• 즉, A → B, B → A 두 개의 간선이 존재해야 해.
• 무방향 그래프처럼 보이지만, 기술적으로는 방향이 있는 간선 두 개가 존재하는 거지.

예를 들어:

A → B
B → A

이건 방향 그래프 안에서 양방향 연결이 존재하는 상황이야.

---

🔍 둘의 핵심 차이

구분	무방향 그래프	양방향 그래프 (in 방향 그래프)
간선의 개수	A-B 간선 하나	A→B, B→A 간선 두 개 필요
메모리 사용	간선 1개	간선 2개
코드 표현 방식	리스트 한 쌍에 A-B 추가	A의 리스트에 B 추가, B의 리스트에 A 추가
사용되는 곳	친구 관계, 도로 연결 (이동 가능)	네트워크 프로토콜, 메시지 왕복 등

---

💡 시각적 이해 예시

무방향 그래프:
A --- B

양방향 그래프 (방향 그래프 상의 양방향 연결):
A → B
B → A

---

그래프의 종류 및 표현 방식 시각적 이해

아래는 무방향, 방향, 가중치 그래프의 예시와 각각을 표현하는 방식(인접 행렬과 인접 리스트)을 시각적으로 나타낸 그림이야:

그림 설명

1. 그래프의 종류 (위쪽 섹션)

• Undirected Graph: 정점들이 방향 없이 연결됨. A — B는 양방향 이동 가능.
• Directed Graph: 화살표 방향에 따라 일방향 이동만 가능.
• Weighted Graph: 간선마다 숫자(가중치)가 부여되어 있음. 거리나 비용 등을 표현.

2. 표현 방식 (아래쪽 섹션)

• Adjacency Matrix: 2차원 배열 형태. [i][j]가 1이면 i → j로 간선이 있음.
• Adjacency List: 각 정점마다 연결된 정점들을 나열한 리스트 구조. 희소 그래프에 유리.

이 그림을 참고하면, 그래프의 구조와 표현 방식이 문제에 따라 어떻게 선택되어야 하는지를 더 쉽게 이해할 수 있어.

---

그래프 구성 요소: Vertex, Edge, Node, Arc

그래프는 기본적으로 "점과 선"으로 구성돼 있어. 각각의 용어를 명확히 이해하고 있어야 그래프 알고리즘을 쉽게 다룰 수 있어.

● Vertex (정점)

• 데이터를 담고 있는 기본 단위.
• 정점 하나는 하나의 노드, 개체, 상태 등을 나타냄.
• 예: 도시, 사용자, 웹페이지 등

● Node (노드)

• 일반적으로 Vertex와 같은 의미로 사용돼.
• 자료구조에서는 트리의 노드, 연결 리스트의 노드처럼 쓰이기도 하지만, 그래프에서는 Vertex ≒ Node로 생각하면 돼.

● Edge (간선)

• 두 정점을 연결하는 선.
• 간선은 방향이 있을 수도 있고(방향 그래프), 없을 수도 있어(무방향 그래프).
• 간선에는 가중치가 붙을 수도 있고 아닐 수도 있어.

● Arc (호)

• 방향이 있는 간선을 특히 Arc라고 부름.
• 즉, Arc는 A → B처럼 방향성이 있는 연결을 뜻함.
• 보통 이 용어는 **방향 그래프(Directed Graph)**에서 자주 쓰여.

정리

용어	의미 요약	예시
Vertex	데이터가 담긴 점	도시 A, 사용자 B 등
Node	Vertex와 같은 의미	정점 1, 정점 2
Edge	두 정점을 연결하는 선	A — B, 또는 A → B
Arc	방향이 있는 간선	A → B

이 용어들을 정확히 이해하면, 그래프 문제의 조건이나 표현을 해석할 때 훨씬 빠르게 구조를 파악할 수 있어.

인접 리스트 (Adjacency List)

구조

• 각 노드마다 연결된 노드들의 리스트를 따로 저장함
• 파이썬에서는 보통 리스트의 리스트(list of lists) 또는 딕셔너리의 리스트(defaultdict(list)) 형태로 구현

graph = [
  [],         # 0번 노드 (사용 안함)
  [2, 5],     # 1번 노드는 2번, 5번과 연결
  [1],        # 2번 노드는 1번과 연결
  [4],        # 3번 노드는 4번과 연결
  [3, 6],     # 4번 노드는 3번, 6번과 연결
  [1],        # 5번 노드는 1번과 연결
  [4]         # 6번 노드는 4번과 연결
]

특징

• 연결된 간선만 저장하기 때문에 공간 효율성 높음
• 연결 여부를 확인하려면 해당 리스트를 탐색해야 함 → O(degree of node)

---

인접 행렬 (Adjacency Matrix)

구조

• 2차원 배열로 노드 간 연결 정보를 저장
• matrix[i][j] = 1이면 i와 j가 연결됨, 아니면 0

graph = [
  [0, 0, 0, 0, 0, 0, 0],  # 0번 노드 (사용 안함)
  [0, 0, 1, 0, 0, 1, 0],  # 1번 노드는 2, 5와 연결
  [0, 1, 0, 0, 0, 1, 0],  # 2번 노드는 1, 5와 연결
  [0, 0, 0, 0, 1, 0, 0],  # 3번 노드는 4와 연결
  [0, 0, 0, 1, 0, 0, 1],  # 4번 노드는 3, 6과 연결
  [0, 1, 1, 0, 0, 0, 0],  # 5번 노드는 1, 2와 연결
  [0, 0, 0, 0, 1, 0, 0]   # 6번 노드는 4와 연결
]

특징

• 연결 여부 확인이 즉시 가능 (O(1))
• 간선이 적은 희소 그래프에서는 불필요하게 많은 공간을 낭비함
  • 공간 복잡도: O(N^2)
• 모든 노드 쌍을 다루는 알고리즘 (예: 플로이드 와샬)에서 유리함

---

비교 요약표

항목	인접 리스트	인접 행렬
연결 여부 확인	느림 (O(degree))	빠름 (O(1))
간선 순회	빠름 (O(간선 수))	느림 (O(N^2))
공간 효율	높음 (O(N + E))	낮음 (O(N^2))
그래프 밀도	희소 그래프에 적합	조밀 그래프에 적합
구현 난이도	약간 복잡	간단

---

※ 참고: 그래프 밀도란 간선의 수가 노드 수에 비해 얼마나 많은지를 의미한다.

• 희소 그래프: 간선 수가 노드 수에 비해 적은 경우 (ex. E ≪ N^2)
• 조밀 그래프: 간선 수가 노드 수에 비해 많은 경우 (ex. E ≈ N^2)