Algorytm obliczania domknięcia przechodniego grafu skierowanego.

Odpowiedz Nowy wątek
2019-06-05 23:33
0

Cześć, problem jak w tytule.
Na bazie algorytmu Floyda-Warshalla opisać algorytm obliczania domknięcia przechodniego grafu skierowanego.
Na wejsciu jest graf skierowany G=(V,E) o p wierzchołkach, bez f. wagowej. Wierzchołki to kolejne liczby całkowite V={1,...,p}. Zbiór krawędzi to macierz T(p x p) taka, że (v_i, v_j) należą do E wtedy i tylko wtedy, gdy T(i,j)=TRUE, w przeciwnym wypadku T(i,j)=FALSE.
Algorytm ma skonstruować macierz S taką, że S(i,j) = TRUE wtedy i tylko wtedy, gdy w grafie G istnieje ścieżka z v_i do v_j.

Problem dość skomplikowany. W takim stopniu, że nawet nie wiem jak się za to zabrać. Czy potrafiłby ktoś napisać pseudokod, lub coś podobnego. Przynajmniej jakiś schemat jak taki algorytm mógłby wyglądać, bo chciałbym dobrze to zrozumieć. Pozdrawiam

Napisz to po angielsku: " opisać algorytm obliczania domknięcia przechodniego grafu skierowanego", co to jest? - lion137 2019-06-05 23:37
transitive closure of a directed graph - Norbert Dąbrowski 2019-06-05 23:41

Pozostało 580 znaków

2019-06-06 05:42
1

Nie nazwałbym tego klasycznego problemu skomplikowanym, w szczególności że gotowców jest pełno:
https://www.geeksforgeeks.org/transitive-closure-of-a-graph/


#Dżunior React Devloper wanna be#

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0