[자료구조] 그래프에 대해

그래프

그래프(graph)란 각각의 단위 정보를 링크로 연결하여 구조화시킨 비선형 자료 구조로서 무방향 그래프, 방향 그래프, 완전 그래프

가 있다. 일반적으로 그래프라고 하면 보통 무방향 그래프를 의미하는 것 같다.

용어 

정점(vertex) : 노드들의 집합

간선(edge) : 정점들 사이의 상호 연결의 집합 이 있다.

그래프의 표현법 

- 인접 행렬 

배열을 사용하여 그래프를 표현한 것이다.

- 인접 리스트

포인터 형 변수를 사용하여 그래프를 표현한 것이다. 

헤드 노드 , 정점 링크를 사용한다.

그래프의 순회 알고리즘

그래프의 모든 정점을 체계적으로 방문하는 것으로 무방향 그래프의 순회 방법은 깊이 우선 탐색과 너비 우선 탐색이 있다.

- 깊이 우선 탐색(DFS)

정점을 방문할 때 갈수 있는 데까지 우선 가다가 더 이상 진행할 수 없으면 거슬러 올라가면서 아직 가보지 않은 노드가 있으면 그 노드를 따라갈 수 있는 데까지 가보는 방법이다. 이 방법은 스택을 사용한다.

-너비 우선 탐색(BFS)

우선 가깝게 인접한 정점을 모두 방문한 후 그 다음으로 가깝게 인접한 정점을 방문 하는 순으로 진행한다.

이 방법은 큐를 사용합니다.

나무(Tree)

나무란 비선형 구조로 노드와 가지로 연결된 그래프의 특수한 형태로 계층구조를 이룹니다.

트리의 기본 용어 

- 노드 : 나무 각각의 알파벳 부분에 해당하는 것

-근 노드 : 나무의 맨 위에 있는 노드

-부모 노드 : 노드에 연결된 이전 레벨의 노드

-자식 노드 : 노드에 연결된 다음 레벨의 노드

-형제 노드 : 동일한 부모를 갖는 노드

-노드의 차수 : 노드의 서브 나무 수 또는 노드의 가짓수

- 나무의 차수 : 노드들의 차수 중에서 가장 많은 수

- 깊이 : 나무에서 노드가 가질 수 있는 최대의 레벨 값

- 레벨 : 루트 노드의 레벨을 1로 가정했을 때 각 노드들이 속해 있는 깊이.