[기초 알고리즘] 그래프(기초Ⅰ)

그래프

그래프는 우리가 중학교 때부터 많이 봐오던 익숙한 것입니다.

오늘 그래프에 대해 공부를 해 볼겁니다.

그래프는 기본적으로 정점(Vertex)와 간선(Edge)로 이루어져 있어요

<그래프 G>

이때 그래프 A/B를 정점이라고 부르고 A와 B를 잇는 선을 간선이라고 부릅니다

그리고 간선에는 두 가지 종류가 있습니다.

방향이 있는 것과 방향이 없는 것

                                        

                 <An Undirected Graph>                                                   <A directed Graph>

• 방향성 그래프(Directed Graph)
  

정점(V)

V = {A, B, C, D, E, F}

간선(E)

E = {(A,B), (A,C), (B,B), (B,C), (B,D), (C,D), (D,C), (E,F)}

방향성을 가지는 그래프이기 때문에 (C, D) 와 (D, C) 간선 모두 가집니다. 

즉, 이 두 간선은 서로 다르다고 표현할 수 있습니다.

• 무방향성 그래프(An Undirected Graph)

위의 방향성 그래프와 정점은 같습니다. 하지만 간선 표현이 약간 다릅니다.

무방향성 그래프의 간선은 방향성이 없기 때문에 (A,B) 와 (B,A) 간선은 서로 같은 것입니다.