Graph

트리는 그래프의 특수한 케이스

그래프는 다양한 문제를 모델링 하는 것과 문제를 해결하기 위해 알고리즘을 고안하는데 유용


용어

vertex, vertices(vertex의 복수형): 트리의 Node와 동일개념

  • root node와 leaf node가 아닌 모든 노드

edge: 트리의 link와 동일개념

  • undirected edge ( = undirected graph)
  • directed edge ( = directed graph)
    • 단방향, 양방향
    • in-degree (해당노드로 들어오는 방향성 있는 edge), out-degree (해당노드에서 나가는 방향성 있는 edge)
  • weighted edge ( = (directed or undirected) weighted graph)
    • 서울 - 제주도 와 서울 - LA의 weight는 다름

정의1

graph G=(V,E)


V(G): empty가 없는 vertex들의 유한한 집합

  • v1, v2, ..., vi, vj, ... ∈ V(G)

E(G): empty가 가능한 유한한 edge들의 집합

  • (vi, vj) ∈ E(G) 이면 vi, vj ∈ V(G)

undirected graph

  • (vi,vj) = (vj,vi)

directed graph ordered

  • <vi,vj> ≠ <vj,vi>

집합의 표현 예시

V(G1) = {0,1,2,3}; E(G1) = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}

V(G2) = {0,1,2,3,4,5,6}; E(G2) = {(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}

V(G3) = {0,1,2}; E(G3) = {<0,1>,<1,0>,<1,2>}

예시

상세

degree (of a vertex): vertex에 인접한 edge의 수

in-degree (of a vertex v): 방향성 있는 edge가 vertex를 향하고 있는 edge의 수

out-degree (of a vertex v): 방향성 있는 edge가 vertex에서 나가고 있는 edge의 수

그래프 제한사항

vertex에 edge가 없거나 자기자신을 가리키는 edge는 없음

하나의 vertex에서 다른 vertex를 연결하는 edge가 중복인 경우는 없음 (<=> multigraph)

정의2

  • subgraph: 그래프의 한 부분

  • connected graph: 모든 vertex가 연결된 그래프

  • disconnected graph: 한개의 vertex라도 연결되어 있지 않는 그래프

  • adjacent nodes: 인접한 vertex간 연결되어 있는 node 관계

  • complete (connected) graph: 모든 vertex가 adjacent node로 표현이 가능한 그래프. 전부 연결되어 있으므로 connected graph임

예시

정의3

  • path: vertex X에서 vertex Y까지 가는 edge의 연결된 경로
    • 아래 그림에서 A에서 D까지 가는 경로는 (A,B), (B,C), (C,D) 이므로 length=3임
  • cycle: 출발한 노드 다시 도착할 수 있는 구조
    • 아래 그림에서 ABCDA는 cycle 구조
  • cyclic graph: cycle 구조가 존재하는 그래프
  • acyclic graph: cycle 구조가 존재하지 않는 구조 (=tree)

예시

그래프 표현방식

Adjacency Matrix

(n x n) 2차원 배열 - (vertex)(edge)로 표현

  • n은 그래프 안에 존재하는 노드의 개수

만약 v1가 v2가 adjacent하다면 1로 표현하고 그렇지 않으면 0으로 표현




예시

장점

공간절감

방향성이 없는 그래프일 때, 공간의 절반을 절약할 수 있음

저장할 때, 위 또는 아래의 삼각형모양의 데이터만 저장하면 됨

방향성이 없는 그래프일 때, vertex i의 degree를 구하는 공식은  임

그래프 탐색방법

그래프에서 모든 vertex를 방문하는 방법은 아래와 같음

  • depth-first traversal
  • breadth-first traversal

Depth-First Traversal

  1. 한 노드에서 더이상 새로운 인접한 노드가 없을 때까지, 인접한 노드를 재귀적으로 방문하는 방법
  2. 재귀적으로 실행한 다음, 뒤로 돌아갈 때, 다음 새로운 인접한 노드를 재귀적으로 방문
  3. 처음 시작한 노드에서의 인접한 노드를 재귀적으로 전부 방문했다면 종료

방문 순서의 방법은 preorder tree traversal 과 유사


재귀적으로 실행되는 순서는 stack을 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시


방문경로

Breadth-First Traversal

  1. 시작노드에서 인접한 노드를 한번 방문함
  2. 그 다음, 한번도 방문하지 않은 모든 인접한 노드를 방문
  3. 모든 노드를 방문했다면 종료

방문 순서의 방법은 level-order tree traversal 과 유사함

queue를 사용하여 구현하면 쉽다!

adjacent matrix로 구현한다고 하면 시간복잡도는 O(n2)임

예시

방문경로

'공부 > 자료구조' 카테고리의 다른 글

트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13

+ Recent posts