[인프런|그래프(1)] 영리한 프로그래밍을 위한 알고리즘 강좌

그래프 개념과 표현

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

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

E: 노드쌍을 연결하는 에지(edge) 혹은 링크(link)

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

n=|V|, m=|E|

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

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

 

- 가중치(weighted) 그래프

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

 

 

그래프의 표현

- 인접 행렬(adjacency matrix)

- 인접리스트 (adjacency list)

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

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

2m개 edge1개당 2개가 필요 그래서 2*m개가 필요 

degree는 인접한 정점의 개수이다.

 

인접리스트는 노드의 최대 개수만큼만 소요 

인접행렬은 인덱스로 접근 가능하지만 인접노드를 찾는데 O(n) 만큼 소요

 

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

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

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

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

 ex) 1. 가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 무한대, 대각선은 0.

   2. 만약 가중치가 용량을 의미한다면 에지가 없을때 0, 대각선은 무한대

 

경로와 연결성

- 무방향 그래프 G=(V,E)에서 노드 u와 노드 v를 연결하는 경로(path)가 존재할때 v와 u는 서로 연결되어 있다.

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

- 연결요소 (connected component)