W jaki sposób znaleźć wszystkie wierzchołki grafu skierowanego, bez cykli, leżące na ścieżkach najdłuższej długości? Nic nie wiemy o spójności/silnej spójności grafu.
0
0
A teraz może jednak po polsku?
- Wierzchołki nigdy nie mają cykli.
- Co to znaczy
leżące na ścieżkach najdłuższej długości? Na ilu z tych ścieżek?
Szklana kula mówi, że może chciałbyś: podgraf grafu skierowanego, bez cykli, który stanowi najdłuższą ścieżkę w danym grafie?
Rada na przyszłość: jeśli nie umiesz odrobić pracy domowej i co więcej nie rozumiesz polecenia, to przepisz je tak jak stoi w jego treści, a nie próbuj "opisać własnymi słowami" bo wychodzą takie bzdury jak tutaj...
0
- "wierzchołki grafu skierowanego, bez cykli"
"grafu skierowanego, bez cykli" - Jeżeli graf nie jest silnie spójny, to takich ścieżek może być dużo. W każdej silnie spójnej składowej jest owa średnica grafu. Ale tak - chodzi o podgraf stanowiący najdłuższą scieżkę w grafie.
0
No to chodzi o jeden podgraf czy o jeden dla każdej silnie spójnej składowej?
0
O jeden dla każdej spójnej składowej. Można w łatwy sposób wyznaczyć wierzchołki, będące końcami średnicy (2x BFS) jednak nie mam pomysłu co dalej z tym zrobić.
0
Dla dowolnego grafu to jest problem Longest Path i jest NP-trudny. Ale dla acyklicznego grafu można to zrobić tak: http://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths
0
Chodzi ci o spojne czy o silnie spojne skladowe w koncu? Bo to roznica. Poza tym nawet jesli by rozpatrywac oddzielnie kazda skladowa to i tak moze byc duzo roznycb sciezek o dlugosci k gdzie k to najdluzsza sciezka w kazdej z nich. Ale jako ze jest to DAG to dla kazdej spojnej skladowej:
posortuj topologicznie
przejdz graf dfsem albo bfsem zaczynajac od wierzcholkow do ktorych nic nie wchodzi i zapamietuj sobie odleglosci w jakiejs tablicy
przejdz po tablicy i znjdz max odleglosc
przejdz graf jeszcze raz dfsem odkladajac wierzcholki na jakis stos, jak znajdziesz wierzcholek, ktorego ogleglosc == max odleglosci to wypisz wierzcholki ze stosu (sciezka)
Powinno dzialac w O(V+E), chyba ^^
EDIT: to by działało dla znalezienia jednej ścieżki
żeby znaleźć wszystkie to trzeba ostatnie przeszukanie trochę trudniej zaimplementowac i to jest już O(n^n)