개발 공부 - [그래프 알고리즘] 그래프(graph) 개념과 표현

 그래프 (Graph)

(무방향) 그래프 G = (V,E)

V : 노드 (node) 혹은 정점 (vertex)

E : 노드쌍을 연결하는 edge 혹은 link

개체들 간의 이진관계를 표현

n = |V|, m = |E|

방향 그래프와 가중치 그래프

방향그래프(Directed Graph) G = (V,E)

- 에지 (u,v)는 u로부터 v로의 방향을 가짐

가중치 그래프

- 에지마다 가중치(weight)가 지정

ㄴ 노드의 모든 에지마다 가중치라고 부르는 value를 지정해 주는 그래프이다.

    노드에다가 직접 부여하지는 않고 에지에 부여함

그래프의 표현

인접행렬(adjacency matrix), 인접리스트

인접행렬 : 근처에 있는 애부터 시작해서 모든 노드를 조회하는 방식이다.

= 연결 관계를 이차원 배열로 만들 수 있다.

n x n 배열을 a[0][0] 부터 a[n][n] 까지 정의할 수 있음.

인접리스트 (adjacency list)

정점 집합을 표현하는 하나의 배열과

각 정점마다 인접한 정점들의 연결 리스트

- 저장 공간 : O(n+m)

- 어떤 노드 v에 인접한 모든 노드 찾기 : O(degree(v)) 시간

- 어떤 에지 (u,v)가 존재하는지 검사 : O(degree(u)) 시간

참고 : https://sarah950716.tistory.com/12

방향그래프

인접행렬은 비대칭

인접 리스트는 m개의 노드를 가짐

가중치 그래프의 인접행렬 표현

- 에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장

- 에지가 없을 때 혹은 대각선:

특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서 표현

경로와 연결성

- 무방향 그래프 G= (V,E)에서 노드 u와 노드 v를 연결하는 경로(path)가

존재할 때 v와 u는 서로 연결되어 있다고 말함

모든 노드 쌍들이 서로 연결된 그래프를 연결된 그래프라고 한다 .(Connected graph)

연결 요소 (Connected component) : 노드 3개가 연결되어 있을 때 3개의 연결 요소를 가졌다고 표현한다.

참고: https://velog.io/@kjh107704/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C

아래의 그림처럼 나누어진 각각의 그래프를 연결 요소라고 한다.

즉, 노란색 덩어리 하나가 연결 요소 하나, 초록색 덩어리 하나가 연결 요소 하나를 차지하여 전체 그래프에는 연결 요소가 2개 존재하는 셈이다.