Chciałbym zapytać, czy istnieją algorytmy, jak zminimalizować przejazdy przez krawędź na wykresie, na przykład, jeśli mam macierz przejścia wykresu.Redukcja przewężenia na wykresie
Znalazłem metody, takie jak próby umieszczenia węzłów wokół drugiego węzła, ale chciałbym poznać kilka innych pomysłów. Dzięki.
Istnieje szereg dobrze znanych algorytmów/bibliotek, które zostały opracowane dla aplikacji do rysowania wykresów, można uzyskać nieco tła here.
Aby narysować grafy bezkierunkowe, popularnym wyborem jest algorytm układu opartego na wymiarze, w którym krawędzie wykresu są traktowane jako sprężyny (siły przyciągania), podczas gdy wierzchołki są traktowane jako cząstki naładowane (stosując siły odpychające). Algorytm działa poprzez aktualizację pozycji wierzchołków na podstawie tych sił, aż do osiągnięcia stanu ustalonego. Możesz przeczytać więcej o metodach opartych na siłach here. Ponieważ algorytmy te szukają rozwiązania równowagi, często powodują pseudooptymalne układy, bez większego splątania krawędzi.
Być może zainteresuje Cię jedna z wielu dostępnych bibliotek rysunków wykresów. Pakiet Graphviz jest ogólnie całkiem niezły i obsługuje wiele różnych algorytmów dla różnych aplikacji do rysowania wykresów.
Czy pytasz o wykres * rysunek * - tj. Algorytm, który da dobry układ wierzchołków (z minimalnymi przejściami krawędzi itp.) Dla wykresu 'G (V, E)' ?? –
Tak, właśnie to robię – DropDropped