Skierowany graf - użycie dynamicznych struktur danych.

0

Muszę zrealizować projekt, który głównie będzie się opierał na skorzystaniu z algorytmu Dijkstry obsługującego skierowany graf.

Pomógłby ktoś zinterpretować te dwie zasady?

rules

  1. Czym są dynamiczne struktury danych? Czy mogę skorzystać z np. tablic, stosu, kolejki priorytetowej?

  2. Z jakich struktur danych byście skorzystali wiedząc, że w projekcie chodzi o Dijkstrę z skierowanym (jednokierunkowym) grafem?

Dzięki za porady.

1

Masz napisać własne kontenery odpowiadające za listy/drzewa i na ich podstawie zaimplementować algorytm Dijkstry.

Jeśli głównym celem kursu/ćwiczenia jest nauczenie was jak implementować kontenery, to jest to ok. Jeśli to Dijkstra jest celem, to kurs jest do bani, bo poza celami edukacyjnymi nie powinno się właściwie samemu kontenerów tworzyć.

PS: jako technically correct możesz użyć kontenerów z Boosta, ale profek pewnie nie uzna :​D

1

Nie jest tak żle, algorytm Dijkstry jest podobny do algorytmu Boruwki, żeby to miało złożonośc O(nlog), Potrzebujesz tylko skrobnąć Linked List i Heap (żeby tanio O(logn)) wybierać `"najtanśzą" krawędź. Oba te kontenery Powinieneś już mieć w notatkach:)

0

@lion137: @kq

Tylko jeśli chcę skorzystać z np. kopca, to tu nie chodzi o kopca z C++ STL, tylko o jakiegoś innego kopca, którego samemu zaimplementuję od podstaw?

I analogicznie co do innych kontenerów.

Jest właściwie jakikolwiek gotowy kontener z którego mogę skorzystać? Chyba najzwyklejsza tablica powinna być takim kontenerem, a coś innego?

1

Wydaje się, że Musisz korzystać z własnej strukrury danych, czyli podać jej kod. Ma być dynamiczna czyli zachowywać się, jak, np. ArrayList z javy. Zwykła tablica taka nie jest.

1

Swoje możesz implementować, nie ma problemu.

1 użytkowników online, w tym zalogowanych: 0, gości: 1