Mam taką tablicę 5x5:
1 2 3 4 5
1 0 1 0 0 0
2 0 0 1 1 1
3 0 0 1 1 0
4 0 0 1 0 1
5 0 0 1 1 1
Jest to macierz sąsiedztwa pewnego grafu. Tablica jest 5x5 więc wiadomo, że graf ma 5 wierzchołków. Ja chcę napisać program, któremu podam pewną liczbę np.p=2 poczym ten program wyświetli mi czy droga o długości p czyli =2 istnieje czy nie w taki sposób:
wierzchołki
1 1 nie
1 2 nie
1 3 tak
1 4 tak itd.
Gdybym podał, że chcę drogę p=1 to sprawa jest prosta wystarczy dwiema pętlami przelecieć przez tablice i posprawdzać wartości. Jednak gdy p jest właśnie np. = 2 program powinien robić coś takiego:
Biorę wierzchołki:
1 1 -nie ma połączenia więc lecę dalej
1 2 -jest połączenie, zmniejszam p i szukam połączń dla wierzchołka 2
...2 1 -nie ma połączenia więc lecę dalej
...2 2 -nie ma połączenia więc lecę dalej
...2 3 -jest połączenie, zmniejszam p, które teraz jest już równe 0 więc zapisuje, że taka droga istnieje z 1-3.
...2 4 -jest połączenie, zmniejszam p, które teraz jest już równe 0 więc zapisuje, że taka droga istnieje z 1-4
...2 5 -jest połączenie, zmniejszam p, które teraz jest już równe 0 więc zapisuje, że taka droga istnieje z 1-5
i teraz program powinien wrócić by dokończyć poprzednią pętlę:
powinien wziąć:
1 3 nie ma połączenia więc lecę dalej
1 4 nie ma połączenia więc lecę dalej
1 5 nie ma połączenia więc lecę dalej
I tu jest problem. Nie wiem jak to zrobić, iteracyjnie chyba się nie da a z rekurencją mi coś nie wychodzi. Jak mogę wykonać takie przeszukiwanie?
0
0
Lepiej zapytaj tutaj:
Algorytmy i struktury danych
0
w macierzy przejść masz wszystkie ścieżki długości jeden, jak ją podniesiesz do kwadratu, to będziesz miał wszystkie ścieżki długości dokładnie dwa itd. n-ta potęga, ścieżki długości n :)