Zachłanne kolorowanie grafów

0

Witam
Mam projekt, w którym muszę napisać program, który ma demonstrować działanie algorytmu zachłanne kolorowanie grafów (+ możliwość wyboru sposobu tworzenia listy) w c/c++. Jednak co szukam coś w internecie, to nigdzie nie ma właśnie o zachłannym kolorowaniu grafów, a nie mogę się zabrać za pisanie jak nie wiem, jak ma wyglądać sama procedura. Wiem co to jest kolorowanie grafów i wiem co to są algorytmy zachłanne, jednak przydałby się jakiś pseudokod/kod w c (najlepiej) oraz wytłumaczenie działania algorytmu żebym mógł zacząć coś zrobić. E-book, na którym mam się opierać (5. "Optymalizacja dyskretna. Modele i metody kolorowania grafów", M. Kubale i in.) jest niedostępny online (A przynajmniej ja nie mogę go znaleźć) . Dlatego byłbym bardzo wdzięczny jakby ktoś nakierowałby mnie na jakieś źródło informacji o tym konkretnym algorytmie (kolorowanie zachłanne) lub najlepiej kod napisany w c, ew. c++.

0

Najogólniej chodzi o to ze odpalasz coś na zasadzie BFS i kolorujesz za pomocą: "pokoloruj na pierwszy kolor z listy na który możesz". Czyli przeglądasz listę kolorów sąsiadów i wybierasz najmniejszą liczbę której w tym zbiorze nie ma i na ten kolor kolorujesz.

0

A czy jest w ogóle coś takiego jak algorytm na zachłanne kolorowanie w grafie? Czy mam swój algorytm zrobić?

0

Czytałem już wcześniej stronę na wikipedi i algorytm.org, ale nie ma tam mowy o kolorowaniu zachłannym. Na Wikipedii są 3 algorytmy kolorowania grafów, ale żaden nie jest zachłanny. Chyba, że czegoś nie rozumiem.

0

Nie rozumiesz. Te wszystkie podane tam algorytmy są zachłanne, bo bazują na tym że wybierasz pierwszy kolor który ci pasuje.

0

Dzięki, teraz już zaczynam rozumieć.

(+ możliwość wyboru sposobu tworzenia listy) --> może tutaj chodzić o sposób zapisu grafu? poprzez macierz/listwa sąsiedztwa? czy o coś innego?

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