그래프 & 트리

그래프

• 비선형 자료구조

• 관계에 특화된 자료구조

  • 정점
    • 고유하게 식별되는 객체
  • 간선
    • 정점 간의 관계

• 방향 그래프

  • 간선이 방향성을 가짐

• 무방향 그래프

  • 방향성이 없을 때.

• 가중치 그래프

  • 간선이 단순 연결 이상의 정보인 가중치를 가지는 그래프

• 인접

  • 간선으로 연결된 정점
  • 해당 간선은 연결된 정점에 부속됨.

• 차수

  • 정점에 부속되어 있는 간선의 수
  • 진입차수
    • 정점으로 들어오는 방향
  • 진출 차수
    • 정점에서 나가는 방향

• 경로

  • 한 정점에서 다른 정점까지 간선으로 연결된 정점을 순서대로 나열한 리스트

  • 경로가 있으면 정점끼리 연결되어 있음.

  • 경로 길이

    • 경로를 구성하는 간선 수

  • 단순 경로

    • 모두 다른 정점으로 구성된 경로

  • 사이클

    • 단순경로중 경로의 시작 정점과 마지막 정점이 같은 경로

  • 인접 행렬

    • N개의 정점이 있을 때, N x N 크기의 2차원 배열로 그래프 표시.
    • 배열의 원소는 간선의 가중치
    • 2차원 배열을 사용하기에 그래프에 간선이 적으면 메모리 낭비.

  • 인접 리스트

    • 각 정점에 연결된 정점의 ID만 저장하는 방식으로 그래프 표시

• 순회

  • 그래프 순회

    • 한 정점에서 시작해 그래프에 있는 모든 정점을 한 번씩 방문하는 것

    • 깊이 우선 탐색(DFS)

      • 한 방향의 경로를 깊이 탐색하고, 갈 곳이 없으면 마지막 갈림길 간선으로 되돌아와 다시 탐색
      • 스택 사용

    • 너비 우선 탐색(BFS)

      • 인접한 정점부터 방문 후, 방문했던 정점 부터 다시 인접한 정점을 방문
      • 큐 사용

최단 경로

• 가중치 그래프에서 두 정점을 연결하는 경로 중 가중치의 합이 최소인 경로

• 최단 경로를 구하기 위한 간신이 없으면 무한대 값으로 저장.

• 가중치가 음수여서는 안됨.

  • 다익스트라 알고리즘

    • 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구함

  • A* 알고리즘

  • 플로이드 알고리즘

트리 (Directed Acyling Graph)

• 계층형 자료구조
• 노드
  • 데이터가 저장된 정점
• 간선
  • 노드간 관계를 표현
• std::set, std::map, std::multiset, std::multimap
• Root 노드
  • 트리의 시작점
• 부모 - 자식 노드
  • 상위 - 하위노드를 뜻함
  • 자식이 없는 노드를 Leaf 노드라고 함
  • 같은 레벨의 노드를 Sibling 노드라고함

-조상 노드

• 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드

• 차수

  • 한 노드가 가지는 서브 트리의 수. 간선의 수.
  • 노드의 차수 중 최댓값을 트리의 차수라고 함.

• 내부 노드

  • 단말 노드를 제외한 나머지 노드

• 순회

  • 전위 순회

    • 본인을 가장 처음으로 방문하고, 나머지 자손 노드를 왼쪽부터 순회함.
    • DFS와 동일한 순서로 순회

  • 중위 순회

    • 왼쪽, 본인, 오른쪽 순으로 순회함.

  • 후위 순회

    • 왼쪽, 오른쪽, 본인 순으로 순회함.

  • 레벨 순회

    • 레벨 별로 순회함.
    • BFS와 동일한 순서로 순회.

• 이진 검색 트리

  • 한 노드를 기준으로 왼쪽 서브 트리는 모두 그 노드보다 작은 값을 가지고 있다.

  • 오른쪽 서브 트리는 모두 그 노드보다 큰 값을 가지고 있다.

  • 이진 검색 트리를 중위 순회하면 오름차순으로 정렬됨.

  • 연산

    • 트리가 균형잡혀 있다면 O(logN)
    • 편향 되어 있다면 O(N)

  • AVL트리

    • 자가 균형 이진 탐색 트리
    • 이진트리가 편향되어 있을 경우 트리를 회전시켜서 균형을 맞춤
    • 모든 경우의 연산이 O(logN)

  • 레드블랙트리

    • 자가 균형 이진 탐색 트리
    • AVL트리에서 조금 더 발전된 형태
    • STL의 트리 라이브러리, std::set, std::map, std::multiset, std::multimap는 모두 레드블랙트리로 구현되어 있음.

  • 집합

    • 유일한 데이터를 가진 자료구조.