그래프(자료구조) 라이브러리 질문

Question

QuickGraph (C#)구현을 살펴보니 해시테이블을 통해 인접 리스트를 얻더군요.(var edges &#61; vertexEdgesDictionary[vertexId]; 와 같은 형식으로)하지만 탐색 알고리즘에서 재귀적인 방문을 하게 되는데,인접한 정점을 방문할 때마다 해시테이블을 조회하는 건 이상한 것 같습니다.유저로부터 받은 정점의 이름(번호)을 배열 인덱스로 번역해서 내부적으로는 배열 인덱스를 통해 조회한다든지,아니면 정점 자체를 객체로 만들고 그 안에 인접 리스트를 포함한다든지하는 방법이 있을 것 같은데,왜 그렇게 구현 안되어있을까요..?성능을 높일 필요가 없어서?아니면 더 좋은게 필요하신 분들은 알아서 직접 만들어 쓰시나요?

빙수빙수 · Accepted Answer

인접한 정점을 방문할 때마다 해시테이블을 조회하는 건 이상한 것 같습니다.해시테이블 조회는 O(1)인데 어떤점이 이상하신지요.유저로부터 받은 정점의 이름(번호)을 배열 인덱스로 번역해서 내부적으로는 배열 인덱스를 통해 조회한다든지,아니면 정점 자체를 객체로 만들고 그 안에 인접 리스트를 포함한다든지하는 방법이 있을 것 같은데,왜 그렇게 구현 안되어있을까요..?성능을 높일 필요가 없어서?말씀하신 각각의 구현도 다 유즈케이스가 있겠죠. 일반적으로 저런 라이브러리의 구현체들은 시간/공간복잡도, 복잡도의 상수 및 여러 유즈케이스를 고려해 제일 무난한 방법을 고릅니다.말씀하신 배열의 예를 들어 볼까요. 물론 가능한 방법입니다만, add (노드 추가) 연산에 있어서 배열이 꽉 찼을때 새로운 노드를 추가하려면 커다란 배열을 새로 할당해서 기존의 배열을 복사해야 할 겁니다. 이게 괜찮은 경우도 있겠지만, 간헐적으로 add가 너무 오래 걸리는게 누구에게는 치명적인 문제일 수도 있습니다.정점을 객체로 만들고 인접 리스트로 한다면 노드의 총 갯수나 엣지의 총 갯수를 파악하는데에 모든 그래프를 통째로 방문해야하거나, 임의의 어떤 노드를 삭제할때 복잡할 수 있거나, 아니면 단순히 캐시미스로 인한 성능저하가 발생할지도 모릅니다 (제가 한 말이 맞을수도 틀릴수도 있습니다).단순히 하고싶은 말은, 저런 라이브러리들의 구현은 모든 상황에서 두루 쓸만한 무난한 구현체를 지향한다는 겁니다. 어떤 한 구현이 이해가 안 되거나 개선점이 보인다면, 제작자들이나 메인테이너에게 가서 질문을 해보시면 됩니다.도움이 되셨으면 좋겠네요.

그래프(자료구조) 라이브러리 질문

1개의 답변

#algorithm 목록