Algorytm teorii grafów dla minimalnie łączących obszarów ze wspólnymi granicami

Question

Mam ważony wykres wielu "zagród zwierząt" z każdym pisakiem mającym co najmniej 3 krawędzie/punkty i co najmniej dwa pióra. Muszę wymyślić minimalne ważone krawędzie do usunięcia, aby połączyć wszystkie pióra (można je połączyć, usuwając zewnętrzne krawędzie, które nie są połączone z innymi piórami).

Czy ktoś może polecić algorytm lub proces, z którym mógłbym podejść do znalezienia minimalnych ścian ważonych do usunięcia. Myślałem o algorytmie Prima, ale nie jestem do końca pewny, jak mogę to zastosować.

Jest to problem, S4 na http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

I nie chcesz odpowiedzieć tylko jakiś kierunek, w jaki sposób podejść to

Answer 1

Jesteś we właściwym kierunku.

modelu problem jako undirected wykresu G=(V,E) gdzie V = { all pens }, E = { (u,v) | there is a wall between u and v } z w((u,v)) = cost of wall between u and v

aby „połączyć wszystkie długopisy” - rzeczywiście szukasz podgrafu: G'=(V,E') tak, że sub wykres G' zostaną połączone [ Między co dwoma węzłami istnieje ścieżka, a koszt ścian w E 'jest minimalny.

Aby uzyskać to przy minimalnych kosztach - szukasz Minimum Spanning Tree. [Łatwo zauważyć, że rzeczywiście potrzebujesz drzewa - ponieważ każda dodatkowa krawędź po utworzeniu drzewa jest zbędna i może zostać usunięta bez szkody dla połączenia z wykresem - lub w przypadku problemu - możesz przywrócić jedną ścianę, a pisaki będą pozostawać w kontakcie]

dwóch możliwych algorytmów, które będzie Ci MST są Prim i Kruskal