W jaki sposób mogę przedstawić ważony, ukierunkowany wykres w Javie?

Question

Nie mogę używać żadnych zewnętrznych bibliotek, więc staram się wymyślić kilka sposobów na samodzielne zbudowanie struktury danych. Myślałem, że może coś takiego:

public class Node{ 
    Set<Edge> adjacent; 
    int value; 
} 

public class Edge{ 
    Node target; 
    int weight; 
} 

Ale domyślam się, że jest prawdopodobnie lepszy sposób to zrobić.

Moim ostatecznym zastosowaniem do tego wykresu jest uruchomienie algorytmu Bellmana Forda, ale oczywiście potrzebuję najpierw działającego wykresu!

Answer 1

Odpowiedź zależy w dużej mierze od algorytmów, które planujesz zastosować do swoich wykresów.

Istnieją dwa popularne sposoby prezentacji wykresu - adjacency list i adjacency matrix. W twoim przypadku macierz sąsiedztwa jest kwadratową tablicą liczb całkowitych reprezentujących wagi. Twoja reprezentacja używa listy przyległości.

Istnieją algorytmy, które działają lepiej na macierzach sąsiedztwa (np. Algorytmie Floyd-Warshall). Inne algorytmy działają lepiej na listach sąsiednich (np. Algorytm Dijkstry). Jeśli twój wykres jest rzadki, użycie macierzy sąsiedztwa może być zaporowe.

Answer 2

Jak zwykle, możesz reprezentować wykresy jako Listy Przyległości lub Matryce Przyległości. Wybór naprawdę zależy od szczegółów twojego problemu.

Używając macierzy sąsiedztwa, można po prostu mieć macierz liczb całkowitych, reprezentujących wagę.

Jeśli zdecydujesz się na listę sąsiedztwa, możesz po prostu zapisać listę listy liczb całkowitych (zakładając, że węzły twojego wykresu są identyfikowane przez liczbę całkowitą), podobnie do tego, co zrobiłeś.

Answer 3

można użyć węzeł jak w nieważonej wykresie posiadający listę węzłów, z którym jest połączony, oraz dodać wagi związanych z połączeniami jak:

public class Node{ 
    int value; 
    HashMap<Node,Integer> adjacency; 
}