그래프의 이해와 종류

그래프의 개념

그래프는 노드(node)와 그 노드들을 연결하는 간선(Edge)을 하나로 모아 놓은 자료 구조입니다. 즉, 연결 되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조입니다. 이미 생활 속에서도 그래프 알고리즘이 적용되어 있습니다. 지도나 지하철 노선도를 확인하거나 최적의 경로를 찾아주는 데 사용한 것이 바로 그래프 알고리즘 입니다.

그래프와 트리의 차이

	그래프	트리
정의	노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조	그래프의 특별한 한 케이스('최소 연결 트리'라고도 불림), DAG(Directed Acyclic Graph. 방향성이 있는 비순환 그래프)의 한 종류
방향성	방향 그래프(Directed), 무방향 그래프(Undirected),                   가중치 그래프(Weight), 부분 그래프(Sub)	방향이 있음
사이클	사이클 가능, 자체 간선(self-loop)도 가능, 순환 그래프, 비순환 그래프 모두 존재	사이클(Cycle) 불가능. 자체 간선(self-loop_도 불가능. 비순환(Acyclic Graph) 그래프
루트/부모/자식 노드	루트/부모/자식 노드의 개념 없음	한 개의 루트 노드만이 존재, 모든 자식 노드는 한 개의 부모 노드 만을 가짐, 부모-자식 관계 있음, top-bottom 또는 bottom-top으로 이루어짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	Pre-order, In-order, Post-order가 있음. 이 세가지는 모두 DFS, BFS 안의 있음.
간선의 수	그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음	노드가 N인 트리는 항상 N-1의 간선을 가짐
경로	-	임의의 두 노드 간의 경로는 유일
예시 및 종류	지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목	이진 트리, 이진 탐색 트리. 균형 트리(AVL 트리, red-black트리), 이진 힙(최대힙, 최소힙) 등

그래프(Graph)와 과련된 용어

• 정점(vertex) : 위치라는 개념, (node 라고도 부름)
• 간선(edge) : 위치 간의 관계, 즉. 노드를 연결하는 선(link, branch라고도 부름)
• 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
• 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수(무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래                                      프의 간선 수의 2배)
• 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선의 수(내차수라고도 부름)
• 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수(외차수라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length) : 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 특징

• 그래프는 네트워크 모델입니다.
• 2개 이상의 경로가 가능합니다.
  • 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있습니다.
• self-loop 뿐 아니라 loop/circuit 모두 가능합니다.
• 루트 노드라는 개념이 없습니다.
• 부모-자식 관계가 없습니다.
• 순회는 DFS나 BFS로 이루어 집니다.
• 그래프의 순환혹은 비순환이 있습니다.
• 그래프는 크게 방향 그래프와 무방향 그래프가 있습니다.
• 간선의 유무는 그래프에 따라 다릅니다.

그래프의 종류

무방향 그래프(Undirected Graph)

• 무방향 그래프이 간선은 간선을 통해서 양방향으로 갈 수 있습니다.
• 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현합니다. ((A, B)와 (B, A)는 동일)
• EX) 양방향 통행 도로

방향 그래프(Directed Grapgh)

• 간선에 방향성이 존재하는 그래프
• A -> B로만 갈 수 있는 간선은 <A, B>로 표시(<A, B>와 <B, A>는 다름)
• EX) 일반 통행 도로

가중치 그래프

• 간선에 비용이나 가중치가 할당된 그래프
• 네트워크(Network)라고도 합니다.
• EX) 도시-도시의 연결, 도로의 길이. 회로 소자의 용량, 통신망의 사용료 등

연결 그래프

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

비연결 그래프

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

사이클 그래프

• 단순 경로의 시작 정점과 종료 지점이 동일한 경우
• 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우

비순환 그래프

• 사이클이 없는 그래프

완전 그래프

• 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 무방향 완전 그래프
• 정점 수 : n이면 간선의 수 : n*(n-1)/2