Greedy Algorithms: City Network and Lazy Entrepreneur

Algorytmy minimalnego łączenia wybierają najkrótszą krawędź w grafie i następnie dodają kolejną najkrótszą krawędź, która nie tworzy cyklu.

Algorytm Kruskala wybiera najkrótszą krawędź w grafie, a algorytm Prima zaczyna od dowolnego wierzchołka i wybiera najkrótszą krawędź połączoną z tym wierzchołkiem.

Algorytmy minimalnego drzewa rozpinającego polegają na wybraniu najtańszej krawędzi i dodawaniu jej do drzewa, zwracając uwagę na to, aby nie doprowadzić do powstania cyklu. (correct)

Algorytmy zachłanne konstruują minimalne drzewo rozpinające krawędź po krawędzi, wybierając zawsze najkrótszą krawędź w grafie.

Algorytmy minimalnego łączenia

Algorytm Prima

Algorytm zachłanny

Algorytm Kruskala (correct)

Wybiera najkrótszą krawędź w grafie i następnie dodaje kolejną najkrótszą krawędź, która nie tworzy cyklu.

Wybiera najkrótszą krawędź w grafie, a następnie przemieszcza się do innego wierzchołka, wybierając kolejną najkrótszą krawędź połączoną z tym wierzchołkiem.

Wybiera dowolny wierzchołek, a następnie wybiera najkrótszą krawędź połączoną z tym wierzchołkiem. (correct)

Wybiera najkrótszą krawędź łączącą dowolny wierzchołek już dołączony, a następnie powtarza ten proces dopóki wszystkie wierzchołki nie zostaną połączone.

<p>Znalezienie (niecyklicznego) podzbioru T o minimalnej całkowitej wadze, łączącego wszystkie wierzchołki grafu.</p> Signup and view all the answers

<p>Suma wag wszystkich krawędzi grafu.</p> Signup and view all the answers