트리와 그래프

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

트리 - 정의

노드가 있는 트리 그림.

  • 노드 기반 자료구조
  • 각 노드는 여러 노드로 링크될 수 있음
Python으로 배우는 자료구조와 알고리즘

트리 - 용어

노드가 있는 트리 그림. 루트 노드가 노란색으로 표시됨.

Python으로 배우는 자료구조와 알고리즘

트리 - 용어

노드가 있는 트리 그림. 루트 노드는 노란색, 부모 노드는 주황색.

Python으로 배우는 자료구조와 알고리즘

트리 - 용어

노드가 있는 트리 그림. 루트 노드는 노란색, 부모 노드는 주황색, 자식은 초록색.

Python으로 배우는 자료구조와 알고리즘

트리 - 용어

노드가 있는 트리 그림.

Python으로 배우는 자료구조와 알고리즘

트리 - 용어

다양한 레벨의 노드가 표시된 트리 그림.

Python으로 배우는 자료구조와 알고리즘

트리 - 이진 트리

이진 트리의 도식.

  • 각 노드는:
    • 자식이 0개일 수 있음
    • 자식이 1개일 수 있음
    • 자식이 2개일 수 있음
Python으로 배우는 자료구조와 알고리즘

트리 - 이진 트리 구현

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

노드가 있는 트리 그림.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Python으로 배우는 자료구조와 알고리즘

트리 - 실제 활용

  • 계층적 관계 저장
    • 컴퓨터 파일 시스템
    • HTML 문서 구조

  • 체스: 상대의 가능한 수

  • 탐색·정렬 알고리즘

Python으로 배우는 자료구조와 알고리즘

그래프

노드가 있는 그래프 그림.

  • 구성:
    • 노드/정점
    • 링크/간선
  • 트리는 그래프의 한 종류
Python으로 배우는 자료구조와 알고리즘

그래프 - 유형

  • 방향 그래프:
    • 간선에 방향이 있음

방향 그래프 그림.

Python으로 배우는 자료구조와 알고리즘

그래프 - 유형

  • 무방향 그래프:
    • 간선에 방향이 없음
    • 관계는 상호적임

무방향 그래프 그림.

Python으로 배우는 자료구조와 알고리즘

그래프 - 유형

  • 가중치 그래프:
    • 간선에 수치 값이 있음
    • 방향/무방향 모두 가능

도시 이름과 거리 가중치가 있는 무방향 그래프 그림.

Python으로 배우는 자료구조와 알고리즘

그래프 vs. 트리

트리

  • 순환이 없어야 함
  • 모든 노드는 연결되어야 함

노드가 있는 트리 그림.

그래프

  • 순환이 있을 수 있음
  • 연결되지 않은 노드가 있을 수 있음

노드가 있는 그래프 그림.

Python으로 배우는 자료구조와 알고리즘

그래프 vs. 트리

트리

  • 순환이 없어야 함
  • 모든 노드는 연결되어야 함

노드가 있는 트리 그림.

그래프

  • 순환이 있을 수 있음
  • 연결되지 않은 노드가 있을 수 있음

노드가 있는 그래프 그림. 연결되지 않은 노드가 하나 있음.

Python으로 배우는 자료구조와 알고리즘

그래프 - 실제 활용 사례

  • 소셜 네트워크의 사용자 관계
    • 친구
    • 팔로우
    • 좋아요
    • 등
  • 위치와 거리
    • 경로 최적화
  • 그래프 데이터베이스
  • 탐색·정렬 알고리즘
Python으로 배우는 자료구조와 알고리즘

그래프 - 구현

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

방향 그래프 그림.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}
Python으로 배우는 자료구조와 알고리즘

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...