4-1. 그래프와 BFS
그래프 정점(Node, Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 이때 간선은 정점간의 관계를 나타낸다. G = (V, E)로 나타낸다. 자세한 내용은 생략한다. 그래프의 표현 인접 행렬(Adjacency-matrix) 정점의 개수를 V라고 했을 때 VxV크기의 이차원 배열을 이용한다. a[i][j]는 i에서 j로 가는 간선의 존재 유무를 나타낸다.(0: 有, 1:無) 가중치를 표현하고 싶다면 0일때 간선이 없음, 1이상의 수일때 가중치로 표현할 수 있다. 인접 리스트(Adjacency-list) 리스트를 이용해서 구현한다. A[i]=i와 연결된 정점을 리스트로 표현한다. 리스트는 크기를 동적으로 변경할 수 있어야 하기 때문에, 일반적인 배열은 사용할 수 없다. 가중치를 표현할때는 리스트..
2019.05.14