트리와 그래프 내용 정리

트리와 그래프 내용 정리

트리와 그래프

그래프란?

그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.

출처 : 위키백과

그래프의 종류

무방향 그래프

간선에 방향이 존재하지 않아 양방향으로 이동이 가능하다.

(A,B), (B,A)는 동일한 간선이다

방향 그래프

간선에 방향이 존재하는 그래프로 지정된 방향으로만 이동이 가능하다.

A->B로 가는 간선은 로 표시하며 와는 다른 간선이다.

가중치 그래프

간선에 비용이나 가중치가 할당된 그래프이다.

완전 그래프

한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프

단순 그래프

두 정점 사이의 연결선이 최대 한 개인 그래프

부분 그래프

원래의 그래프에서 일부 정점이나 간선을 제거해 만든 그래프

그래프 구현 방법

그래프 구현 방법은 인접리스트 방법과 인접 행렬 방법 두 가지로 나뉜다.

인접 리스트 방법

일반적인 그래프 표현 방법

모든 정점을 인접 리스트에 저장하고, 각각의 정점에 대해 인접한 정점들을 리스트로 표현한 것이다. 구현 방식

각각의 연결리스트 헤더에 모든 정점을 하나씩 저장한다.

이때 헤더 노드들은 하나의 배열로 붙어있다.

이때 헤더 노드들은 하나의 배열로 붙어있다. 헤더에 연결되는 연결 리스트에는 해당 헤더가 저장하고 있는 노드에 인접한 노드들을 저장한다.

무방향 그래프인 경우 (a,b)는 a의 연결 리스트에 표시되고, b에도 표시해준다.

인접 행렬 방법

n x n 불린 행렬로써 matrix[i][j]가 참이라면 i->j로의 간선이 존재한다는 의미이다.

노드가 n개인 그래프를 인접행렬로 표현하면 간선 수와 무관하게 n^2의 메모리 공간이 필요하다.

인접 리스트는 어떤 노드에 대해 인접한 노드에 대해 바로 찾을 수 있지만 인접 행렬을 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회하여야 하므로 효율성이 떨어진다.

트리란?

그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

트리에는 사이클이 존재할 수 없다.

최상위 노드를 루트 노드(root node)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 트리 종류

이진트리

각 노드가 최대 두 개의 자식을 갖는 트리

이진 탐색 트리

이진트리의 속성을 만족하고 모든 노드에 대해 왼쪽 서브 트리는 해당 노드보다 작은 값이, 오른쪽 서브트리는 해당 노드보다 큰 값을 가져야 한다.

완전 이진트리

트리의 모든 높이에서 노드가 꽉 차 있는 이진트리

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 이진트리

from http://bang-tori.tistory.com/20 by ccl(A) rewrite - 2021-12-05 21:26:41