[Data Structure] 그래프와 트리

그래프의 특징

• 노드와 노드를 연결하는 간선을 하나로 모아놓은 자료구조
• 방향 그래프 (Directed) 와 무방향 그래프 (Undirected) 로 나뉜다.
• 사이클 (Cycle) 이 있을 수도 있고, 자체 간선 (Self-loop) 도 있을 수 있다.
• 루트 노드, 부모-자식의 개념이 없다.
• 순회 방법은 BFS, DFS가 있다.
• 간선의 수가 제한되어있지 않다.

그래프 용어

정점 (vertex) : 위치 (node)

간선 (edge) : 위치 간의 관계. 노드를 연결하는 선 (link)

인접 정점 (adjacent vertex) : 간선에 의해 직접 연결된 정점

정점의 차수 (degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

진입 차수 (in-degree) : 방향 그래프에서 정점으로 들어오는 간선의 수

진출 차수 (out-degree) : 방향 그래프에서 정점으로 향하는 간선의 수

단순 경로 (Simple path) : 경로 중에서 반복되는 정점이 없는 경우

사이클 (Cycle) : 단순 경로의 시작 정점과 끝 정점이 동일한 경우

무향 그래프 (Undirected Graph)

• 간선을 통해서 양 방향으로 갈 수 있다. (u, v) = (v, u)
• ex) 양방향 통행 도로

유향 그래프 (Directed Graph)

• 간선에 방향성이 존재. <u, v> != <u, v>
• ex) 일방 통행 도로

완전 그래프 (Complete Graph)

• 그래프에 속한 모든 정점이 서로 연결되어 있는 그래프로, 최대 정점을 갖는다.
• n개의 vertex를 가진 무방향 그래프의 최대 정점 수 = n(n - 1) / 2
• n 개의 vertex를 가진 방향 그래프의 최대 정점 수 = n(n - 1)

가중치 그래프 (Weighted Graph)

• 간선에 비용이나 가중치가 할당된 그래프로, 네트워크라고도 한다.
• ex) 통신망 사용료

연결 그래프 (Connected Graph)

• 무방향 그래프에 있는 모든 정점쌍 사이에 항상 경로가 존재하는 그래프
• ex) 트리 (Tree) : 사이클을 갖지 않는 연결 그래프

비연결 그래프 (Unconnected Graph)

• 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프

트리의 특징

• 연결 그래프이다. 
• 방향성이 있는 비순환 그래프이다. (사이클 X, 자체 간선 X)
• 트리의 간선 개수는 반드시 정점 수 - 1이다.
• 계층 관계 (부모 - 자식 관계)이므로 1개의 루트 노드만 존재하고, 모든 자식 노드는 1개의 부모 노드만을 가진다.
• 순회 방법 : DFS, BFS, 전위 순회, 중위 순회, 후위 순회

 

 

그래프 구현 방법 (1) - 인접 리스트

• 가장 일반적인 방법으로 vector, arrayList로 구현
• 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있다.
• 모든 간선의 수를 O(N+E) 에 알 수 있다.
• 간선의 존재 여부를 알기 위해서는 정점의 차수만큼의 시간 필요

 

그래프 구현 방법 (2) - 인접 행렬

• 간선이 많은 밀집 그래프의 경우에 사용
• 두 정점을 연결하는 간선의 여부를 O(1)에 알 수 있다.
• 정점의 차수는 O(N)에 알 수 있다.
• 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 순회해야한다.
• 그래프에 존재하는 모든 간선의 수는 O(N^2)에 알 수 있다.