그래프 알고리즘(Graph)

■ (무방향) 그래프(Graph)

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)

 : 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트

m(edge 개수)

if 방향그래프라면

- 인접행렬은 비대칭

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

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

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

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

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

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

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

** 경로와 연결성

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

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

-연결요소(connected component)