[알고리즘] 그래프 Graph (1)

그래프란? 
실제 세계의 현상이나 사물을 노드 Node와 간선 Edge  로 표현하기 위해 사용하는 알고리즘으로, 네비게이션 길찾기, 게임 내 캐릭터 이동, 지식 그래프 등에 사용되며, 앞서 배웠던 트리 또한 그래프의 일종입니다. 

그래프 데이터베이스 (GDB)의 예시, 출처: t.ly/O-Zo

우리에게 익숙한 그래프의 예시로는 쾨니히스베르크의 다리 문제가 있습니다. 

출처: t.ly/WlnI

1. 용어

• 노드 Node : 위치, 정점 vertex와 같음
• 간선 Edge : 위치 간의 관계를 표시한 선, 노드를 연결한 선, link 또는 branch 와 같
• 인접 정점 Adjacent vertex : 간선으로 직접 연결된 노드를 말함
• 차수 Degree : 방향이 없는 그래프에서 하나의 노드에 연결된 노드의 갯수
• 평균 차수 average degree: 노드 개수와 간선의 개수를 비교하기 위한 값
• 진입 차수 In-degree : 방향이 있는 그래프에서 외부에서 오는 간선의 수 - 아래 그림에서 A node의 진입 차수는 2
• 진출 차수 Out-degree: 방향이 있는 그래프에서 외부로 향하는 간선의 수 - 아래 그림에서 A node의 진출 차수는 1
• 경로 Path: 간선으로 연결되어 있는 노드의 정렬
• 경로 길이 Path length: 경로에 포함된 간선의 개수, 아래 그림에서 경로 ACDF의 길이는 3

출처:t.ly/99Dh

• 단순 경로 Simple path: 경로에서 처음 노드와 끝 노드를 제외하고 중복이 없는 경우
• 사이클 Cycle: 단순 경로의 시작 노드와 끝 노드가 동일한 경우
• 루프 Loop: 자기 자신 노드를 연결하는 간선 (degenerate edge that joins a vertex to itself - 주어가 edge임) 아래 그림의 3번 노드의 간선, 단순 경로에는 루프가 없음

출처: t.ly/ecVu

2. 종류 (굵은 글씨는 자주 쓰이는 그래프)

• 무방향 그래프 undirected graph: 간선에 방향이 없는 그래프, 간선을 통해 노드는 양방향으로 이동 가능,
  표기: $(A,B) $ 또는 $ (B,A)$
• 방향 그래프 directed graph: 간선에 방향이 있는 그래프
  표기: $<A,B>$
• 가중치 그래프: 간선에 비용 혹은 가중치가 할당된 그래프
• 연결 그래프 / 비연결 그래프: 무방향 그래프에서 모든 노드에 대해 항상 경로가 존재하는 경우 / 모든 노드에 대해 경로가 존재하지는 않은 경우
• 순환 그래프 cyclic graph/ 비순환 그래프 acyclic graph: 단순 경로의 시작 노트와 종료 노드가 동일한 경우 / 동일하지 않은 경우
• 완전 그래프: 그래프의 모든 노드가 간선으로 연결되어 있는 그래프

3. 그래프와 트리의 차이

	그래프	트리
경로	한 개 이상의 경로가 있을 수 있음	노드 두개 간 한 개의 경로만 존재할 수 있음
방향성	방향성이 있는 그래프 / 없는 그래프 둘 다 존재함	방향 그래프만 존재함
사이클	사이클 가능, 순환/비순환 그래프 모두 존재	비순환 그래프, 사이클 존재 X
복잡도	상대적으로 복잡	덜 복잡
Root node	존재하지 않음	1개의 root node만 존재
Traversal techniques	Breadth-first search and depth-first search.	Pre-order, In-order and Post-order
부모/자식 관계	부모 자식 개념이 존재하지 않음	부모 자식 개념 존재
Model type	Network	Hierarchical

(영어 자료 출처:t.ly/ZK3r)

출처: t.ly/zmZQ