힙/우선 순위 대기열을 사용하여 가중 그래프 지정

Question

이 문제를 시각화하는 데 문제가 있습니다.

그래서 나는 가중 그래프를 유도했습니다. Dijskra의 알고리즘을 사용하여이 그래프를 스캔하고 최단 경로를 인쇄해야합니다. 나는 힙/우선 순위 대기열을 사용해야하며, 현재의 지식에서 나는 이것이 동일한 것임을 안다.

그러나 그래프에는 2 개 이상의 자식이 있고 힙에는 2 개의 자식 노드 만있을 수 있습니다. 이것을 힙 형식으로 만들면 다른 자식 (가장자리)은 어떻게됩니까?

Answer 1

힙의 표현은 어쨌든 그래프 구조와 상관 관계가 없습니다.

그래프 작업 중입니다. 최소 거리를 가진 꼭지점을 찾아서 그 꼭지점으로부터 최소 거리를 결정할 때 사용해야합니다. 힙은 당신이 그 일을하도록 돕고 있습니다. 그 이상은 아닙니다.

이 힙에서는 레이어가 그래프의 계층을 나타내지 않고 단순히 노드의 값이 하위의 값인보다 작은 속성으로 힙의 레이어를 연결합니다. 그게 전부 야. 그래프의 형제가 힙에서 부모 - 자식 관계에있을 가능성이 있습니다.

힙 작업을 수행하거나 Dijkstra를 만들기 위해 힙에 그래프 구조를 모방해야한다고 생각할 필요가 없습니다. 그것을하는 방법이 아닙니다. (당신도 그것을 할 수 없습니다).

힙 형식으로 넣을 때 다른 자식 (가장자리)은 어떻게됩니까?

• 아무 반응이 없습니다. 적절한 키를 사용하여 힙에 삽입하는 한 제대로 작동합니다. 그게 전부 야.