Graph

그래프란?

연결되어 있는 정점과 정점 간의 관계를 표현할 수 있는 자료구조로, 노드와 간선으로 구성된다.

• 노드(정점, Vertex): 연결 관계를 가진 각 데이터
• 간선(Edge): 노드 간의 관계를 표시한 선
• 인접노드(Adjacent Node): 간선으로 직접 연결된 노드

비선형 구조 vs 선형구조

• 선형 구조: 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있다. (예: 배열, 스택, 큐)
• 비선형 구조: 자료 간의 연결 관계 표현에 초점이 맞춰져 있다.
• 그래프는 비선형 구조로, 노드와 간선으로 연결 관계를 표현한다.

손흥민 - 시몬스
         ⎜       
       쿠두스 - 무아니
       
- 시몬스는 연결 관계를 가진 노드이다.
- 시몬스는 손흥민과 간선으로 연결되어 있다. 
- 시몬스와 쿠두스는 인접노드이다.

유방향 그래프 vs 무방향 그래프

• 유방향 그래프(Directed Graph): 방향이 있는 간선을 가지며, 간선은 단방향 관계를 나타낸다.
• 무방향 그래프(Undirected Graph): 방향이 없는 간선을 가지며, 양쪽 노드가 서로 연결되어 있다.

그래프를 표현하는 방법

그래프는 다음 2가지로 표현이 가능하다.

1) 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현

손흥민(0) - 시몬스(1)
             ⎜       
          쿠두스(2) - 무아니(3)


|   | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | X | O | X | X |
| 1 | O | X | O | X |
| 2 | X | O | X | O |
| 3 | X | X | O | X |


graph = [

	[False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
    
]

# 0번과 1번이 연결되었는지 확인
- graph[0][1]  # True
- 시간 복잡도: O(1)
- 공간 복잡도: O(n²)

2) 인접 리스트: Linked List로 그래프의 연결 관계를 표현

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

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

# 0과 1번이 연결되었는지 확인
# graph[0]에 있는 리스트를 다 돌아봐야 한다.
- 시간 복잡도: O(n)
- 공간 복잡도: O(n + m)

두 방식의 가장 큰 차이는 시간 복잡도와 공간 복잡도이다.

• 인접 행렬: 원하는 연결 관계를 바로 인덱스로 접근할 수 있어 O(1)의 시간 복잡도를 가진다. 그러나 노드 수 n에 따라 이차원 배열을 만들어야 하므로 공간 복잡도는 O(n²).

• 인접 리스트: 리스트를 전부 검색해야 하므로 시간 복잡도는 O(n). 대신 노드 수 n과 간선 수 m에 따라 필요한 공간만 차지하므로 공간 복잡도는 O(n + m).