Praktické cvičenie: Prehľadávanie a usporiadanie grafu

Cieľ

Implementujte základné grafové algoritmy nad reprezentáciou grafu pomocou zoznamu susedov.

Študent si precvičí:

• reprezentáciu grafu cez adjacency list,
• rozdiel medzi orientovaným a neorientovaným grafom,
• BFS a hľadanie najkratšej cesty v neváženom grafe,
• DFS a množinu dosiahnuteľných vrcholov,
• komponenty súvislosti v neorientovanom grafe,
• topologické usporiadanie orientovaného acyklického grafu.

Zadanie

Vytvorte súbor solution.py a implementujte funkcie:

def build_graph(edges, directed=False):
    pass

def bfs_shortest_path(graph, start, goal):
    pass

def dfs_reachable(graph, start):
    pass

def connected_components(graph):
    pass

def topological_sort(graph):
    pass

Graf reprezentujte ako slovník:

{
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

Kľúč je vrchol grafu a hodnota je zoznam jeho susedov.

1. build_graph(edges, directed=False)

Funkcia dostane zoznam hrán:

edges = [
    ("A", "B"),
    ("A", "C"),
    ("B", "D"),
]

Vráti graf ako adjacency list.

Ak directed=False, graf je neorientovaný a hrana sa pridá oboma smermi:

build_graph([("A", "B"), ("A", "C")])
# {
#     "A": ["B", "C"],
#     "B": ["A"],
#     "C": ["A"],
# }

Ak directed=True, graf je orientovaný:

build_graph([("A", "B"), ("A", "C")], directed=True)
# {
#     "A": ["B", "C"],
#     "B": [],
#     "C": [],
# }

Požiadavky:

• každý vrchol, ktorý sa objaví v hrane, musí byť kľúčom v slovníku,
• zoznamy susedov vráťte zoradené, aby bol výstup deterministický,
• duplicitné hrany sa vo výsledku nemajú opakovať.

2. bfs_shortest_path(graph, start, goal)

Funkcia nájde najkratšiu cestu medzi vrcholmi start a goal v neváženom grafe.

Vráti:

• zoznam vrcholov tvoriacich najkratšiu cestu,
• alebo None, ak cesta neexistuje.

Príklad:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

bfs_shortest_path(graph, "A", "E")
# napr. ["A", "B", "D", "E"]

Ak existuje viac najkratších ciest, môže vrátiť ľubovoľnú z nich.

Požadovaná zložitosť:

• časová zložitosť O(V + E),
• pamäťová zložitosť O(V).

3. dfs_reachable(graph, start)

Funkcia vráti množinu všetkých vrcholov, ktoré sú dosiahnuteľné z vrcholu start.

Príklad:

graph = {
    "A": ["B"],
    "B": ["C"],
    "C": [],
    "X": ["Y"],
    "Y": [],
}

dfs_reachable(graph, "A")
# {"A", "B", "C"}

Ak start nie je v grafe, vráťte prázdnu množinu.

4. connected_components(graph)

Funkcia dostane neorientovaný graf a vráti jeho komponenty súvislosti.

Výstup má byť zoznam množín:

connected_components({
    "A": ["B"],
    "B": ["A"],
    "C": ["D"],
    "D": ["C"],
    "E": [],
})
# [{"A", "B"}, {"C", "D"}, {"E"}]

Poradie komponentov ani poradie vrcholov v komponentoch nie je dôležité.

Požadovaná zložitosť:

• časová zložitosť O(V + E),
• pamäťová zložitosť O(V).

5. topological_sort(graph)

Funkcia dostane orientovaný acyklický graf a vráti topologické usporiadanie vrcholov.

Pre každú hranu u -> v musí platiť, že u je vo výsledku pred v.

Príklad:

graph = {
    "cook": ["eat"],
    "shop": ["cook"],
    "eat": [],
}

topological_sort(graph)
# napr. ["shop", "cook", "eat"]

Ak graf obsahuje cyklus, funkcia má vyhodiť výnimku:

raise ValueError("graph contains a cycle")

Požiadavky:

• vrcholy, ktoré sa objavia iba v zoznamoch susedov, musia byť zahrnuté vo výsledku,
• ak existuje viac správnych topologických poradí, môže vrátiť ľubovoľné z nich.

Automatické hodnotenie

Automatické testy majú overovať správnosť výstupov a vlastnosti grafových algoritmov. Pri BFS a topologickom triedení netreba testovať presne jeden pevný výstup, pretože môže existovať viac správnych riešení.

Testy

import pytest

from solution import (
    build_graph,
    bfs_shortest_path,
    dfs_reachable,
    connected_components,
    topological_sort,
)

def normalize_components(components):
    return {frozenset(component) for component in components}

def assert_valid_path(graph, path, start, goal):
    assert path is not None
    assert path[0] == start
    assert path[-1] == goal

    for current_node, next_node in zip(path, path[1:]):
        assert next_node in graph[current_node]

def assert_topological_order(graph, order):
    all_nodes = set(graph)
    for neighbors in graph.values():
        all_nodes.update(neighbors)

    assert set(order) == all_nodes

    position = {node: index for index, node in enumerate(order)}

    for node, neighbors in graph.items():
        for neighbor in neighbors:
            assert position[node] < position[neighbor]

def test_build_undirected_graph():
    graph = build_graph([
        ("A", "B"),
        ("A", "C"),
        ("B", "D"),
        ("A", "B"),
    ])

    assert graph == {
        "A": ["B", "C"],
        "B": ["A", "D"],
        "C": ["A"],
        "D": ["B"],
    }

def test_build_directed_graph():
    graph = build_graph([
        ("A", "B"),
        ("A", "C"),
        ("B", "D"),
    ], directed=True)

    assert graph == {
        "A": ["B", "C"],
        "B": ["D"],
        "C": [],
        "D": [],
    }

def test_bfs_shortest_path():
    graph = build_graph([
        ("A", "B"),
        ("A", "C"),
        ("B", "D"),
        ("C", "D"),
        ("D", "E"),
        ("C", "F"),
    ])

    path = bfs_shortest_path(graph, "A", "E")

    assert_valid_path(graph, path, "A", "E")
    assert len(path) == 4

def test_bfs_no_path():
    graph = {
        "A": ["B"],
        "B": ["A"],
        "X": ["Y"],
        "Y": ["X"],
    }

    assert bfs_shortest_path(graph, "A", "Y") is None

def test_dfs_reachable():
    graph = {
        "A": ["B"],
        "B": ["C"],
        "C": [],
        "X": ["Y"],
        "Y": [],
    }

    assert dfs_reachable(graph, "A") == {"A", "B", "C"}
    assert dfs_reachable(graph, "missing") == set()

def test_connected_components():
    graph = {
        "A": ["B"],
        "B": ["A"],
        "C": ["D"],
        "D": ["C"],
        "E": [],
    }

    components = connected_components(graph)

    assert normalize_components(components) == {
        frozenset({"A", "B"}),
        frozenset({"C", "D"}),
        frozenset({"E"}),
    }

def test_topological_sort():
    graph = {
        "shop": ["cook"],
        "cook": ["eat"],
        "set_table": ["eat"],
        "eat": [],
    }

    order = topological_sort(graph)

    assert_topological_order(graph, order)

def test_topological_sort_includes_neighbor_only_nodes():
    graph = {
        "A": ["B"],
        "B": ["C"],
    }

    order = topological_sort(graph)

    assert_topological_order(graph, order)

def test_topological_sort_detects_cycle():
    graph = {
        "A": ["B"],
        "B": ["C"],
        "C": ["A"],
    }

    with pytest.raises(ValueError):
        topological_sort(graph)

Skryté testy

Skryté testy môžu overovať:

• prázdny graf,
• graf s jedným vrcholom,
• viacero rovnako krátkych ciest,
• graf s izolovanými vrcholmi,
• väčší graf s tisíckami vrcholov,
• duplicitné hrany v build_graph,
• cykly v orientovanom grafe.

Odporúčaná stratégia riešenia

• build_graph: použite slovník a množiny susedov, na konci premeňte množiny na zoradené zoznamy.
• bfs_shortest_path: použite collections.deque, množinu navštívených vrcholov a slovník predchodcov na rekonštrukciu cesty.
• dfs_reachable: použite rekurziu alebo zásobník; pri veľkých grafoch je bezpečnejší zásobník.
• connected_components: opakovane spúšťajte DFS/BFS z ešte nenavštíveného vrcholu.
• topological_sort: použite Kahn algoritmus cez vstupné stupne alebo DFS s detekciou cyklu.

Hodnotenie

Časť	Body
build_graph	3
bfs_shortest_path	4
dfs_reachable	2
connected_components	3
topological_sort	5
Detekcia cyklu v topologickom triedení	2
Čitateľnosť kódu a vhodné dátové štruktúry	1

Spolu: 20 bodov.

Bonus

Pridajte funkciu:

def dijkstra_shortest_path(graph, start, goal):
    pass

Vstupný graf má vážené hrany:

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("D", 5)],
    "C": [("B", 1), ("D", 8)],
    "D": [],
}

Funkcia vráti dvojicu:

(vzdialenost, cesta)

Napríklad:

dijkstra_shortest_path(graph, "A", "D")
# (8, ["A", "C", "B", "D"])

Použite prioritnú frontu cez heapq.

Previous Post Next Post