Java Grafy macierz sąsiedztwa

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

odpowiedź 19 listopada 2016 przez damianMg4 Użytkownik (740 p.)

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.