직대딩 블로그

오늘은 알고리즘 문제를 풀 때 정말 흔히 보이는 에 대하여 알아보겠습니다. DFS, BFS, 다익스트라, 스패닝 트리 등 정말 다양한 문제에서 등장하는 것이 그래프죠. ​ 1. 그래프란 ? 가장 기본적인 정의는 정점(Vertex)와 간선(Edge)의 집합입니다. 여기서 간선은, 두 정점을 이어주는 역할을 합니다. 자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주 다양한 형태의 그래프가 있습니다. 위의 그래프는 1,2,3,4,5,6의 총 6개의 정점으로 이루어져 있고, {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)} 의 총 7개의 간선으로 이루어져 있다고 불 수 있겠습니다. V(정점의 집합)..