그래프(Graph), 트리(Tree), BFS/DFS 정리

오늘은 자료구와 알고리즘에서 자주 빈출되는 그래프, 트리, BFS, DFS에 관하여 간단하게 정리해보려고 합니다!

그래프

그래프란?

• 노드와 간선으로 구성된 자료구조로 이를 통해 연결된 노드간의 관계를 표현할 수 있다.
• 노드(node)란 정점(vertex)라고도 하며 그래프를 구성하는 기본 원소 (점)
• 간선(edge)이란 정점간의 관계로 노드를 연결하는 선

인접행렬

• 노드와 노드가 연결되어 있는지 나타내는 정사각행렬(이차원 배열)
• 장점: 구현이 쉽고 직관적이다. i와 j 노드의 연결상태를 바로 알 수 있다.
• 단점: 노드의 개수가 N이라고 하면 이 배열의 크기는 N*N이 된다. 특정 노드에 연결된 노드를 찾으려면 N번 만큼 확인해줘야한다.

인접리스트

• 노드별로 연결된 노드를 기록
• 장점: 실제로 연결된 노드의 정보만 알면 된다.
• 단점: i와 j 노드의 연결상태를 바로 알 수 없다.

가중치 - 간선마다 가지는 비용

• 1번 노드에서 출발해서 4번 노드까지 가장 적은 비용으로 이동하려면?

 

트리

• 트리는 그래프의 일종이다.

트리란?

• 사이클(cycle)이 없고 방향이 없는(양방향) 그래프

트리의 특징

• 두 점을 연결하는 경로는 유일하다

노드의 종류

• 루트노드 - 트리애서 부모가 없는 최상위 노드
• 부모노드 - 루트노드 방향으로 직접 연결된 노드
• 자식노드 - 부모노드와 반대방향으로 연결된 노드
• 형제노드 - 같은 부모를 갖는 노드들
• 리프노드 - 자식이 없는 노드들
• 레벨 - 루트노드까지 연결된 간선의 수
• 높이 - 루트노드까지 연결된 가장 긴 간선의 수
• 크기 - 연결된 노드의 갯수
• 치수 - 연결된 자식노드의 갯수
• 서브트리 - 트리안의 작은 트리(부분집합)

이진트리

• 자식 노드의 수를 최대 2개로 제한하는 가장 간단한 형태

트리의 순회

• 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)
• 전위
  • Root → Left → Right
• 중위
  • Left → Root → Right
• 후위
  • Left → Right → Root

 

BFS/DFS with 그래프

큐 = BFS

1. 큐에서 하나를 꺼낸다.
2. 연결된 노드 중 방문하지 않은 노드를 찾는다.
3. 해당노드를 방문처리하고 큐에 넣는다.
4. 큐가 빌때까지 1~3을 반복한다.

스택 = DFS

1. 스택에서 하나를 꺼낸다.
2. 연결된 노드 중 방문하지 않은 노드를 찾는다.
3. 해당노드를 방문처리하고 스택에 넣는다.
4. 스택이 빌때까지 1~2을 반복한다.

정리

• 그래프란 노드완 간선으로 구성된 자료구조이다.
• 그래프를 표현하는 방법에는 인접행렬과 인접리스트가 있다.
• 트리란 사이클(cycle)이 없고 방향이 없는(양방향) 그래프 + 유일한 경로
• 전위, 중위, 후위 선회(Root의 순서 기준)
• BFS = 큐, DFS = 스택