Python_#10

📈 그래프

연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조.
그래프는 정점(vertex / node)들과 간선(edge)들로 이루어진 네트워크 구조.
수식으로는 G = (V, E) 로 쓰는데, V는 정점들의 집합, E는 간선들의 집합.
예시: 사람들(정점)과 친구관계(간선) → 소셜 네트워크

‼️트리를 배우면서 배웠던 "비선형 구조" ?

비선형 구조는 표현에 초점이 맞춰져 있고,
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,
비선형구조는 표현에 초점이 맞춰져 있다.

이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있다.

👉 그래프에서 사용되는 용어 정리

노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

그래프는 유방향 그래프와 무방향 그래프 두가지가 있지만,
이번 강의에서는 무방향 그래프에 대해서만 배워보도록 하겠습니다!

📊 그래프 종류

• 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다.A → B는 B → A와 다름.
  간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.
• 무방향 그래프(Undirected Graph)는 방향이 없는 간선을 갖는다.A — B는 B — A와 동일.
  

📊 그래프 표현 방법

그래프라는 개념을 컴퓨터에서 표현하는 방법은 두 가지 방법이 있다!

1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

          2 - 3      4. ....  9999999
          ⎜       
      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]
]

서로연결되었는지? 확인하기 위해서 
graph[1][2] -> O(1)

얼마나 공간을 쓰냐?
O(N^2)


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

서로 연결되었는지 확인하기 위해서
graph[0] 원소들을 다 봐야합니다. 따라서 O(N)
얼마나 공간을 쓰냐?
O(N)

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

4 .... 


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

바로 시간 VS 공간

• 인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있습니다.
  그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 $O(노드^2)$ 만큼의 공간을 사용해야 한다.

• 인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다.

• 따라서 연결되었는지 여부를 알기 위해서 최대 $O(간선)$ 만큼의 시간을 사용해야 한다.
  대신 모든 조합의 연결 여부를 저장할 필요가 없으니 $O(노드 + 간선)$ 만큼의 공간을 사용하면 된다.