그래프는 종종 인접 행렬을 사용하여 표현됩니다. 다양한 소스는 초기화 비용을 | V^2 | (V은 정점의 수입니다.) 그러나 어떻게 계산하지 못했습니까?그래프 구현 및 인접 행렬의 초기화
자바에서는 단순히 행렬을 선언함으로써. boolean adj [][] 일 때 런타임은 이 자동으로으로 배열을 초기화하고 false으로 초기화하면 O (V^2) 비용 (배열의 크기)이됩니다.
오해할까요? 인접성 행렬의 초기화의 2 차 비용을 피할 수 있습니까? 아니면 구현 언어에 따라 이론적 인 것입니까?
행렬의 각 요소 (많은 수의 0을 포함 할 수 있음)보다는 "1"의 위치 만 할당되는 인접 행렬의 희소 행렬 표현을 사용하면 가능합니다. this thread도 유용 할 수 있습니다.
매트릭스의 값의 기본 초기화는 실제로 기능입니다. 기본 초기화가 아니라면, 모든 필드를 직접 초기화해야 할 필요가 없으므로 그 값이 무엇을 기대하는지 알 수 있습니까?
인접 행렬에는 다음과 같은 단점이 있습니다. 메모리 효율이 좋지 않습니다 (O (n) 개의 메모리 셀이 필요합니다.) 그리고 초기화가 느리다는 단점이 있습니다. 그러나 초기화는 결코 가장 큰 문제로 간주되지 않습니다. 날 믿어, 메모리 할당을 훨씬 느리게하고 필요한 메모리가 훨씬 더 제한 시간을 초기화보다.
많은 경우 사람들은 행렬 대신 인접 목록을 사용하는 것을 선호합니다. 이러한 목록에는 O(m) 메모리가 필요합니다. 여기서 m은 그래프의 가장자리 수입니다. 이것은 특히 스파 스 그래프의 경우 훨씬 더 효율적입니다. 이 그래프 표현이 인접 행렬보다 나쁜 유일한 연산은 쿼리 is there edge between vertices i and j입니다. 매트릭스는 O(1) 시간에 응답하고 목록은 확실히 더 느리게됩니다.
전형적인 그래프 알고리즘 그러나 많은 (같은 Dijkstra, Bellman-Ford, Prim, Tarjan, BFS 및 DFS 참조)은 소정의 정점의 모든 이웃을 반복 할 필요가있을 것이다. 행렬 대신 인접 목록을 사용하면 이러한 모든 알고리즘이 엄청난 이익을 얻습니다.
그래서 2 차 시간보다 짧은 시간에 배열을 초기화하는 "트릭"이 없다는 말입니까? 이론적으로도? – Cratylus
@ user384706 아니, 이론적으로는 존재할 수 없다. 그러나 C++의'memset' 함수와 같이 고도로 최적화 된 연산을 사용하는 함수가 있습니다. –
어떤 경우에는 메모리 효율면에서 좋지 않습니다. 나는 당신이 말하고자하는 것을 알고 있지만, 행렬이 메모리 효율적 일 수 있다는 것을 아는 것이 중요합니다. [이 스레드] (http://stackoverflow.com/questions/2218322/what-is-better-adjacency-lists-or-adjacency-matrix-for-graph-problems-in-c/5419933#5419933)를 참조하십시오. info – keyser
A_A의 답변에 대해 자세히 설명해 드리겠습니다. 그는 기본적으로 인접성 목록을 유지하는 것을 의미합니다 스파 스 매트릭스를 권장합니다.
매트릭스를 사용하는 두 가지 이유가 있습니다. 성능에 전혀 신경 쓰지 않고 제공하는 간단한 코드가 마음에 들지 않거나 성능에 관심이 있지만 매트릭스가 상대적으로 가득차면 (즉, 이 게시물의 목적을 위해 적어도 20 %가 가득).
분명히 성능에 신경을 써야합니다. 행렬이 상대적으로 비어있는 경우 초기화 오버 헤드가 중요 할 수 있으므로 인접 목록을 사용하는 것이 좋습니다. 완전히 채워지면 초기화는 무시할 수 없게됩니다. 매트릭스에서 올바른 셀을 채울 필요가 있습니다 (초기화보다 더 많은 작업이 필요함). 그리고 처리해야합니다 (다시 말하지만, 초기화).
이 스레드에는 많은 혼란과 잘못된 정보가 있습니다. 사실, 인접성 매트릭스 (및 일반적으로 모든 어레이)의 초기화 비용을 피하는 방법이 있습니다. 그러나 Java 기본 요소가 기본 값으로 초기화되므로 메소드를 Java 기본 요소와 함께 사용할 수 없습니다.
data[0..n] 어레이가 자동 초기화되지 않았다고 가정 해보십시오. 시작하기 전에 그것은 이전에 기억에 있던 것에서부터 쓰레기로 가득 차 있습니다. O (n) 시간을 덮어 쓰지 않으려면 정크 데이터에서 추가 한 좋은 데이터를 구별하는 방법이 필요합니다.
"트릭"은 좋은 데이터가 포함 된 셀을 추적하는 보조 스택을 사용하는 것입니다. 우리가 처음으로 data[i]에 쓸 때 색인에 i을 추가합니다. 스택은 스택을 추가 할 때만 커지기 때문에 걱정할 필요가없는 쓰레기는 절대 포함되지 않습니다.
이제 data[k]에 액세스 할 때마다 k의 스택을 스캔하여 정크인지 아닌지 확인할 수 있습니다. 그러나 그것은 각 읽기에 대해 O (n) 시간이 걸리고, 처음에 배열의 포인트를 물리칩니다!
이 문제를 해결하기 위해 또 하나의 보조 배열 stack_check[0..n]도 쓰레기로 가득 차 있습니다. 이 배열에는 스택의 요소에 대한 포인터가 들어 있습니다. 이제 data[i]에 처음 쓸 때 i을 스택에 넣고 stack_check[i]을 새 스택 요소를 가리 키도록 설정합니다.
data[k]이 양호한 데이터 인 경우 stack_check[k]은 k을 보유하는 스택 요소를 가리 킵니다. data[k]이 정크이면 stack_check[k]의 정크 값은 스택 외부를 가리키거나 k 이외의 스택 요소를 가리 킵니다 (k은 절대로 스택에 저장되지 않았기 때문에). 이 속성을 확인하는 데는 O (1) 시간이 걸리므로 배열 액세스가 여전히 빠릅니다.
모두 가져 오면 배열과 도우미 구조를 O (1) 시간으로 정크하게 가득 채워서 만들 수 있습니다. 각 읽기 및 쓰기에서 우리는 주어진 셀에 우리의 도우미를 사용하여 O (1) 시간의 정크가 포함되어 있는지 확인합니다. 우리가 쓰레기를 쓰고 있다면 셀을 유효한 데이터로 표시하도록 도우미 구조를 업데이트합니다. 우리가 쓰레기를 읽으면 주어진 문제에 적절한 방법으로 처리 할 수 있습니다. 예를 들어 0과 같은 기본값을 반환 할 수 있습니다 (이제는 초기화하지 않았다고 말할 수도 없습니다!) 또는 예외를 throw 할 수 있습니다.
인접성 매트릭스의 스파 스 표현은 인접성 목록입니다. –