To, ta tu, to nie macierz sąsiedztwa

Tutaj możesz podyskutować na tematy nie kwalifikujące się do żadnego z pozostałych forów

To, ta tu, to nie macierz sąsiedztwa

Postautor: narbej » 04 lut 2015, 21:33

To nie ja wymysliłem teorie grafów, to matematycy. Wymyślili też pojęcie macierzy sąsiedztwa. Oni też, albo może do spółki z wielkimi informatykami wymyślili algorytmy przeszukiwania grafów BFS czy DFS, ale raczej nie poruszając się po macierzy sąsiedztwa, tylko po tej drugiej reprezentacji grafu - wiesz o czy piszę?
Więc nazywanie planszy czy mapy, np takiego tworu, jaki też i ja użyłem w swoim zadaniu Linia brzegowa, macierzą sąsiedztwa jest pomstą wołającą do nieba, powodującą siwienie i wypadanie [przez wyrywanie sobie] włosów i jeszcze wiele innych szkodliwych skutków na mojej biednej osobie, o których dalej.

Najprostsza mapa, poruszamy się tylko pionowo i poziomo
Kod: Zaznacz cały
|1 2|
|3 4|

Mapę powyżej przerabiamy na graf, ale to musisz sobie zrobić sam, ewentualnie w wyobraźni, lub może kiedyś wkleje tu rysunek wykonany graphvizem
Gdy mamy już ten graf, czy widzisz go oczyma wyobraźni? Jednak narysuję go, chociaż w uproszczeniu:
Kod: Zaznacz cały
1 -- 2
|    |
3 -- 4

Zapiszemy go jako macierz sąsiedztwa = graf nieważony nieskierowany:
Kod: Zaznacz cały
  | 1 2 3 4
------------
1 | 0 1 1 0
2 | 1 0 0 1
3 | 1 0 0 1
4 | 0 1 1 0

Pierwszy twór - mapa, plan, tak jest macierzą, ale w żadnym wypadku macierzą sąsiedztwa. Sam popatrz! Dojdziesz do wniosku, że dopiero ta macierz powyżej jest macierzą sąsiedztwa. Poruszanie się po tej mapie [macierz na samej górze, ale nie macierz sąsiedztwa], nawet używając stosu, czy kolejki to wcale z tego powodu nie oznacza, że to jest algorytm BFS czy DFS, jest to prosty algorytm flud-fill [ale warto planszę otoczyć murkiem].

Wracając do tych skutków ubocznych na mojej osobie, to właściwie nie zauważyłem żadnych innych więcej. Te codzienne koszmary nocne, a może powinienem powiedzieć conocne, to nie z tego powodu. Więc spokojnie sobie nazywaj to jak chcesz. Ja i tak będę miał koszmary, ale to nie twoja wina. To wina admina. Co noc w środku nocy związuje mi nogi i ręce i każe mi robić gcd [nwd] Dzisiaj wpadłem na genialny pomysł. Gdy dzisiaj, spyta:
-- czy już,
kiwnę głową, tak, a gdy powie:
--- przecież to czysta kartka, nic tu nie ma.
Odkrzyknę krótko:
-- Warto uczyć się języków! Whitespaces amigo[s]!
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Wróć do Forum ogólne

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 1 gość

cron