[기초] 자료구조 / 그래프(Graph)의 표현과 탐색
그래프를 저장하는 방식에 대해 알아봅니다. 그래프의 표현 - 위와 같은 그래프는 정점이 6개, 간선이 8개 있다. - 간선에 방향이 없기 때문에, 방향이 없는 그래프이다. - 정점 : {1, 2, 3, 4, 5, 6} - 간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} 보통 위 그림과 같이 정점의 개수, 간선의 개수 그리고 m개의 줄에 어떤 간선이 연결되어 있는지 주어집니다. 인접 행렬(Adjacency-matrix) 정점의 개수를 V라 했을 때, V x V 크기의 이차원 배열을 이용합니다. A[i][j] = 1 (i -> j 간선이 있을 때), 0 (없을 때) 이 인접행렬은 없는 간선도 저장하기 때문에 불필요한 배열이 생겨 많..
2022. 8. 10.
