„A számítástudomány alapjai - Segédanyagok a vizsgához” változatai közötti eltérés
| 93. sor: | 93. sor: | ||
===Algoritmusok, eljárások és egyebek=== | ===Algoritmusok, eljárások és egyebek=== | ||
* Kruskal-algoritmus: minimális súlyú feszítőerdőt talál egy gráfban | * Kruskal-algoritmus: minimális súlyú feszítőerdőt talál egy gráfban | ||
*# Kiválasztjuk az összes él közül valamelyik legkisebb súlyút. | |||
*# Kiválasztjuk a maradék élek közül azt a legkisebb súlyút, ami a már kiválasztottakkal nem alkot kört. | |||
*# Addig ismételgetjük a 2. pontot, amíg minden pontját le nem fedtük a gráfnak. | |||
* Prüfer-kód felírása | * Prüfer-kód felírása | ||
*# Számozzuk meg a fa pontjait tetszőleges sorrendben. | |||
*# Töröljük le a fa elsőfokú pontjai közül azt, amelyiknek a legkisebb a száma és jegyezzük fel a szomszédja számát. | |||
*# Ezt ismételgessük addig, amíg csak tudjuk. | |||
==3. Euler-séta és -körséta (Euler-út, -kör) fogalma, szükséges és elégséges feltétel a létezésükre, Hamilton-kör és -út, szükséges, illetve, elégséges feltételek Hamilton-kör létezésére== | ==3. Euler-séta és -körséta (Euler-út, -kör) fogalma, szükséges és elégséges feltétel a létezésükre, Hamilton-kör és -út, szükséges, illetve, elégséges feltételek Hamilton-kör létezésére== | ||