[알고리즘] 그래프1 - 그래프란?
그래프란? 그래프는 정점(노드, Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 의미이다. 위의 그림에서, V(G) = {1, 2, 3, 4, 5}이고, E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} 이다. 그래프의 종류 무방향 그래프 이름 그대로 간선에 방향이 없는 그래프이다. 그렇기 때문에 정점 v와 정점 w를 잇는 간선 (v, w)가 있다고 하면 (w, v)도 같은 간선이 되는 것이다. 그러므로 정점이 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개 이다. 방향 그래프 간선에 방향이 있는 그..
2023. 9. 21.
