[dedronek]

Ktoś z #programowanie ogarnia algorytm Prima dla grafu? Graf musi być nieskierowany, spójny. Mam odczytać listę krawędzi grafu z pliku, stworzyć listę sąsiedztwa grafu a następnie za pomocą tej listy sąsiedztwa i wektora kolorów zrobić algorytm na szukanie MDR.

Listę sąsiedztwa grafu już mam tylko teraz nie wiem jak ten algorytm na niej zrobić. Jak działa sam algorytm to wiem, ale ciężko mi ogarnąć jak zaznaczać np.: jak wybiorę następny wierzchołek do MDR, to zaznaczam go na czarno, ale on jest w kilku miejscach na liście sąsiedztwa :/

#algorytmy #informatyka #pomocy

[j.....0]

@dedronek: nie możesz po prostu zrobić sobie tablicy bool'i z informacją, czy dany wierzchołek był już wykorzystany?

[dedronek]

@jaksa0: tak, to rozumiem przez tablice kolorów, ewentualnie tablice visited[] . Dla listy sąsiedztwa jak wyżej rozpoczynając od wierzchołka 1, wybieram wierzchołek 4 bo jest najkrótsza droga i teraz ten wierzchołek 4 muszę dać, że odwiedzony ale nie tylko w pierwszym rzędzie, ale też w 6 i 8. Jak potem wyszukać krawędzie, które wychodzą z wierzchołków już odwiedzonych?

[j.....0]

@dedronek najprościej to sprawdzasz za każdym razem, czy wierzchołek znajduje się w tablicy visited, jeśli tak to go pomijasz. Oczywiście przy implementacji można to optymalizować.