[자료구조] Graph

※ 2022년 1월 27일에 작성된 글입니다.

🖇 Graph

• 연결되어 있는 객체 간의 관계를 표현하는 자료구조

Graph의 구조

• vertices(정점)
  = node
  여러 가지 특성을 가질 수 있는 객체
•  

V(G): 그래프 G의 정점들의 집합

•  
• edge(간선)
  = link
  정점들 간의 관계
•  

E(G): 그래프 G의 간선들의 집합

•  

Graph vs Tree

	Graph	Tree
방향성	방향, 무방향	방향
순환	가능	불가능
루트 노드	루트 노드의 개념이 없음	한 개의 루트 노드만 존재
부모-자식	부모-자식의 개념이 없음	부모-자식 관계
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS 안의 Pre-, In-, Post-order
간선의 수	그래프의 따라 다름	노드가 N인 트리는 항상 N-1의 간선을 가짐

Graph의 종류

• 무방향 그래프
• 방향 그래프

Graph의 경로

• 무방향 그래프의 정점 s부터 e까지의 경로
• simple path
  경로 중에서 반복되는 간선이 없는 경로
• cycle
  단순 경로의 시작 정점과 종료 정점이 동일한 경로

Graph의 차수

무방향 그래프의 차수

• 하나의 정점에 연결된 다른 정점의 수

방향 그래프의 차수

• 진입 차수(in-degree): 외부에서 가리키는 간선의 수
• 진출 차수(out-degree): 외부로 향하는 간선의 수
• 방향 그래프의 모든 진입(진출) 차수의 합 = 간선의 수

Weighted Graph

= Network

• 간선에 비용(cost)이나 가중치(weight)가 할당된 그래프

Subgraph

• 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프

Connected Graph

• 모든 정점쌍에 대하여 항상 경로가 존재하는 무방향 그래프

Complete Graph

• 모든 정점이 연결되어 있는 그래프
• n개의 정점을 가진 무방향 완전그래프의 간선의 수: n * (n - 1) / 2

Graph의 구현

adjacent matrix

• 간선(i, j)가 그래프에 존재하면 M[i][j] = 1,
  그렇지 않으면 M[i][j] = 0으로 표현한다.

0	1	1	1
1	0	1	0
1	1	0	1
1	0	1	0

adjacent list

• 각 정점에 인접한 정점들을 연결 리스트로 표현한다.

0 → 1 → 2 → 3
1 → 1 → 2
2 → 0 → 1 → 3
3 → 0 → 2