인접행렬과 인접리스트의 차이

졸리네요

 

항상 지하철 만석이니 피곤이 가시질 않네요.

 

뭐 어쨌든

인접행렬과 인접리스트 중 어느 것을 써야 할까요?

뭐 그냥 편한 거 쓰면 됩니다.

 

근데 차이는 한번 비교해보죠.

 

공간복잡도의 차이

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V + E)

V는 Vertex(정점)이며 E는 Edge(간선)입니다.

행렬은 정점이 10개라면 10 * 10 배열이 생기는 것이며

리스트는 정점이 10개의 그 10개의 간선이 2개라면  12개의 리스트가 생깁니다.

 

시간복잡도의 차이

간선 한개 찾기

• 인접행렬 : O(1)
• 인접리스트 : O(V)

for (int i = 0; i < V; ++i)
{
    // 인접행렬
    for (int j = 0; j < V; ++j)
    {
        if (arr[i][j])
        {
        
        }
    }
    
    // 인접리스트
    for (int j = 0; j < adj[i].size(); ++j)
    {
        if (adj[i][j])
        {
            
        }
    }
}

이렇게 보듯이 인접행렬은 바로 인덱스를 통해 접근하지만

인접리스트는 정점의 개수만큼 순차적으로 접근하게 됩니다.

 

모든 간선 찾기

• 인접 행렬의 공간복잡도 O(V^2)
• 인접 리스트의 공간복잡도 O(V + E)

 

그래서 결론이 뭐냐.

 

 

이렇게 그래프가 희소할 때는 인접리스트를 사용하는게 좋다.

이유는 벌써 정점이 8개면 인접행렬은 64공간의 배열을 만들어야 합니다.

하지만 리스트는 13개의 공간밖에 안필요하죠.

 

다만 아래처럼 조밀한 형태의 그래프라면 인접행렬이 더 좋습니다.

어차피 다 연결이 되어있고 메모리적 효율성으로 봤을 때 동일해지며, 참조 속도도 더 빠르기 때문입니다.

 

끄으으읕