그래프 연결에서 이웃 노드 찾기 알고리즘

Question

경로 찾기 문제를 해결하려고합니다. 나는 고르게 이격 된 노드들의 2D 그리드를 가지고있다. 모든 이웃 연결을 찾을 수 있도록 각 노드마다 8 개의 이웃을 찾는 알고리즘이 필요합니다 (존재하는 경우).

유일한 방법

은 나는 이런 식으로 뭔가 될 것 수행하는 방법을 알고

for each node 
for every other node 
    check position to find if it is neighboring if so add it to the nodes connection list 

내 관심사는이 O(n^2) 매우 비효율적이다 나는 그것을 해결하는 더 나은 방법이 상상한다.

도움이 될 것입니다.

Answer 1

하나의 간단한 옵션은 노드의 x 및 y 좌표로 인덱싱 된 2 차원 배열에 노드 자체를 저장하는 것입니다. 그런 식으로 배열에 색인을 붙이고 거기에있는 내용을보고 위치 (x, y)에 저장된 노드에 대한 O (1) 임의 액세스를 가질 수 있습니다.

노드가 희박한 경우 노드를 (x, y) 위치로 키순 해시 테이블에 저장하는 것이 좋습니다. 이것은 주어진 위치에있는 노드에 O (1) 랜덤 액세스를 제공하고, 간단한 이중 for 루프로 8 개의 이웃을 모두 나열 할 수 있습니다.

희망이 도움이됩니다.