그래프의 개념과 표현

📌 그래프의 개념과 표현

💡 그래프 소개

1. 그래프(Graph)란?
   1. 연결되어 있는 객체 간의 관계를 표현하는 자료구조
      - 지하철 노선도, SNS 친구 관계, 컴퓨터 네트워크

💡 그래프 데이터 타입

1. 그래프 G의 두가지 구성요소
   1. V(G) : G에 포함된 Vertex(정점)들의 집합
   2. E(G) : G에 포함된 Edge(간선)들의 집합

2. 무방향성 그래프(Undirected Graph)
   1. Vertex 의 쌍을 나타내는 Edge가 방향성이 없다.
   2. (u, v), (v, u) 는 동일한 Edge 를 표현하는 것이다.
      EX) 지하철 노선도

3. 방향성 그래프(Directed Graph)
   1. 각 Edge에 방향성이 존재하는 그래프
   2. (u, v) : v -> v 인 Edge를 표현하는 것이다.
      u : Tail
      v : Head

💡 그래프에서 사용되는 용어들 - 1

1. 완전 그래프(Complete Graph)
   1. Edge의 수가 최대인 그래프
   2. Vertex 의 개수가 N개 일 때, 최대 엣지 수는 N(N - 1)/2 개이다.
      각 정점마다 나머지 모든 노드들에 대해 방향성 엣지를 가질 수 있다.

2. 부분 그래프(Sub Graph)
   1. V(G') <= V(G) and E(G') <= E(G) 일 경우,
      G' 은 G의 부분그래프이다.

3. Vertex u 에서 v 까지의 경로(Path)
   * path : Edge를 몇 개나 거쳐갔는가?
   
   1. 그래프의 Edge를 통해 두 정점을 연결하는 경로이다.
      1에서 3으로 가는 경로는 다음과 같다.
      (1,3), (1,0,3), (1,0,2,3) ...

4. 경로의 길이는 경로 상에 있는 Edge의 수 와 같다.

5. 단순 경로(Simple Path)
   1. 처음과 마지막을 제외한 Vertex가 다른 경로

6. 사이클(Cycle)
   1. 처음과 마지막이 동일한 단순경로

💡 그래프에서 사용되는 용어들 - 2

1. 연결(Connected)
   1. Vertex u 와 v 사이에 경로가 존재할 경우, u와 v는 연결되어 있다고 한다.
   2. 방향성 그래프로 연결되어 있다면, "Strongly Connected"

2. 연결 요소(Connected Component)
   1. Maximal Connected Subgraph
   2. 방향성 그래프로 연결되어 있다면 "Strongly Connected Component"

3. 트리(Tree) = Connected Acyclic Graph
   - 그래프 중, 싸이클이 없는 그래프를 말한다.

4. Vertex v의 차수(Degree)
   1. v 에 연결된 Edge의 수
   2. 방향성 그래프
      • in-degree : v 가 head가 되는 edge의 수
      • out-degree : v 가 tail이 되는 edge의 수

💡 그래프의 표현

1. 두가지의 표현이 있다.
   1. 인접 행렬(Adjacency Matrix)
   2. 인접 리스트(Adjacency List)
      - 각 edge를 표현하는 방법에 따라서 구분된다.

💡 인접 행렬(Adjacency Matrix)

1. 2차원 행렬로 그래프를 표현
   1. 정점이 N개일 경우 : A[N][N]
      • (u, v)가 edge 목록에 있다면, A[u][v] = 1
      • (u, v)가 edge 목록에 없다면, A[u][v] = 0
   2. 무방향성 그래프 : A[][] 는 대칭 행렬
      A[n(n - 1)/2]로 구현가능
   3. 방향성 그래프 : A[][] 는 비대칭 행렬

💡 인접 리스트(Adjacency List)

1. 인접 행렬의 N행들을 N개의 연결 리스트로 표현한다.
   - 즉, 그래프 G의 각 Vertex에 대해 한 개의 연결 리스트가 존재하는 것이다.

💡 그래프 표현 방법들의 분석

1. G에 존재하는 Edge 의 수 혹은 G가 연결되었는지 검사한다.
   1. 인접 행렬 : n(n-1)/2 개의 항을 조사한다.
      O(n^2)
   2. 인접 리스트 : O(N + E)
      전체 Vertex 수 : N
      Edge 수 : e
      1. Good if e << n^2/2 (Sparse Graphs)
         희소 그래프 : Edge가 매우 적은 그래프

2. Digraph 에서 Vertex의 in-degree를 조사
   1. 인접 행렬 : O(N)
   2. 인접 리스트 : O(N + E)
      • 역인접 리스트(Inverse Adjacency List) 를 별도로 유지한다.
        역인접 리스트 : 들어오는 Edge에 대한 것만 표현한 리스트