그래프의 기초와 표현

인강 듣고 정리한 내용 메모

- 그래프 G는 정점,V(vertex)와 간선,E(edge)의 집합

- 엣지에 화살표가 있느냐 없느냐를 기준으로 방향성,directed 무방향성,undirected으로 나눈다.

- 방향성 그래프에서는 A->B일때 B는 A에 인접하지만 A은 B에 인접하지 않는다 ( 무방향성은 상관 없다 )

- 차수는 vertex가 얼마나 많은 데이터가 in,out되는지를 표현할 수 있어 vertex의 중요도를 나타낼 수 있다.

- in-degree : vertex에 들어오는 간선

- out-degree  : vertex에서 나가는 간선

차수는 in+out이며 무방향 그래프에서는 in,out 상관없이 그냥 차수만 나타낸다.

- 그래프에서 'simple'이 들어가면 '겹치는 vertex가 없는'이라는 것이다

- 그래프의 cycle은 시작 vertex와 도착 vertex가 동일한 것이다.

- 무방향을 방향으로 변경하는것은 상관 없지만 방향을 무방향으로 변경하는것은 방향성이 증가한다.

- connected라는 것은 어떤 vertex 2개를 골라도 path가 존재한다라는 것이다.

- Dag은 순환하지 않는 방향성 그래프

- 포레스트는 순환하지 않는 무방향성 그래프

- 트리는 연결된 비순환 무방향성 그래프

그래프의 표현

- 우리가 보고 있는 아래와 같은 모습은 실제 데이터가 저장되는 모습이 아니라 그냥 생각하는 이미지에 불과함

- 실제로는 다음과 같이 저장됨

- 인접 리스트 : 한개의 vertex에 인접된 정점을 리스트에 모두 저장함

 - 인접 행렬 : 간선이 존재하는 경우에 1로 표시함

- 인접 행렬의 경우 무방향성 그래프는 양방향으로 간선이 존재하여 하위 삼각행렬이 상위 삼각 행렬과 대칭 된다.

상황	인접 리스트	인접 행렬
저장 공간	G가 성기면 인접리스트가 좋음	G가 촘촘하면 인접 행렬이 좋음
간선을 찾는데 걸리는 시간	O(1)	O(V)
모든 간선을 찾거나 방문하는데 걸리는 시간	O(V^2)	O(V+E)

- 가중 그래프는 간선에 숫자를 표현하여 나타낼 수 있다.