파이썬과 함께하는 자료구조 8장 그래프

절반정도 해서 뒤로 점프!

8. 그래프

그래프는 광범위한 분야에서 활용되는 자료구조!

여러가지 알고리즘과 탐색방법등이 존재한다.

8.1.1 그래프 용어

그래프는 기본적으로 용어에 대한 이해가 없으면 공부가 아예 안된다...

정점(vertex): 노드, 

간선(edge): 두개의 정점을 연결한 선

차수(degree): 정점 a 에 인접한 정점

무방향그래프 : 간선에 방향이 없는 것, (a, b)

방향그래프 : 간선에 방향이 있는 것 <a, b>

- 진입차수(in-degree): 정점으로 들어오는 차수

- 전출차수(out-degree): 정점에서 나가는 차수

경로(path): 시작점부터 끝정점까지의 정점들의 나열

- 단순경로(simple-path) : 경로상의 정점이 모두 다름

- 싸이클 : 시작과 끝이 같음

연결성분: 그래프 중 서로 연결되어있는 부분

가중치(weighted) : 간선에 가중치를 부여(거리, 소요시간 등)

부분그래프(subgraph): 주어진 그래프 중 일부분

- 트리 : 싸이클이 없는 그래프

- 신장트리 : 그래프의 모든 정점을 싸이클 없이 연결하는 그래프

8.1.2 그래프의 자료구조

그래프를 자료구조로 저장하기 위한 방법은 2가지가 있다

인접행렬(Adjacency Matrix)

- 행과 열을 통해 연결되면 1, 아니면 0으로 표현한다

- 만약 노드가 무수히 많을 경우 연결이 되지않은 부분을 0으로 표현하다보니

메모리? 등의 낭비가 있다고 한다. 이런 경우엔 리스트 활용

인접리스트(Adjacency List)

- 연결 된 부분을 리스트로 표현

예) 1번노드와 3번 노드가 연결되어있다면

인접행렬 : a[1][3] = 1

인접리스트 : a = [[],[3]...]

- 1번째 인덱스가 3을 뜻한다 = 1이 3을 가리킨다로 이해