그래프 알고리즘 - 1

그래프

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

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

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

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

- n=|v|, m=|E|

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

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

- 가중치 그래프 : 에지마다 가중치가 지정

 

인접행렬

- n*n행렬 A = (aij) 연결되면 1, 안되면 0

연결리스트

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

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

 

방향그래프

- 인접행렬은 비대칭

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

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

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

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

• 특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서
• 예 : 가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 무한, 대각선은 0
• 예 : 가중치가 용량을 의미한다면 에지가 없을 때 0, 대각선은 무한

경로와 연결성

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

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

- 연결요서 (connect component)

 

* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.