학교 과제를 위해 나는 그래프를 만들고 그것으로 물건을 만들어야합니다. 입력시 각 꼭지점에는 0-999'999'999의 ID가 있습니다. 이 배열을 오래 만들 수 없기 때문에이 ID를 인접 행렬의 키로 사용할 수 없습니다. 첫 번째 해결책은 원래의 임의의 ID를 만들고 사전 /지도와 같은 일종의 ID에 저장하는 것이 었습니다. 그러나 10,000 개의 버텍스 레코드를 얻으면 조회가 느리게 진행될 수 있습니다. 알고리즘은 O (n^2) 이하이어야하며 이미 BFS와 toposort가 있습니다. 이 경우 가장 좋은 해결책은 무엇입니까? 보조 노트로서 - 이미 설정된 라이브러리를 사용할 수 없으므로 (그래프, 맵, 벡터, 문자열 클래스 등을 사용할 수는 없습니다), 최선의 선택이라면 직접 코딩 할 수 있습니다.빠른 사전 만들기
원하는 것은 이진 검색 트리 O(logn) 시간 또는 해시지도에서 조회를 할 ~O(1) 시간을 조회하거나 배열 경로와 함께 갈 수있는 경우 귀하의 배열의 크기는 최대 값 ID는 (귀하의 경우 10^9) 가질 수 있습니다.
@amit이 말한 것처럼 AVL/Red-Black 나무와 해시 맵을 확인하십시오. O(n) 아래의 그래프에서 조회를 수행하는 더 좋은 방법은 그래프의 토폴로지를 변경하여 "검색 그래프"로 바꿀 수있는 경우가 아니면 않는 것입니다.
왜 10 억 크기의 배열을 만들어야합니까? 노드 수의 인접성 행렬 또는 인접성 목록을 간단히 생성 할 수 있습니다.
버텍스 수가 일정하든 그렇지 않든간에 adjacency list으로 이동하시기 바랍니다. 예를 들어 10 개의 노드가 있으므로 크기 10의 배열을 만들어야합니다. 그런 다음 위의 링크에서 볼 수있는 것처럼 각 노드에 대해 가장자리 목록을 만듭니다.
이 그래프를 고려, 당신은 정말 당신이 인접리스트 대신 4 개 요소 10^10 요소를 가질 필요가 있다고 생각합니까?
문제는 내가 10 개의 꼭지점을 가지면 배열에서 ID가 1-10이지만 각 꼭지점에서 인접한 단위가 예를 들어 89777371과 13876873은 내가 1-10로 번역해야합니다. 각 정점에 대해 이것은 시간이 걸립니다. 크기가 10 억에 이르는 배열을 통해 특정 정점이 어디에 있는지 즉시 알 수있었습니다. – vvolis
왜 정점의 이름이 10 자리 문자열입니까? 행렬에 26^10 행을 사용해야합니까? 각 노드 인접리스트는'value'와'next'를 가지며, 값 안에'89777371'라고 쓰여질 것이고 다음 요소의 값은'13876873'이 될 것이므로 매핑 할 필요가 없습니다. – smttsp
그들은 주문 목록에 없습니다. 따라서 각 꼭지점마다지도를 통해 인접 꼭지점을 조회해야합니다. 다음 노드가 예를 들어 36827648736하지만 내 배열에있는 10 개의 요소 중 하나가 무엇인지 전혀 알지 못합니다. – vvolis
나는 임무가 마치이 건물을 직접 건축함으로써 이러한 자료 구조에 대해 가르쳐주는 것처럼 보입니다. 해시 테이블에 대해 배웠습니까? AVL/레드 - 블랙 나무? – amit
아니요 우리는 해시 테이블에 대해 알지 못했지만 할당 시점은 아닙니다. 이 주제는 그래프 (toposort, BFS, DFS, DAG 등)입니다. 조회 용으로 이진 트리를 만들 수는 있지만 가장 좋은 솔루션인지 궁금합니다 (지나치게 복잡한 것처럼 보입니다) – vvolis
배열이 ID로 정렬 된 경우 특정 ID를 찾는 것이 훨씬 빠릅니다 (힌트 : 확인 시작 –