Graph

1. 정의

• 어떤 데이터 사이의 인접한 정보를 저장하는 자료구조
• object와 relationship이 존재
• object는 어떤 사람 혹은 어떤 도시가 될 수 있으며
• 이러한 object를 노드라고 부르는 graph가 존재
• 그리고 이들 사이의 relationship을 graph에 저장함
• relationship을 연결하는 선을 edge
• 예: 친구 관계, 도시 관계, 지하철 노선도, 컴퓨터 네트워크등.
  

2. Graph Data Type

• Graph G의 두 가지 구성 요소
  • V(G): G에 포함된 vertex(정점)들의 집합
  • E(G): G에 포함된 edge(간선)들의 집합
  • G = (V,E)라고 쓰기도 함
• undirected graph(무방향성 그래프)
  • Vertex의 쌍을 나타내는 edge가 방향선이 없음
  • (u,v), (v,u): 동일한 edge를 표현
• directed graph(방향성 그래프)
  • 각 edge에 방향성이 존재하는 grpah
  • <u,v>: u => v인 edge를 표현
    • u = tail, v = head

3. Graph의 예

4. Graph에서 사용되는 용어들

• complete graph(완전 그래프)
  • edge의 수가 최대인 그래프
  • n개의 vertex -> 최대 edge 수 = n(n-1)/2
    
• subgraph(부분 그래프)
  • $V(G') \in V(G)$ and $E(G') \in E(G)$일 경우, G'는 G의 부분 그래프
    
• Vertex u에서 v까지의 경로
  • graph의 에지를 통하여 두 정점을 연결하는 경로
  • 예: 1부터 3까지의 경로 = (1,3)(1,0,3)(1,2,3)
  • 경로의 길이 = 경로 상에 있는 edge의 수
  • 단순 경로: 처음과 마지막을 제외한 vertex가 다른 경로
  • cycle: 처음과 마지막이 동일한 단순 경로
  • connected(연결)
    • Vertex u와 v 사이에 경로가 존재할 경우, u와 v는 연결
    • 방향성 그래프: strongly connected
  • connected component(연결 요소)
    • maximal connected subgraph
    • 방향성 그래프: strongly connected component
  • tree = Connected acyclic graph
  • Vertex v의 차수
    • v에 연결된 edge의 수
    • 방향성 그래프
      • in-degree = v가 head가 되는 edge의 수
      • out-degree = v가 tail이 되는 edge의 수
    • Digraph = Directed Graph의 준말

5. Graph의 표현

• 두 가지 방법
  • Adjacency Matrix(인접 행렬)
  • Adjacency List(인접 리스트)

6. Adjacency Matrix(인접 행렬)

• 2차원 행렬료 graph를 표현
  • 정점이 n개일 경우: A[n][n]
    • $(u,v) \in E(g)$, A[u][v] = 1
    • otherwise, A[u][v] = 0
  • 무방향성 graph: A[][]는 대칭 행렬
  • 방향성 graph: A[][]는 비대칭 행렬
    

7. Adjacency List(인접 리스트)

• 인접 행령의 n행들을 n개의 연결 리스트로 표현
  • 즉, graph G의 각 vertex에 대해 1개의 연결리스트가 존재
    

8. Graph 표현 방법들의 분석

• G에 존재하는 edge 수? 혹은 G가 연결되었는지 검사.
  • 인접행렬: n(n-1)/2 개의 항을 조사 => O(n^2)
  • 인접리스트: O(n+e)
    • Good if e << n^2/2(sparse graphs)
• Digraph에서 vertex의 in-degree를 조사
  • 인접 행렬: O(n)
  • 인접 리스트: O(n+e)
    - 역인접 리스트(inverse adjacency list)를 별도 유지
    

참고

• 영남대학교 자료구조
• Digtal Dynamics