Logowanie

Najlepsza reprezentacja grafu dla tego programu to...

pytanie zadane 26 kwietnia 2015 w C i C++ przez keresmi Użytkownik (770 p.)

Cześć!

Zamierzam napisać program, który sprawdzałby czy dany graf jest spójny. Nigdy wcześniej nie korzystałem z grafów w programowaniu i chciałem się zapytać jaka reprezentacja grafu byłaby najbardziej optymalna dla tego problemu?

1 odpowiedź

odpowiedź 26 kwietnia 2015 przez bossik21 Mądrala (5,750 p.)

Tablica 2wymiarowa będzie idealna.

komentarz 26 kwietnia 2015 przez keresmi Użytkownik (770 p.)
edycja 26 kwietnia 2015 przez keresmi

A co ze złożonością pamięciową? Dla tablicy będzie to O(V^2). Osobiście myślalem o liście sąsiedztwa.

komentarz 14 maja 2015 przez Fulaphex Początkujący (470 p.)

Chyba lista sasiedztwa bedzie lepsza, wtedy w czasie O(m+n) gdzie m to liczba krawedzi a n liczba wierzcholkow mozna sprawdzic spojnosc bfsem lub dfsem.

Podobne pytania

0 głosów

0 odpowiedzi 500 wizyt

reprezentacja grafu nieskierowanego za pomocą wektora list

pytanie zadane 16 grudnia 2020 w C i C++ przez kiuyama Nowicjusz (190 p.)

+1 głos

1 odpowiedź 1,609 wizyt

algorytm na zbadanie stopnia spójności grafu

pytanie zadane 11 maja 2015 w C i C++ przez keresmi Użytkownik (770 p.)

0 głosów

0 odpowiedzi 122 wizyt

Implementacja ruchomych elementów grafu

pytanie zadane 14 listopada 2022 w HTML i CSS przez MacGyver Nowicjusz (120 p.)

...