adjacency matrix
-
[Graph] 그래프의 표현 - 인접 행렬과 인접 리스트 (Adjacency Matrix, Adjacency List)알고리즘, 코딩테스트/알고리즘 개념 2023. 9. 12. 01:38
그래프(Graph) 탐색 문제를 풀기 위해서 가장 먼저 고려해야하는 것은 그 그래프를 어떻게 자료구조로 표현할지에 대한 것이다. DFS든 BFS든, 최단경로를 찾아내기 위한 다익스트라(Dijkstra)를 이용하든 일단 그래프를 프로그램으로 적절히 옮겨와야 무엇이든 해볼 수 있다. 정점 (Node 또는 Vertex) 과 간선 (Edge)으로 구성된 그래프를 자료구조로 표현하는 방법에는 인접행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List), 두가지가 있다. 각각 이름에서 알 수 있듯이 행렬(배열)을 이용해 표현하는 방법과 리스트를 이용하는 방법이다. 여기에서 말하는 '인접'은 두 노드 간 간선이 연결되어있음을 뜻한다. 그래프에서 두 노드가 간선으로 연결되어있다면 인접했다고 ..