• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Java Grafy macierz sąsiedztwa

VPS Starter Arubacloud
0 głosów
2,064 wizyt
pytanie zadane 19 listopada 2016 w Java przez Patryk Rafał Bywalec (2,700 p.)
Witam może mi ktoś wytłumaczyć jak w javie utworzyć macierz sąsiedztwa nie chce kodu chcę tylko żeby ktoś mi wytłumaczył jak to napisać

2 odpowiedzi

0 głosów
odpowiedź 19 listopada 2016 przez damianMg4 Użytkownik (740 p.)
0 głosów
odpowiedź 13 stycznia 2017 przez Wojciech Cies Obywatel (1,140 p.)

Graf to struktura składająca się z węzłów i połączeń. Połączenia mogą być jedno- lub dwu-kierunkowe (zależnie od potrzeb danego algorytmu). Załóżmy że rozmawiamy o grafie w którym dwa węzły mogą być połączone lub nie. Czyli NIE obsługujemy sytuacji:

  • pomiędzy tymi samymi dwoma węzłami może istnieć więcej niż jedno połączenie
  • połączenia skierowane, gdzie czymś innym jest połączenie A > B, B < A czy A <> B

Taki graf można zapisać więc jako "kwadratową" macierz połączeń, gdzie długość boku to ilość węzłów. Przykładowo graf składający się z 5 węzłów A,B,C,D,E, gdzie istnieją połączenia A-B, A-D, C-E, C-D może być zapisany tak:

# A B C D E
A x 1 0 1 0
B 0 x 0 0 0 
C 0 0 x 1 1
D 0 0 0 x 0
E 0 0 0 0 x 

Taką macierz możesz zaimplementować jako dwuwymiarową tablicę. Tylko że ona marnuje dużo miejsca. Połowa powierzchni jest niewykorzystana (wystarczy zaznaczyć A-B, B-A jest tym samym). Jak w graf jest mało połączony to większość pól to będą zera.

Dlatego częściej tworzy się jednowymiarową tablicę sąsiedztwa. To też tablica dwuwymiarowa, ale prostsza. Zapisujemy w niej tylko informację o połączeniach:

{
  {A, B},
  {A, D},
  {C, E},
  {C, D}
}

W ten sposób oszczędzasz dużo miejsca w pamięci pomijając zera.
 

Podobne pytania

+1 głos
1 odpowiedź 1,226 wizyt
pytanie zadane 27 maja 2017 w C i C++ przez redie Obywatel (1,490 p.)
0 głosów
1 odpowiedź 362 wizyt
–1 głos
0 odpowiedzi 241 wizyt
pytanie zadane 18 sierpnia 2020 w C i C++ przez LinosiK Obywatel (1,920 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...