Clolent

그래프란

정점 ( Vertex ) 과 간선 ( Edge ) 로 이루어진 자료구조의 일종으로

간선의 방향성 유무로 유향 그래프 ( Directed graph ) 와 무향 그래프 ( Undirected graph )

간선에 가중치의 존재에 따라 가중 그래프 ( Weighted graph ) 로 나뉜다.

간선의 갯수가 최대치일 경우 완전 그래프 라고도 한다. 

M = 정점의 수

N = 간선의 수

V = 노드 ( 정점 )

E = 엣지 ( 간선 )

- 그래프 G = ( V, E ) 로 이루어져 있다 ( V = Vertex / E = Edge ) 

- V는 정점으로 노드라고도 불린다.

- Incident 부속 되다 : V1과 V2를 잊는 간선은 V1, V2에 부속되어있다. ( 정점과 간선의 관계 )

- adjacent 인접 하다 : 두 정점이 간선으로 직접 연결 되어 있다. ( 정점과 정점과의 관계 )

그래프에서의 제한 

- E는 간선으로 한 간선의 양 끝에는 Vertex가 있어야 한다.

- 중복되는 간선이 없다. ( A에서 B를 잊는 간선은 1개로 유일하다 )

- Self Roop는 없다. ( 자기자신에서 출발해서 자기자신을 향하는 간선은 없다. ) 

유향 그래프

- directed graph 혹은 digraph 라고 부른다.

- M,N의 관계 = 간선의 최대 수는 M  * ( M - 1 )  개 이다. 

- G = ( V, E )

무향 그래프

- undirected graph 라고 불린다. 

- M,N의 관계 = 간선의 최대수는 M * ( M - 1 ) / 2 개 이다.

- G = ( V, E )

가중 그래프

- Weighted graph 라고 불린다. ( 유향일수도 무향일수도 있다. )

- 각 간선은 weight를 가지고 있다.

- A -> B 와 B -> A의 Weight는 다를 수 있다.

- G = ( V, E, W )

- 엣지 e에 대하여 W(e) 는 e의 weight를 반환한다. 

그래프의 구현

1. 인접 행렬

2. 인접 리스트

인접 행렬은 2차원 배열을 이용하여, 해당 노드와 노드를 연결하는 간선이 있는지 없는지를 표시해 놓은, 행렬을 사용하여 그래프를 표현하는 방법이다. 

이런 식이다.

연결이 되어 있는지를 체크하기 위해선 해당 행렬에 값을 확인하면 되므로 아주 빠르게 확인이 가능하지만, 노드가 추가되는 경우 골치아파 진다.

인접 리스트는 노드의 갯수 N 만큼의 리스트로 그래프를 표현한다. 각 정점에 대하여 점점과 연결된 간선을 한 개의 연결리스트의 저장한다. 

그 외 그래프의 용어들

1. Subgraph ( 부분 그래프 )

그래프 전체에 일부만을 때어낸 부분

2. Complete graph ( 완전 그래프 )

간선의 수가 최대치인 그래프 = 모든 정점들이 인접한 그래프 = 다 연결되어 있다는 뜻이다.

3. Adjacency relation ( 인접 관계 )

4. Path, simple path, reachable

패스 : edge의 나열( 집합 ) 어느 엣지의 끝이 다른 엣지의 시작 부분, 하나의 경로

심플 패스 : 반복이 없는 패스그래프 전체에 일부만을 때어낸 부분

reachable : 도달 가능성 ( 패스를 만들어가서 도달이 가능한지 등을 물을 때 나온다 )

5. Connected, Strongly connected

Connected : 모든 정점사이에 path가 존재 ( 무향 )

Strongly connected : 임의의 두 저점사이에 path가 존재 ( 유향 )

6. Cycle, simple cycle

Cycle : 출발과 도착이 중복 되는 부그래프

Simple cycle : 출발과 도착을 빼고는 중복이 없는 부그래프

7. Acyclic

cycle이 없음

8. Strongly Connected Component ( SCC )

Strongly connected 되어 있는 부분 그래프 ( 이 때 각 부분 그래프들은 최대 크기 )

하나의 그래프에는 여러개의 부분 그래프들이 나올 수 있다.