StudyData Structure

그래프 순회(Graph traversal)

그래프(Graph)

정의

  • 그래프는 객체와 객체 사이의 ‘관계’를 표현하기 위한 자료구조이다.
  • 그래프 G는 두 ‘집합’ V, E로 나타낸다.
    • V(G) : 노드(node) 혹은 정점(vertex)의 집합
    • E(G) : 정점을 잇는 에지(edge)의 집합

방향

1. 무방향 그래프(Undirected graph)

출처 : https://github.com/ythwork/CS
  • G = (V, E)
  • V(G) = {0, 1, 2, 3}
  • E(G) = {(0, 1), (1, 2), (2, 3), (1, 3)}
  • 정점의 수 : n
  • 최대 에지 수 : n(n-1)/2

2. 방향 그래프(Directed graph)

출처 : https://github.com/ythwork/CS
  • G = <V, E>
  • V(G) = {0, 1, 2}
  • E(G) = {<0, 1>, <1, 2>}
  • 정점의 수 : n
  • 최대 에지 수 : n(n-1)

특징

  • 자기 간선(self-edge)를 가질 수 없음 = (v, v)나 <v, v>를 가질 수 없음
  • 두 정점 사이에 같은 에지를 여러 개 가질 수 없음
출처 : https://github.com/ythwork/CS
  • adjacent : (u, v)가 E(G)에 속해있다면 정점 u와 v는 인접한다.
  • incident : 에지 (u, v)는 u와 v에 부속된다.
출처 : https://github.com/ythwork/CS
  • 경로(path)
    • (v1, v2), (v2, v3), (v3, v4)가 E(G)의 원소라고 할때
    • v1에서 v4까지의 정점 순서(v1 -> v2 -> v3 -> v4)
  • 경로 길이(length) : 어떤 경로에서 에지의 수
  • 어떤 경로에서 처음과 마지막을 제외하고 모든 정점이 다를 때 단순 경로(simple path)라고 한다.
출처 : https://github.com/ythwork/CS
  • 차수(degree) : 정점 v에 부속된 에지의 수 = d(v) = 3
출처 : https://github.com/ythwork/CS
  • 방향 그래프에서는 진입 차수(In-degree)와 진출 차수(Out-degree)가 존재한다.
    • 진입 차수(In-degree) : in-d(v) = 1
    • 진출 차수(Out-degree) : out-d(v) = 1
    • 차수 = 진입 차수 + 진출 차수 = d(v) = 2

부분 그래프(subgraph)와 신장 부분 그래프(spanning subgraph)

  • 부분 그래프(subgraph)

    • V(G’) ⊆ V(G’)이고 E(G’) ⊆ E(G)인 그래프 G’를 그래프 G의 부분 그래프라고 한다.

  • 신장 부분 그래프(spanning subgraph)

    • V’ = V이고 E(G’) ⊆ E(G)인 그래프 G’를 그래프 G의 신장 부분 그래프라고 한다.

그래프 표현(graph representation)

출처 : https://github.com/ythwork/CS
  • 인접 행렬(adjacency matrix)
    • 정점 u와 v에서 (u, v)가 E(G)에 속한다면 1로, 그렇지 않으면 0으로 표시한다.
    • 인접하는 모든 노드를 구하려면 v에 대해서 데이터의 개수 n개를 탐색 : O(n)
    • 인접하는 가를 검사 (u, v) : O(1)
출처 : https://github.com/ythwork/CS
  • 인접 리스트(adjacency list)
    • 인접하는 모든 노드 : O(d(v))
    • (u, v) 검사 : O(d(v))
출처 : https://github.com/ythwork/CS

그래프 순회(Graph traversal)

  • 재방문없이 그래프의 모든 정점을 방문

  • Tree traversal

    • 전위(preorder), 중위(inorder), 후위(postorder) 순회 = Stack을 이용(DFS)
    • 레벨(levelorder) 순회 = Queue를 이용(BFS)

  1. BFS(너비우선탐색, Breadth First Search) - Queue

    • 정점 v에서 시작하여 인접한 정점을 모두 방문
    • 방문한 인접 정점에 대해서 모든 인접한 정점을 방문

  2. DFS(깊이우선탐색, Depth First Search) - Stack, Recursion

    • 정점 v에서 시작하여 방문하지 않는 정점 중 한 방향으로 계속 따라감
    • 방문할 정점이 없으면 다시 돌아와서 방문하지 않는 다른 정점을 따라 계속 따라감
    • 처음 시작한 정점으로 돌아와서 더 이상 방문할 정점이 없다면 종료
Share