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++.
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.
A czy jest w ogóle coś takiego jak algorytm na zachłanne kolorowanie w grafie? Czy mam swój algorytm zrobić?
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.
Nie rozumiesz. Te wszystkie podane tam algorytmy są zachłanne, bo bazują na tym że wybierasz pierwszy kolor który ci pasuje.
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?