• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Najlepsza reprezentacja grafu dla tego programu to...

0 głosów
169 wizyt
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ź

0 głosów
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 93 wizyt
+1 głos
1 odpowiedź 986 wizyt
pytanie zadane 11 maja 2015 w C i C++ przez keresmi Użytkownik (770 p.)
0 głosów
2 odpowiedzi 256 wizyt
pytanie zadane 21 października 2015 w C i C++ przez szmq Pasjonat (22,820 p.)

88,720 zapytań

137,332 odpowiedzi

306,819 komentarzy

58,907 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...