Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

6.8. Feladatok

6.8. Feladatok

  1. A Prim algoritmust használva határozzunk meg egy minimális feszítőfát az alábbi hálózatban! Induljunk ki az 1-es csúcsból! Minden élt csak egy helyen adunk meg a szomszédsági listában, zárójelben az él hossza (súlya) áll. Hány él alkotja a kapott minimális feszítőfát? Melyik csúcs a szülője a 6-os csúcsnak a kapott minimális feszítőfában?

  2. Adott egy digráf az 1, 2, 3, 4, 5, 6 csúcspontokkal az alábbi szomszédsági listával. Az 1-es csúcspontból kiindulva végezzünk el egy szélességi keresést! Hány él alkotja az eljárás által létrehozott szélességi fát? Mennyi a megtalált csúcsokba vezető legrövidebb utak összhossza?