Graph & Tree

이영구·2022년 6월 23일
0

Algorithm

목록 보기
4/19
  • 구조의 범위로 보았을 때, Tree는 Graph에 포함되는 개념

    • 그래프: 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료구조, 연결된 노드 간의 관계를 표현할 수 있는 자료 구조

      • 특징:
        1. 그래프는 순환 혹은 비순환 구조를 이룸
        2. 그래프는 방향이 있는 그래프와 방향이 없는 그래프로 구분
        3. 루트 노드의 개념이 없음 / 부모 - 자식 관계라는 개념이 없음
        4. 2개 이상의 경로가 가능하다. (무방향, 방향, 양방향 가능)
        5. 그래프는 네트워크 모델이다.
    • 트리(Tree): 그래프 중에서도 특수한 케이스에 해당하는 자료 구조로, 두개의 노드 사이에 반드시 1개의 경로만을 가지며, 사이클이 존재하지 않는 방향 그래프. 부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 함

      • 특징:
        1. 부모-자식 관계가 존재해 레벨이 존재
        2. 노드가 N개면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k개
        3. 방향성이 존재하고 사이클은 존재하지 않음
        4. 트리는 pre-order, in-order, post-order 순회 존재

알고리즘 문제에서 '그래프' or '트리'라고 지칭했을 경우에는 위의 특징을 생각할 수 있어야만 문제를 쉽게 풀 수 있다.

profile
In to the code!

0개의 댓글