자료구조 4주차_그래프

---

자료구조 4주차_그래프

---

그래프란?

비선형구조

연결 관계에 초점을 맞춤

 

            로제 - 사나
             ⎜       
      제니 - 르탄

로제, 사나, 제니, 르탄이는 연결관계를 가지는 노드(Node)

르탄이와 제니는 간선(Edge)으로 연결되어 있음

르탄이와 로제는 인접노드(Adjacent Node)

 

📌 유방향 그래프(Directed graph) : 방향이 있는 간선(단방향) 

로제 -> 사나

로제에서 사나로는 갈 수 있지만, 사나에서 로제로는 갈수 없음

 

📌 무방향 그래프(Undirected graph) : 방향이 없는 간선

로제 - 사나

로제에서 사나로 갈 수 있고 사나에서 로제로도 갈 수 있음

---

📌 인접 행렬

          2 - 3
          ⎜       
      0 - 1

1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!
  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]
]

O(노드^2) 공간을 많이 차지함 but 즉각적인 관계 파악하기 쉬움

 

📌 인접 리스트

2. 이번에는 인접 리스트로 표현해보겠습니다!
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장합니다.

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

이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

o(노드 + 간선) 공간을 적게 차지하지만, 즉각적인 연결 관계를 파악하기 어려움