Graph (그래프) / Tree (트리)

thang_velog·2023년 3월 20일
0
post-thumbnail

Graph (그래프)

- 그래프의 개념

  • 노드(N, Node) 와 그 노드를 연결하는 간선(E, Edge)을 하나로 모아 놓은 자료구조
  • 연결되어 있는 객체 간의 관계를 표현할 수 있다
  • EX) 지하철 노선도의 최단 경로, 전기 회로의 소자들, 선수 과목 등
  • 그래프는 여러 개의 고립된 그래프로 구성될 수 있다. (Isolated Subgraphs)

- 그래프의 특징

  • 그래프는 네트워크 모델이다.
  • 2개 이상의 경로가 가능 즉, 노드들 사이에 양방항 경로가 가능하다.
  • 루트 노드라는 개념이 없다.
  • 부모-자식 관계라는 개념이 없다.
  • 순회는 DFS/BFS로 이루어진다.
  • 그래프는 순환 혹은 비순환이다.
  • 그래프는 방향 그래프와 무방향 그래프가 있다.

Tree (트리)

- 트리의 개념

  • 트리는 노드로 이루어진 자료 구조다.
    • 트리는 하나의 루트 노드를 갖는다.
    • 루트 노드를 0개 이상의 자식 노드를 갖고 있다.
    • 반복적으로 그 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
  • 각 노드(Node)들을 연결하는 선을 간선(Edge)이라고 한다.
    • 트리에는 사이클이 존재할 수 없다.
    • 각 노드는 부모 노드로의 연결이 있을 수도, 없을 수도 있다.
    • 각 노드는 어떤 자료형으로도 표현이 가능하다.
  • 비선형 자료구조로 계층적 관계를 표현한다.
  • 그래프의 한 종류이다.

- 트리의 특징

  • 그래프의 한 종류로 '최소 연결 트리' 라고도 불린다.
  • 트리는 계층 모델이다.
  • 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류(즉, 사이클이 없다)이다.
  • 노드가 N개인 트리는 항상 N-1rodml 간선을 가진다.
  • 임의의 두 노드 간의 경로는 유일하다. (두 개의 정점 사이 1개의 경로만)
  • 모든 자식 노드는 한 개의 부모 노드만을 가진다.
    • 부모-자식 관계이므로 흐름은 top-bottom or bottom-top으로 이루어짐
  • 순회는 Pre-order/In-order/Post-order로 이루어진다.
  • 트리는 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다.

0개의 댓글