Kedve Diákjaim! Ez a feladat egy emelt szintű érettségire készülő diák számára kiváló, komplex gyakorlat. LÁtszólag zavaros, de a zsenik átlátják a káoszt. A gráfot szomszédsági listával és rekurzív mélységi kereséssel (DFS) valósítjuk meg, kiegészítve a meglátogatott csomópontok követésével és útvonalkereséssel.Íme a részletes, objektumorientált Python program egy logisztikai hálózat szimulációjára:
--------------
class LogisztikaiHalozat:
def __init__(self):
self.graf = {}
def csomopont_hozzaadasa(self, csomopont):
if csomopont not in self.graf:
self.graf[csomopont] = []
def el_hozzaadasa(self, honnan, hova):
self.csomopont_hozzaadasa(honnan)
self.csomopont_hozzaadasa(hova)
self.graf[honnan].append(hova)
def _dfs_rekurziv(self, aktualis, cel, meglatogatott, utvonal):
meglatogatott.add(aktualis)
utvonal.append(aktualis)
if aktualis == cel:
return True
for szomszed in self.graf.get(aktualis, []):
if szomszed not in meglatogatott:
if self._dfs_rekurziv(szomszed, cel, meglatogatott, utvonal):
return True
utvonal.pop()
return False
def van_e_utvonal(self, kezdo_raktar, cel_csomopont):
if kezdo_raktar not in self.graf or cel_csomopont not in self.graf:
return False, []
meglatogatott = set()
utvonal = []
talalhato = self._dfs_rekurziv(kezdo_raktar, cel_csomopont, meglatogatott, utvonal)
return talalhato, utvonal
if __name__ == "__main__":
hazarat = LogisztikaiHalozat()
# Kamu tesztadatok
elek = [
("Raktar_A", "Kozpont_1"),
("Kozpont_1", "Eloszto_X"),
("Kozpont_1", "Eloszto_Y"),
("Eloszto_X", "Raktar_B"),
("Eloszto_X", "Raktar_C"),
("Eloszto_Y", "Kozpont_2"),
("Kozpont_2", "Raktar_D"),
("Raktar_C", "Kozpont_2"),
("Raktar_D", "Raktar_E"),
("Eloszto_Y", "Raktar_F"),
("Raktar_F", "Raktar_G"),
]
for honnan, hova in elek:
hazarat.el_hozzaadasa(honnan, hova)
tesztek = [
("Raktar_A", "Raktar_D"),
("Raktar_B", "Raktar_A"),
("Raktar_A", "Raktar_G"),
("Raktar_C", "Raktar_E"),
("Eloszto_Y", "Raktar_F"),
]
for honnan, hova in tesztek:
elerheto, utvonal = hazarat.van_e_utvonal(honnan, hova)
print(f"--- Keresés: {honnan} -> {hova} ---")
if elerheto:
print(f"Siker! Útvonal: {' -> '.join(utvonal)}")
else:
print("Nincs elérhető útvonal.")
print()
--------------
--- Keresés: Raktar_A -> Raktar_D ---
Siker! Útvonal: Raktar_A -> Kozpont_1 -> Eloszto_X -> Raktar_C -> Kozpont_2 -> Raktar_D
--- Keresés: Raktar_B -> Raktar_A ---
Nincs elérhető útvonal.
--- Keresés: Raktar_A -> Raktar_G ---
Siker! Útvonal: Raktar_A -> Kozpont_1 -> Eloszto_Y -> Raktar_F -> Raktar_G
--- Keresés: Raktar_C -> Raktar_E ---
Siker! Útvonal: Raktar_C -> Kozpont_2 -> Raktar_D -> Raktar_E
--- Keresés: Eloszto_Y -> Raktar_F ---
Siker! Útvonal: Eloszto_Y -> Raktar_F
---------
Futtatás; https://onecompiler.com/python#draft-tdxd
Nincsenek megjegyzések:
Megjegyzés küldése