🚧Intro2Algo🐨22장.기본 그래프 알고리즘 (01)그래프의 표현

$$G = (V, E)$$의미

1. G (Graph): 그래프 자체, 정점들과 그 정점들을 연결하는 간선들의 집합.
2. V (Vertices): 정점 집합. Vertex의 복수형으로, 그래프의 각 노드 또는 점.
3. E (Edges): 간선 집합. 정점들을 연결하는 선.

$G = (V, E)$는 "그래프 G는 정점들의 집합 V와 간선들의 집합 E로 구성된다"는 것을 수학적으로 표현한 것.

그래프 $G = (V, E)$를 표현하기 위해서는 두 가지 표준 방법이 있음.

1. 인접 리스트의 집합
- 작은 밀도($|E|가|V|^2$보다 훨씬 작음) 그래프에 대해 효율적(Sparse Graph $|E| \ll |V|^2$ 조건을 만족)

2. 인접 행렬

두 방법 모두 무방향 그래프에 적용할 수 있다.

무방향 그래프 정점5개 간선 7개	인접 리스트	인접 행렬
	graph = {      1: [2, 5],      2: [1, 3, 4, 5],      3: [2, 4],      4: [2, 3, 5],      5: [1, 2, 4] }	A = [ [0, 1, 0, 0, 1], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 1, 0, 1], [1, 1, 0, 1, 0] ]

정점 6개 간선 8개 방향그래프	인접 리스트	인접 행렬
	graph = {      1: [2, 4],      2: [5],      3: [6, 5],      4: [2],      5: [4]      6: [6] }	A = [     [0, 1, 0, 1, 0, 0],     [0, 0, 0, 0, 1, 0],     [0, 0, 0, 0, 1, 1],     [0, 1, 0, 0, 0, 0],     [0, 0, 0, 1, 0, 0],     [0, 0, 0, 0, 0, 1] ]

http://magjac.com/graphviz-visual-editor/

Graphviz Visual Editor

https://currygamedev.tistory.com/8

[자료구조] 그래프(Graph)