C ++의 그래프 문제에 대해 더 나은 인접 목록 또는 인접 행렬은 무엇입니까? 각각의 장점과 단점은 무엇입니까?
답변
문제에 따라 다릅니다.
- O (n ^ 2) 메모리 사용
- 두 노드 O (1) 사이에 특정 에지의 유무를 조회하고 확인하는 것이 빠릅니다.
- 모든 가장자리를 반복하는 것이 느립니다.
- 노드 추가 / 삭제 속도가 느립니다. 복잡한 연산 O (n ^ 2)
- 새로운 엣지를 추가하는 것이 빠르다 O (1)
- 메모리 사용량은 에지 수 (노드 수가 아님)에 따라 달라 지므로
인접 행렬이 희소 한 경우 많은 메모리를 절약 할 수 있습니다. - 두 노드 사이에 특정 에지의 유무를 찾는 것은
행렬 O (k)보다 약간 느립니다. 여기서 k는 이웃 노드의 수입니다. - 노드 인접 항목에 직접 액세스 할 수 있으므로 모든 에지에서 반복이 빠릅니다.
- 노드 추가 / 삭제가 빠릅니다. 행렬 표현보다 쉽습니다.
- 새로운 에지를 추가하는 것이 빠르다 O (1)
답변
언급 된 모든 것이 언어에 관계없이 데이터 구조 자체에 관한 것이기 때문에이 대답은 C ++에만 국한되지 않습니다. 그리고 내 대답은 인접 목록과 행렬의 기본 구조를 알고 있다고 가정하는 것입니다.
기억
메모리가 주요 관심사 인 경우 루프를 허용하는 간단한 그래프에 대해 다음 공식을 따를 수 있습니다.
인접성 매트릭스는 N 차지하는 2 / 8 바이트의 공간 (엔트리 당 비트).
인접 목록은 8e 공간을 차지합니다. 여기서 e는 에지 수입니다 (32 비트 컴퓨터).
그래프의 밀도를 d = e / n 2 (가장자리 수를 최대 간선 수로 나눈 값)로 정의하면 목록이 행렬보다 더 많은 메모리를 차지하는 “중단 점”을 찾을 수 있습니다.
8E> N 2 / 8 D> 1/64
따라서 이러한 숫자 (여전히 32 비트에만 해당)를 사용하면 중단 점이 1/64에 도달 합니다. 밀도 (e / n 2 )가 1/64보다 크면 메모리를 절약하려면 행렬 이 바람직합니다.
위키피디아 (인접 행렬에 대한 기사)와 다른 많은 사이트 에서 이에 대해 읽을 수 있습니다 .
참고 : 키가 정점 쌍인 해시 테이블을 사용하여 인접 행렬의 공간 효율성을 향상시킬 수 있습니다 (무 방향 전용).
반복 및 조회
인접 목록은 기존 가장자리 만 나타내는 간단한 방법입니다. 그러나 이것은 특정 에지의 검색 속도가 느려질 수 있습니다. 각 목록은 꼭지점의 정도만큼 길기 때문에 목록이 정렬되지 않은 경우 특정 가장자리를 확인하는 최악의 경우 조회 시간이 O (n)이 될 수 있습니다. 그러나 정점의 이웃을 찾는 것은 사소한 일이되며, 희소하거나 작은 그래프의 경우 인접 목록을 반복하는 비용은 무시할 수 있습니다.
반면 인접 행렬은 일정한 조회 시간을 제공하기 위해 더 많은 공간을 사용합니다. 가능한 모든 항목이 존재하므로 인덱스를 사용하여 일정한 시간에 에지의 존재를 확인할 수 있습니다. 그러나 가능한 모든 이웃을 확인해야하므로 이웃 조회는 O (n)을 사용합니다. 명백한 공간 단점은 희소 그래프의 경우 많은 패딩이 추가된다는 것입니다. 이에 대한 자세한 내용은 위의 메모리 토론을 참조하십시오.
여전히 무엇을 사용해야할지 확실하지 않은 경우 : 대부분의 실제 문제는 인접 목록 표현에 더 적합한 희소 및 / 또는 큰 그래프를 생성합니다. 구현하기가 더 어려워 보일 수 있지만 그렇지 않다는 것을 확신합니다. BFS 또는 DFS를 작성하고 노드의 모든 인접 항목을 가져 오려는 경우 코드 한 줄만 있으면됩니다. 그러나 일반적으로 인접 목록을 홍보하지 않습니다.
답변
좋아, 그래프에 대한 기본 작업의 시간 및 공간 복잡성을 컴파일했습니다.
아래 이미지는 설명이 필요 없습니다.
그래프가 조밀 할 것으로 예상 할 때 Adjacency Matrix가 선호되는 방식과 그래프가 희소 할 것으로 예상 할 때 Adjacency List가 어떻게 선호되는지 확인하십시오.
나는 몇 가지 가정을했습니다. 복잡성 (시간 또는 공간)에 대한 설명이 필요한지 물어보세요. (예를 들어, 희소 그래프의 경우 새 정점을 추가하면 가장자리가 몇 개만 추가된다고 가정 했으므로 En을 작은 상수로 사용했습니다. 꼭지점.)
실수가 있으면 알려주세요.
답변
찾고있는 것에 따라 다릅니다.
인접 행렬 을 사용하면 두 정점 사이의 특정 가장자리가 그래프에 속하는지 여부에 대한 질문에 빠르게 답할 수 있으며 가장자리를 빠르게 삽입하고 삭제할 수도 있습니다. 단점은 당신이 특히 그래프는 스파 스 특히 매우 비효율적이며 많은 정점과 그래프에 대한 과도한 공간을 사용해야한다는 것입니다.
반면에 인접 목록을 사용 하면 가장자리를 찾기 위해 적절한 목록을 검색해야하므로 주어진 가장자리가 그래프에 있는지 확인하기가 더 어렵지만 공간 효율적입니다.
일반적으로 인접 목록은 대부분의 그래프 응용 프로그램에 적합한 데이터 구조입니다.
답변
n 개의 노드와 m 개의 간선이있는 그래프가 있다고 가정 해 보겠습니다 .
그래프 예
인접 행렬 : n 개의 행과 열
이있는 행렬을 만들고 있으므로 메모리에서 n 2에 비례하는 공간을 차지합니다 . u 와 v 로 명명 된 두 노드 사이에 가장자리가 있는지 확인하는 데 Θ (1) 시간이 걸립니다. 예를 들어 (1, 2)가 가장자리인지 확인하는 것은 코드에서 다음과 같습니다.
if(matrix[1][2] == 1)모든 모서리를 식별하려면 두 개의 중첩 루프가 필요하고 Θ (n 2 ) 를 사용하는 행렬을 반복해야합니다 . (모든 모서리를 결정하기 위해 행렬의 위쪽 삼각형 부분을 사용할 수 있지만 다시 Θ (n 2 ))
인접 목록 :
각 노드가 다른 목록을 가리키는 목록을 만들고 있습니다. 목록에는 n 개의 요소가 있으며 각 요소는이 노드의 인접 항목 수와 동일한 항목 수를 포함하는 목록을 가리 킵니다 (더 나은 시각화를 위해 이미지보기). 따라서 n + m에 비례하는 메모리 공간을 차지합니다 . (u, v)가 에지인지 확인하는 것은 deg (u)가 u의 이웃 수와 같은 O (deg (u)) 시간이 걸립니다. 기껏해야 u가 가리키는 목록을 반복해야하기 때문입니다. 모든 모서리를 식별하려면 Θ (n + m)이 필요합니다.
예제 그래프의 인접 목록
필요에 따라 선택해야합니다.
평판 때문에 매트릭스 이미지를 넣지 못해 미안해
답변
C ++로 그래프 분석을보고 있다면 BFS를 포함한 여러 알고리즘을 구현하는 부스트 그래프 라이브러리 가 가장 먼저 시작될 것 입니다.
편집하다
SO에 대한 이전 질문이 도움이 될 것입니다.
ac-boost-undirected-graph-and-traverse-it-in-depth-first-searc h를 만드는 방법
답변
이것은 예를 통해 가장 잘 대답됩니다.
예를 들어 Floyd-Warshall 을 생각해보십시오 . 인접 행렬을 사용해야합니다. 그렇지 않으면 알고리즘이 점근 적으로 느려집니다.
아니면 30,000 개의 꼭지점에 대한 조밀 한 그래프라면 어떻게 될까요? 그런 다음 에지 당 16 비트 (인접 목록에 필요한 최소값)가 아닌 정점 쌍당 1 비트를 저장하므로 인접 행렬이 의미가있을 수 있습니다. 1.7GB가 아닌 107MB입니다.
그러나 DFS, BFS (및 Edmonds-Karp와 같이이를 사용하는 알고리즘), 우선 순위 우선 검색 (Dijkstra, Prim, A *) 등과 같은 알고리즘의 경우 인접 목록은 행렬만큼 좋습니다. 글쎄, 행렬은 그래프가 조밀 할 때 약간의 가장자리를 가질 수 있지만 주목할만한 상수 요소에 의해서만 가능합니다. (얼마나? 실험의 문제입니다.)