자료구조 그래프 구현에있어서 유의할 점

위의 3개의 X노드는 서로 다른 노드이다. (메모리가 각각 할당 되어있음) 또한, 2번쨰그림에서 왼편의 X는 노드가 아니라 인접리스트 or 인접행렬의 인덱스이다.

예를들면, 인접리스트 or 인접행렬의 A인덱스에서 X를 탐색했을때의 경우는 A인덱스에서 X노드를 탐색하는 것이다. 즉, X인덱스로 가는게 아니다.

따라서 A인덱스에서의 탐색은 여기서 종료되는것이다. 한가지더 살펴보면 (BFS기반으로설명) X인덱스에서 A탐색후 G탐색후 H탐색의 경우에, H노드까지만 탐색이 이루어지고, H인덱스로 가는것이 아니다. 이것이 'C'언어가 아닌 다른 언어로 구현 할 때 실수 할 수 있는 부분이다.

정리하자면 인접리스트 or 인접행렬의 각 인덱스의 연결리스트의 스코프(범위)는 한 칸 씩으로 제한된다.

왜 이런식으로 메모리를 쓸데없이 여러번 할당하냐고 묻는다면, DFS뿐만아니라 BFS도 고려하기위함이다. 만약 각 정점에 연결된 노드들이 매번 할당된메모리가아니라, 이전에 생성된 노드의 주소값을 그대로 활용한다면 정점에 연결된 노드들을 링크드리스트처럼 한번에 조회할수가없다. (이 말은 어렵게 들릴수있는데 여러번 곱씹어봐야한다)

마지막으로 그래프 자료구조를 유연하게 구현하기위해서는 인접리스트를 배열로 구현하지말고, map과같은 자료구조를 쓰는것이 좋다. 배열로 구현할경우 인덱싱이 정수로만 가능하기때문에 정점의 네이밍을 반드시 어떠한 정수로 매칭되게끔 설계 해야하므로 굉장히 유연하지못하다.

위의 그림으로 예를들면 A,X,G,H를 0,1,2,3으로 enum 한다면, A,X,G,H가 0,1,2,3에 매칭된다는것을 "암기"해야 할수밖에없다. 따라서 map으로 맵핑하면 굉장히 유연해진다. ex) map[string][linkedlist]형식으로...