algorytm wykresu, jeśli wykres jest podłączony, dwustronny, ma cykl i jest drzewem

Question

Przy próbie pracy z wykresami napisałem kod, ale bez powodzenia:/!!

chciałam stworzył coś, która odbędzie dane na wykresie i sprawdzić, czy jest on: podłączonego 1- 2- 3- posiada dwustronny cykl 4- jest drzewem

więc zastanawiałem się na przykład, czy można to zapisać, aby odczytać dane wykresu z pliku .txt, który wykona powyższe testy?

użycie prostego formatu list krawędzi jest dla niego właściwym rozwiązaniem?

Twoja pomoc jest doceniana, jeśli możesz dać mi link do przeczytania o tym, jak wykonać to zadanie lub o uruchomieniu kodu !!

dzięki: D

Answer 1

sprawdzić, czy to jest:

1. połączony

dla tego jednego, próby przemierzać cały wykres z jednego punktu i zobacz jeśli ci się uda. Zarówno przejście z pierwszą na głębokość, jak i pierwsza na szerokość są tutaj dopuszczalne. Algorytm ten zostanie podzielony węzła do komponentów:

znaku

• wszystkich węzłów jako nieodwiedzonych
• dla każdego węzła c, jeśli węzeł jest nieodwiedzonych
  • utworzyć nowy pusty zbiór węzłów bieżącego składnika
  • skolejkowania tego węzła do przechodzenia
  • natomiast istnieje węzeł t skolejkowany
    • usunąć ten nod e z kolejki
    • znak każdy nieodwiedzonych sąsiad jako otwarty i enqueue go do przechodzenia
    • Oznacz ten węzeł jako ruch
    • dodać tego węzła do bieżącego składnika
  • zamknąć bieżący element i dodać go do zestawu składników

Jeśli istnieje tylko jeden składnik, na wykresie jest podłączony.

Jeśli używana jest kolejka, algorytm jest wyszukiwaniem po raz pierwszy. Jeśli stos jest używany, algorytm jest wyszukiwaniem na początku głębi. Każda inna kolekcja z operacjami push i pop-any zrobi. Szczególnie interesujący jest stos wywołań: zastąp "przechodzenie do traversal" przez "przechodzenie rekursywnie"

W przypadku grafów skierowanych istnieją dwie powiązane koncepcje: Graf skierowany jest słabo połączony, ponieważ jest połączony z pominięciem wszystkich kierunków krawędzi. Graf ukierunkowany jest silnie połączony, ponieważ każdy węzeł jest osiągalny z każdego węzła.Aby przetestować silną łączność, wystarczy sprawdzić, czy każdy węzeł jest osiągalny z pierwszego węzła, używając tylko przednich krawędzi, a każdy węzeł jest osiągalny z pierwszego węzła tylko z tylnymi krawędziami (pierwszy węzeł jest osiągalny z każdego węzła).

1. dwudzielny

wykres jest dwudzielna IFF jest bicolorable. Spróbuj przypisać bicoloring, a jeśli ci się nie uda, wykres nie jest dwudzielny. Można to uwzględnić w poprzednim algorytmie: za każdym razem, gdy oznaczysz węzeł jako otwarty, przypisz mu kolor, w przeciwieństwie do koloru przypisanego do jego sąsiada t. Gdy sąsiad t jest już otwarty, sprawdź jego kolor. Jeśli jego kolor jest taki sam jak w przypadku t, nie ma bicoloru.

1. ma cykl

Ten jest prosty: jeśli obserwować dowolny węzeł, który jest już otwarty, istnieje cykl. Zwróć uwagę, że każdy wykres bez cyklu jest dwudzielny.

Na wykreślonych wykresach wykryje to obecność nieukierunkowanego cyklu. Aby wykryć obecność skierowanych cykli, stosuje się następującą (topologiczna sortowania) Algorytm:

• gdy nie jest węzłem z indegree zero
  • dodać węzeł topologicznej rodzaju (nie ma znaczenia dla wykrywania cykli)
  • usunąć węzeł z wykresu
• czy nadal jest jakakolwiek węzeł wykresie
  • wykres zawiera skierowaną Cycl mi. Nie topologiczna rodzaj istnieje na tym wykresie
• inny
  • wykres nie zawiera skierowaną cyklu (jest acykliczny). Generowany wygenerowany topologizm jest prawidłowy.

1. drzewa

undirected wykres jest drzewem, wtedy i tylko wtedy gdy jest podłączony i nie zawiera cyklu.

Kierowany wykres to drzewo zrootowane, w którym nie ma żadnych nieukierunkowanych cykli i istnieje tylko jeden wierzchołek z indegree zerowym (tylko jeden root). Ponadto, skierowany wykres jest drzewem zrootowanym, w którym jest połączony, nie ma żadnych niepokierunkowanych cykli, a każdy węzeł z outdegree o wartości zero ma jednoznacznie co najwyżej jeden (każdy zlew jest liścia).