[기초] 자료구조 / 그래프 (Graph)

 

그래프

그래프는 일종의 자료구조이고, 정점과 간선으로 이루어져 있습니다.

 

정점은 Node, Vertex / 간선은 Edge라 하며 정점 간의 관계를 나타냅니다.

ex) G(V,E)

 

1, 2, 3이 정점이고, 그 연결하는 선은 간선

 

 

차수(Degree)

 

차수는 정점과 연결되어 있는 간선의 개수를 말합니다.

 

위 그래프에서 1, 2, 3은 각각 두 개의 간선이 연결되어 있으므로, 차수는 모두 2가 됩니다.

 

 

 

 

경로(Path)

예를 들어, 정점A에서 정점 B로 가는 경로는

 

1. A -> C -> D -> E -> B

2. A -> B

3. A -> C -> B

4. A -> C -> E -> B

 

이렇게 거쳐가는 경우가 있습니다. 이것이 바로 경로가 됩니다.

 

 

 

사이클(Cycle)

시작 정점과 도착 정점이 같으면 사이클이라 합니다.

 

예를 들어, 정점A에서 다시 정점A로 돌아오는 경로는 사이클입니다.

 

1. A -> C -> B -> A

2. A -> C -> E -> B -> A

3. A -> C -> D -> E -> B -> A

 

 

 

 

경로는 찾는 것은 매우 중요합니다.

 

 

다른 문제를 그래프로 모델링 해서 최소비용을 찾거나 경우의 수를 찾는 경우가 많습니다.

 

 

실제로 자동차 네비게이션, 지도 같은 경우를 생각해보면, 주로 빠른 길찾기를 이용하는데

 

도로를 그래프로 나타내어 최단경로를 찾게 됩니다. 

 

 

 

 

단순 경로(Simple Path)와 단순 사이클(Simple Cycle)

 

- 경로 / 사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로 / 사이클

- 특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로 / 사이클을 말한다.

 

 

 

방향 있는 그래프(Directed Graph)

A -> C와 같이 간선에 방향이 있다. A -> C는 있지만 C -> A는 없다.

 

 

방향 없는 그래프(Directed Graph)

A - C와 같이 간선에 방향이 없다. A - C는 A -> C와 C -> A를 나타낸다. 양방향 그래프 라고도 한다.

 

 

간선 여러개(Multiple Edge)

위 그림의 A-B는 연결하는 간선이 2개이다. 두 정점 사이에 간선이 여러 개일 수도 있다. 두 간선은 서로 다른 간선

 

 

루프(Loop)

간선의 양 끝 점이 같은 경우가 있다. A -> A

 

가중치(Weight)

간선에 가중치가 있는 경우, A에서 B로 이동하는데 필요한 시간, 이동하는데 필요한 비용 등등,,