Pytania otagowane jako graph-traversal

Pytania dotyczące algorytmów przemierzania wykresów, takich jak BFS i DFS.

8
Przeszukiwanie wykresów: Najpierw szerokość kontra najpierw głębokość
Podczas poszukiwania wykresy istnieją dwa proste algorytmy: szerokość pierwszego i głębokość pierwszego (zazwyczaj przez dodanie wszystkich węzłów adjactent wykres w kolejce (wszerz) lub stosu (głębokość pierwszego)). Czy są jakieś zalety jednego nad drugim? Te, o których mogłem myśleć: Jeśli spodziewasz się, że Twoje dane będą znajdować się dość głęboko na …
7
Algorytm znajdowania średnicy drzewa za pomocą BFS / DFS. Dlaczego to działa?
To łącze zapewnia algorytm znajdowania średnicy drzewa bezkierunkowego za pomocą BFS / DFS . Zreasumowanie: Uruchom BFS na dowolnym węźle na wykresie, pamiętając węzeł wykryty jako ostatni. Uruchom BFS, pamiętając ostatnio wykryty węzeł v. d (u, v) to średnica drzewa. Dlaczego to działa? Strona 2 tego zawiera uzasadnienie, ale jest …
4
Cel szarego węzła w wyszukiwaniu na głębokości pierwszego wykresu
W wielu implementacjach pierwszego wyszukiwania głębokości, które widziałem (na przykład: tutaj ), kod rozróżnia szary wierzchołek (wykryty, ale nie odwiedzono wszystkich jego sąsiadów) i czarny wierzchołek (odkryty i odwiedzono wszystkich jego sąsiadów) . Jaki jest cel tego rozróżnienia? Wygląda na to, że algorytm DFS nigdy nie odwiedzi odwiedzonego wierzchołka, niezależnie …
2
Najkrótsza nie przecinająca się ścieżka dla wykresu osadzonego w płaszczyźnie euklidesowej (2D)
Jakiego algorytmu użyłbyś do znalezienia najkrótszej ścieżki wykresu, która jest osadzona w płaszczyźnie euklidesowej, tak aby ścieżka nie zawierała żadnych skrzyżowań własnych (w osadzaniu)? Na przykład na poniższym wykresie chcesz przejść z . Zwykle algorytm taki jak algorytm Dijkstry tworzyłby następującą sekwencję:( 0 , 0 ) → ( - 3 …
1
Kroki gwarantujące wyjście z labiryntu
Biorąc pod uwagę dwuwymiarowy labirynt, w którym możesz wydać 4 polecenia „ruch w górę / dół / prawo / lewo”. Znając labirynt, ale nie wiedząc, gdzie jest człowiek, jak znaleźć minimalną sekwencję poleceń, która gwarantuje wyjście z labiryntu? Szukam pojedynczej sekwencji poleceń, która zadziała bez względu na to, od którego …
2
Liczba możliwych ścieżek wyszukiwania podczas wyszukiwania w BST
Mam następujące pytanie, ale nie mam na to odpowiedzi. Byłbym wdzięczny, jeśli moja metoda jest poprawna: P: Podczas wyszukiwania wartości klucza 60 w drzewie wyszukiwania binarnego węzły zawierające wartości klucza 10, 20, 40, 50, 70, 80, 90 są przemieszczane, niekoniecznie w podanej kolejności. Ile jest możliwych różnych zamówień, w których …
3
Jakie jest znaczenie „szerokość” przy pierwszym wyszukiwaniu?
Uczyłem się o pierwszym wyszukiwaniu szerokości i przyszło mi do głowy pytanie, dlaczego tak nazywa się BFS. W książce Wprowadzenie do algorytmów CLRS przeczytałem następujący powód: Poszukiwanie szerokości jest tak nazwane, ponieważ równomiernie rozszerza granicę między odkrytymi i nieodkrytymi wierzchołkami na całej szerokości granicy. Nie jestem jednak w stanie zrozumieć …
1
Wykresy, które powodują, że DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności
W przypadku niektórych wykresów algorytmy wyszukiwania DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności, pod warunkiem, że oba rozpoczynają się w tym samym węźle. Dwa przykłady to wykresy będące ścieżkami i wykresy w kształcie gwiazdy (drzewa o głębokości z dowolną liczbą dzieci). Czy istnieje sposób kategoryzowania wykresów spełniających …
3
Różnica między krawędziami poprzecznymi i przednimi w DFT
W pierwszym drzewie głębokości znajdują się krawędzie, które definiują drzewo (tj. Krawędzie, które zostały użyte podczas przejścia). Pozostały pewne krawędzie łączące niektóre inne węzły. Jaka jest różnica między krawędzią poprzeczną a przednią? Z wikipedii: Na podstawie tego drzewa łączącego krawędzie oryginalnego wykresu można podzielić na trzy klasy: krawędzie przednie, które …
2
Dlaczego uważa się, że DFS ma złożoność przestrzeni ?
Według tych notatek , DFS jest uważany za złożoność przestrzeń, gdzie jest współczynnik rozgałęzienia drzewa i jest maksymalna długość każdej ścieżki w przestrzeni stanów.O(bm)O(bm)O(bm)bbbmmm To samo zostało powiedziane na tej stronie Wikibook w Search Uninformed Search . Teraz „infobox” artykułu Wikipedii na temat DFS przedstawia następujące aspekty złożoności algorytmu: O(|V|)O(|V|)O(|V|) …
1
Znalezienie najkrótszej ścieżki między dwoma węzłami
Biorąc pod uwagę ważony digraf G=V,EG=V,EG=V,Ei funkcja wagi, d(u,v)d(u,v)d(u,v), zwykle można użyć algorytmu Dijkstry, aby uzyskać najkrótszą ścieżkę. Interesuje mnie to, jak uzyskać2nd2nd2^{nd}- najkrótsza ścieżka, 3rd3rd3^{rd}-krótko i tak dalej. Pytania: Czy istnieje skuteczny algorytm do uzyskania i-tej najkrótszej ścieżki między dwoma węzłami na wykresie ważonym? Czy istnieje skuteczny algorytm pozwalający …
3
Unikalna ścieżka na ukierunkowanym wykresie
Projektuję algorytm dla klasy, który określi, czy skierowany wykres jest unikalny w odniesieniu do wierzchołka vvv tak, że dla każdego u ≠ vu≠vu \ne v jest co najwyżej jedna ścieżka z vvv do uuu. Zacząłem od użycia BFS (wyszukiwanie szerokości), aby znaleźć najkrótszą ścieżkę od v do innego wierzchołka u, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.