Witam!
Mam taki problem:
sa dane punkty A do G, polaczone sa one ze soba tak:
A->B
A->C
B->D
C->D
C->E
E->F
F->G
Chcialbym znaleŹĆ wszystkie mozliwe drogi z punktu A do G...
Dzieki na zaś ;D
0
0
Poczytaj o grafach oraz wyszukiwaniu ścieżek w grafach.
0
Kartka papieru? :P
Drogi są "jednokierunkowe"?
Myśle ze można to zrobić w ten sposób: każdy punkt (A,B,C...) jest elementem listy. Każdy element składa sie ze swojej nazwy, z tablicy wskaźników do elementów z którymi jest połączony i z ilości elementów w tych tablicach. Rekurencyjnie skaczesz sobie do kolejnych elementów (wywołania rekurencyjne są w pętli for która iteruje po kolejnych adresach w tablicy). Stop rekurencji występuje gdy trafisz na szukany punkt G lub gdy okaze się że nie trafiłeś, a nie masz już gdzie skoczyć.
Nie wiem tylko jak tutaj opracować wyświetlanie możliwych tras :)
0
no ale w opisanym przykładzie jest tylko jedna droga:
A -> C -> E -> F -> G
:|
0
Ja uznalem to za "przykład", a nie jako konkretne dane. Algorytmy pisze sie zazwyczaj po to żeby rozwiązywać określony typ problemu, a nie tylko jeden konkretny problem.
0
Przeszukuj graf w głąb (DFS) zapisując wszystkie odwiedzane punkty w kolejce LIFO.
Przeszukiwanie rozpocznij od punktu startowego. Gdy dojdziesz do punktu końcowego zapisz kopię kolejki (będzie to jedna z dróg) i nie idź już głębiej tylko się cofnij i szukaj dalej.