Graph & Tree

그래프(Graph)

그래프 형 자료 구조란 노드(Node, 점)과 그 노드를 연결하는 간선(Edge, 선)을 하나로 모아놓은 구조를 일컫는다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다. 또한 그래프는 여러개의 고립된 부분 그래프(Isolated Graph)로 구성될 수 있다.

그래프의 특징

• 그래프는 네트워크 모델이다.
• 네트워크 모델이라 함은 오브젝트와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있는 데이터 베이스 모델이다. 망 모형이라고한다.
  
• 두개 이상의 경로가 가능하다.(노드들 사이에 무방향/방향 에서 양방향 경로를 가질 수 있다.
• self-loop뿐 아니라 loop/circuit 모두 가능하다.
• 루트 노드라는 개념이 없다.
• 부모, 자식 노드라는 개념이 없다.
• DFS, BFS로 순회가 이루어 진다.
• 그래프는 순환 혹은 비순환이다.
• 그래프는 크게 방향 그래프, 무방향 그래프가 있다.
• 간선의 유무는 그래프에 따라 다르다.

그래프의 종류

• 무방향 그래프(Undirected Graph)
  무방향 그래프의 간선은 양방향으로 갈 수 있다.( (A,B) 와 (B,A)는 같다.)

• 방향 그래프(Directed Graph)
  간선에 방향이 존재하는 그래프이다.( <A,B> 와 <B,A>는 다르다.)

• 가중치 그래프(Weighted Graph)
  간선에 비용이나 가중치가 할당된 그래프이다. 네트워크로 불린다.

• 연결 그래프(Connected Graph)
  무방향 그래프에 있는 모든 정점 쌍에 대해서 항상 경로가 존재하는 경우의 그래프이다. 트리가 이에 포함된다.

• 비연결 그래프(Disconnected Graph)
  무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우의 그래프이다.

• 사이클(Cycle)
  단순 경로의 시작 정점과 종료 종점이 동일한 경우의 그래프이다. 단순 경로란 경로중에서 반복되는 정점이 없는 경우를 말한다.

• 비순환 그래프(Acyclic Graph)
  사이클이 없는 그래프이다.

그래프의 구현

• 인접 리스트(Adjacency List)
  인접 리스트로 그래프를 표현하는 것이 가장 일반적인 방법이다. 모든 정점을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점을 리스트로 표현한 방식이다.
  그래프내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)인 경우에 사용된다. 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있고, 인접 리스트 전체를 조사하기 때문에 그래프에 존재하는 모든 간선의 수를 알 수 있다. 단, 정점의 리스트에 있는 노드의 수만큼 시간이 소요된다.

• 인접 행렬(Adjacency Matrix)
  인접 행렬은 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i->j 로의 간선이 있다는 뜻이다.
  그래프에 간선이 많은 밀집 그래프(Dense Graph)의 경우 사용된다. 두 정점을 연결하는 간선의 존재여부를 쉽게 알 수 있으며 정점의 차수 또한 빠르게 알 수 있다. 단, 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 순회해야한다. 또한 모든 간선의 수는 인접행렬 전체를 조사하기 때문에 오래걸린다.

그래프의 탐색

• 깊이 우선 탐색(DFS, Depth-Frist Search)
  루트 노드, 혹은 다른 임의의 노드부터 시작해 다음 분기에 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 모든 노드를 방문하고자 하는 경우에 이 방법이 선택된다.

• 너비 우선 탐색(BFS, Breath-Frist Search)
  루트 노드, 혹은 다른 임의의 노드부터 시작해 인접한 노드들을 먼저 탐색하는 방법이다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고자 할때 이 방법을 사용한다.

트리(Tree)

트리는 그래프의 한 종류인 자료구조 로써, 하나의 루트 노드를 가지며 루트노드는 0개 이상의 자식을 가지고있다. 그 자식노드 또한 0개이상의 자식노드를 가지며 이를 반복하는 자료구조이다.

트리의 용어

• Root : 루트 노드, 부모가 없는 노드이며 트리는 하나의 루트노드만을 가진다.
• Leaf Node : 리프 노드, 자식이 없는 노드이며 ‘말단 노드’, ‘잎 노드’라고 불린다.
• internal : 내부 노드, 단말 노드가 아닌 노드이다.
• Siblings : 같은 부모를 가지는 노드들을 일컫는다.
• Size : 노드의 크기, 자신을 포함한 모든 자손노드의 개수
• depth : 루트에서 어떤 특정 노드까지 도달하기까지 거치는 간선의 수
• level : 트리의 특정 깊이를 지니는 노드들
• degree : 노드의 차수, 하위 트리 개수 / 간선 수 = 각 노드가 지닌 가지의 수
• degree of tree : 트리의 최대 차수
• height : 루트 노드에서 가장 깊숙이 있는 노드의 깊이

트리의 특징

• 트리는 방향성이 있는 비순환 그래프의 한 종류이다. 즉, Cycle, self-loop, loop, Circuit이 없다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 간선은 항상 (정점의 개수 — 1)만큼을 가진다.
• 두 개의 정점사이의 경로는 한 개 뿐이다.
• 루트노드는 하나만 존재하며, 모든 자식 노드는 하나의 부모만을 가진다.