#programowanie #algorytmy Mirki, jak byście rozwiązali następujący problem: mamy bazę danych złożoną z elementów, gdzie każdy element może (ale nie musi) mieć przypisanych do N elementów nadrzędnych. Nie powinno być sytuacji, w której elementy tworzą cykle, czyli idąc po kolejnych elementach nadrzędnych wracamy do tego od którego zaczęliśmy.
Pytanie brzmi jak najsensowniej sprawdzać w praktyce, czy dodawany nowy element przez użytkownika nie zamknie jakiegoś cyklu?
Teoretycznie z racji tego że to jest klasyczny graf skierowany, to powinien mieć tu zastosowanie klasyczny DFS, jednak mam wątpliwości czy to jest najlepsze rozwiązanie, jeśli elementów w bazie będzie np. 10 000 albo 100 000 i za każdym razem kiedy użytkownik będzie chciał dodać nowy element z przypisanym elementem nadrzędnym to ma być pobierana cała baza danych DFS-em w celu sprawdzenia czy nie powstanie jakiś cykl.
@Wegrzynski: chat gpt podpowiada wiele rozwiązań, imo najlepiej pasuje tutaj UnionFind:
3. Struktury danych wspomagające sprawdzanie cykli Zastosowanie zaawansowanych struktur danych takich jak Union-Find z dodatkowym sprawdzaniem cykli może być bardziej wydajne.
Krok po kroku: Użyj struktury Union-Find do zarządzania zbiorami połączonych wierzchołków. Przy każdym dodaniu nowej krawędzi, sprawdź, czy oba końce krawędzi są już w tym samym zbiorze. Jeśli tak, oznacza to istnienie cyklu. Jeśli nie, połącz zbiory.
@Wegrzynski: Przyjrzałbym się temu od strony algorytmu sortowania topograficznego. Poza tym, jeśli masz bazę danych możesz stworzyć strukturę, która jest płaska gdzie wyszukiwanie zazwyczaj jest jakoś zoptymalizowane(lub można je zoptymalizować używając np indeksów w MySQL).
Może narysuj jakieś przykłady. Ciężko mi zrozumieć o co Ci chodzi. Piszesz, że nie ma być cyklu a jednocześnie, że jak przechodzimy po elementach nadrzędnych to wracamy do tego od którego zaczęliśmy. Nie napisałeś też w którą stronę są skierowane krawędzie w tym grafie.
Pytanie brzmi jak najsensowniej sprawdzać w praktyce, czy dodawany nowy element przez użytkownika nie zamknie jakiegoś cyklu?
Teoretycznie z racji tego że to jest klasyczny graf skierowany, to powinien mieć tu zastosowanie klasyczny DFS, jednak mam wątpliwości czy to jest najlepsze rozwiązanie, jeśli elementów w bazie będzie np. 10 000 albo 100 000 i za każdym razem kiedy użytkownik będzie chciał dodać nowy element z przypisanym elementem nadrzędnym to ma być pobierana cała baza danych DFS-em w celu sprawdzenia czy nie powstanie jakiś cykl.
3. Struktury danych wspomagające sprawdzanie cykli
Zastosowanie zaawansowanych struktur danych takich jak Union-Find z dodatkowym sprawdzaniem cykli może być bardziej wydajne.
Krok po kroku:
Użyj struktury Union-Find do zarządzania zbiorami połączonych wierzchołków.
Przy każdym dodaniu nowej krawędzi, sprawdź, czy oba końce krawędzi są już w tym samym zbiorze.
Jeśli tak, oznacza to istnienie cyklu.
Jeśli nie, połącz zbiory.