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?
Ja bym to zrobił tak:
- na początku mam taką samą macierz
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
obrazuje ona tak jak napisałeś drogi długości jeden. na jej podstawie tworzę nową macierz, która będzie obrazowała czy istnieje droga długości dwa między danymi dwoma wierzchołkami. Można to zrobić w następujący sposób: jeżeli między dwoma wierzchołkami I oraz J istnieje droga to przeszukuję kolumnę I, żeby powiększyć tą drogę o jeden, następnie przeszukuję sąsiadów J, żeby w drugą stronę powiększyć o jeden drogę. Cały czas musisz mieć dwie macierze, jedną która obrazuje połączenia długości jeden i drugą, która obrazuje drogi długości większej.
Nie bardzo rozumiem możesz to przedstawić na liczbach tak jak ja wcześniej? Rozumiem, że tworze dwie pętle jedna w drugiej, pierwsza i druga j obie wykonują się do wartości 5. Pętla i to wiersze a j kolumny tak?
I jak to ma iść?
i j
1 1
1 2 jest droga o długości 1 wiec co teraz robię?