Odległości w grafie

0

Doszedłem do momentu, kiedy posiadam listę sąsiedztwa wierzchołków w grafie.
Potrzebuję, znaleźć 3 wierzchołki będące w równej odległości. Więc potrzebne mi są odległości między każdym z wierzchołków, ale nie wiem jak to zrobić mając listę sąsiedztwa lub macierz sąsiedztwa.

0

Żeby uzyskać odległość pomiędzy każdą parą wierzchołków musisz użyć:

0

Mam jeszcze jedno pytanie, mając odległości między każdymi wierzchołkami jak znaleźć trójki będące w tej samej odległości od siebie? Wydawało mi się to proste, ale nie jest.

0

Najprościej byłoby gdybyś miał macierz sąsiedztwa bo wystarczyłoby sprawdzać czy masz równe wartości w tab[x][y], tab[x][v], tab[y][x], tab[v][x] dla kolejnych wartości x,y,v
Możesz też zrobić tak:

  • wrzucasz do rozwiązania wszystkie wierzchołki jako 1 element
  • iterujesz po wszystkich wierzchołkach i sprawdzasz ich odległość od kolejnych wierzchołków w zbiorze rozwiązań (tzn sprawdzasz czy odległość od X do Y jest taka sama jak od Y do X) i jeśli jakiś nam pasuje to dopisujemy go jako 2 element rozwiązania
  • po tej iteracji usuwamy wszystkie wierzchołki które nie mają 2 elementu
  • iterujemy znów po wszystkich wierzchołkach i sprawdzamy ich odległość z istniejącymi parami i jeśli nam pasuje to dopisujemy jako 3 element
0

Czyli niepotrzebnie pisałem kod na obliczanie odległości.
Myślałem, że z samej macierzy sąsiedztwa nie pójdzie tego wyliczyć.

Chociaż nie. W pierwszym zdaniu na pewno masz na myśli macierz sąsiedztwa (0, 1)? Czy taką, w której mam odległości każdego wierzchołka od każdego? Bo nadal nie rozumiem co mi da sprawdzanie po kolei tablicy gdy tam jest kilka jedynek i same zera.

0

No nie wygłupiaj się. Chodzi mi oczywiście o macierz sąsiedztwa ale z odległościami wyliczonymi wcześniej a nie bezpośrednimi krawędziami.

0

hehe.
Dzięki za pomoc, ale uważam, że ta podpowiedź jest nie trafna. Albo jej nie rozumiem.
Jeśli przeszukam tablicę z odległościami - każdy od każdego to wynik nie będzie poprawny. Ale sprawdziłem, zrobiłem te 3 pętelki i wynik jest o wiele za duży. Przecież w tablicy przechowuję odległości jak już napisałem każdego od każdego, więc jeśli wartości będą równe w różnych częściach tablicy to nie znaczy, że te 3 wierzchołki są w tej samej odległości od siebie tylko, w takim wypadku wybiera pary wierzchołków w równej odległości ale nie powiązane ze sobą. Nie wiem czy to co napisałem jest zrozumiałe, ale jednak to inaczej muszę zrobić.

0

No jak zrobiłes 3 pętle na jana to jasne że wynik będzie za duży. Napisałem ci wyraźnie które wartości musisz porównywać:
tab[x][y] == tab[y][x] -- znaleźliśmy parę która spełnia wymagnia
tab[x][v] == tab[v][x] -- znaleźliśmy drugą parę która spełnia wymagania
tab[[x][y] == tab[x][v] -- sprawdzamy czy te dwie pary maja te same odległości

To wszystko oczwiście dla x,y,v różnych od siebie i najlepiej silnie większych żeby nie dublować wartości, tzn x<y<v żeby nam nie wyszły wyniki np. (1,2,3), (2,1,3) itd

0

Zadania z OI wykonuje się samodzielnie, nie z pomocą forum : )

0

@MaxGarden zauważ że autor nie spytał tutaj o rozwiązanie konkretnego problemu tylko o pewną transformację, czyli wiedział co chce wykonać a nie wiedział jak dokładnie technicznie to zrealizować. Niemniej jednak musimy chyba się mieć na baczności bo to już kolejny temat z prośbami o pomoc z OIG i OI...

1 użytkowników online, w tym zalogowanych: 0, gości: 1