[Data Structure] 인접행렬, 인접리스트

[2d3k]

그래프를 구현할 때 인접행렬과 인접리스트의 장단점?

[2d3k]

인접 행렬의 장단점

장점: 두 노드가 연결되어 있는지 확인하는 데 O(1) 시간이 소요됩니다. 그래프가 작은 경우 메모리 절약이 가능합니다. (노드의 수가 적을 때)

단점: 그래프의 크기가 큰 경우에는 많은 메모리를 소비합니다. (O(n^2) 메모리 사용) 연결된 노드의 개수를 구하는 데 O(n) 시간이 소요됩니다. (인접리스트와 비교)

---

인접 리스트의 장단점

장점: 그래프의 크기가 큰 경우에도 메모리를 효율적으로 사용할 수 있습니다. 각 노드에 연결된 노드를 탐색하는 데 필요한 시간이 O(노드의 차수)로 효율적입니다. 그래프에서 간선의 수가 적을 때 메모리를 적게 사용합니다.

단점: 두 노드가 연결되어 있는지 확인하는 데 최악의 경우 O(n) 시간이 소요됩니다. 각 노드가 갖는 차수에 따라 메모리 사용량이 증가할 수 있습니다. 따라서, 인접 행렬은 그래프의 크기가 작은 경우나 노드 간의 연결 상태를 자주 확인해야 할 때 유용하며, 인접 리스트는 그래프의 크기가 크거나 각 노드의 차수가 작은 경우에 유용합니다.

[hyeonayou]

인접 행렬과 인접 리스트는 그래프를 구현하는 데에 자주 사용되는 두 가지 방법입니다. 각각의 방법에 대한 장단점은 다음과 같습니다.

인접 행렬 (adjacency matrix)

장점: 그래프의 연결 여부를 바로 확인할 수 있어서 빠르게 처리할 수 있다. 단점: 노드의 수가 많아지면 메모리 사용량이 증가하고 빈 공간이 많아질 수 있다. 인접 리스트 (adjacency list)

장점: 메모리 사용량이 적고, 노드의 개수와 관계 없이 효율적으로 저장할 수 있다. 단점: 연결 여부를 확인하려면 순차 탐색이 필요하므로 인접 행렬에 비해 느리다. 따라서, 노드의 수가 적은 경우에는 인접 행렬을 사용하는 것이 좋고, 노드의 수가 많은 경우에는 인접 리스트를 사용하는 것이 좋습니다.