+ All Categories
Home > Documents > Průchod grafu do šířky

Průchod grafu do šířky

Date post: 05-Jan-2016
Category:
Upload: sitara
View: 44 times
Download: 0 times
Share this document with a friend
Description:
Modulární systém dalšího vzdělávání pedagogických pracovníků JmK v přírodních vědách a informatice CZ.1.07/1.3.10/02.0024. Průchod grafu do šířky. Průchod grafu do šířky. Průchod grafu do šířky. Způsob jak projít grafem z vybraného vrcholu, abychom postupně navštívili všechny jeho vrcholy - PowerPoint PPT Presentation
62
Modulární systém dalšího vzdělávání pedagogických pracovníků JmK v přírodních vědách a informatice CZ.1.07/1.3.10/02.0024 Průchod grafu do šířky
Transcript
Page 1: Průchod grafu do šířky

Modulární systém dalšího vzdělávání pedagogických pracovníků JmK v přírodních vědách a informatice CZ.1.07/1.3.10/02.0024

Průchod grafu do šířky

Page 2: Průchod grafu do šířky

Průchod grafu do šířky

Page 3: Průchod grafu do šířky

Průchod grafu do šířky

• Způsob jak projít grafem z vybraného vrcholu, abychom postupně navštívili všechny jeho vrcholy

• Procházíme zleva a „po patrech“ daného grafu• Pro naprogramování používáme frontu

Page 4: Průchod grafu do šířky

Průchod grafu do šířky

Page 5: Průchod grafu do šířky

Průchod grafu do šířky

Page 6: Průchod grafu do šířky

Průchod grafu do šířky

Page 7: Průchod grafu do šířky

Průchod grafu do šířky

Page 8: Průchod grafu do šířky

Průchod grafu do šířky

Page 9: Průchod grafu do šířky

Průchod grafu do šířky

Page 10: Průchod grafu do šířky

Průchod grafu do šířky

Page 11: Průchod grafu do šířky

Průchod grafu do šířky

Page 12: Průchod grafu do šířky

Průchod grafu do šířky

Page 13: Průchod grafu do šířky

Průchod grafu do šířky

Page 14: Průchod grafu do šířky

Průchod grafu do šířky

Page 15: Průchod grafu do šířky

Průchod grafu do šířky

Page 16: Průchod grafu do šířky

Průchod grafu do šířky

Page 17: Průchod grafu do šířky

Průchod grafu do šířky

Page 18: Průchod grafu do šířky

Průchod grafu do šířky

Page 19: Průchod grafu do šířky

Fronta

• Využívá se pro průchod do šířky• Má dvě základní funkce push a shift.• Push – vloží prvek na konec fronty• Shift – sejme prvek ze začátku fronty

Page 20: Průchod grafu do šířky

Push iniciálního prvku A do fronty

Page 21: Průchod grafu do šířky

Shift horního prvku fronty

Page 22: Průchod grafu do šířky

Push sousedů prvku A do fronty

Page 23: Průchod grafu do šířky

Shift horního prvku fronty

Page 24: Průchod grafu do šířky

Push sousedů prvku B do fronty

Page 25: Průchod grafu do šířky

Shift horního prvku fronty

Page 26: Průchod grafu do šířky

Push sousedů prvku C do fronty

Page 27: Průchod grafu do šířky

Shift horního prvku fronty

Page 28: Průchod grafu do šířky

Shift horního prvku fronty

Page 29: Průchod grafu do šířky

Shift horního prvku fronty

Page 30: Průchod grafu do šířky

Shift horního prvku fronty

Page 31: Průchod grafu do šířky

Na zamyšlenou

• Co se stane budou-li následníci uzlů propleteni mezi sebou?

• Jak implementovat frontu?• Jak si hlídat navštívenost vrcholů?• Kdy skončit prohledávání grafu?

Page 32: Průchod grafu do šířky

Průchod grafu do hloubky

Projekt učitelé

Page 33: Průchod grafu do šířky

Průchod grafu do hloubky

Page 34: Průchod grafu do šířky

Průchod grafu do hloubky

• Způsob jak projít grafem z vybraného vrcholu, abychom postupně navštívili všechny jeho vrcholy

• Postupně se „zanořujeme“ až na dno nejlevějšího ramene grafu

• Při programování používáme zásobník

Page 35: Průchod grafu do šířky

Průchod grafu do hloubky

Page 36: Průchod grafu do šířky

Průchod grafu do hloubky

Page 37: Průchod grafu do šířky

Průchod grafu do hloubky

Page 38: Průchod grafu do šířky

Průchod grafu do hloubky

Page 39: Průchod grafu do šířky

Průchod grafu do hloubky

Page 40: Průchod grafu do šířky

Průchod grafu do hloubky

Page 41: Průchod grafu do šířky

Průchod grafu do hloubky

Page 42: Průchod grafu do šířky

Průchod grafu do hloubky

Page 43: Průchod grafu do šířky

Průchod grafu do hloubky

Page 44: Průchod grafu do šířky

Průchod grafu do hloubky

Page 45: Průchod grafu do šířky

Průchod grafu do hloubky

Page 46: Průchod grafu do šířky

Průchod grafu do hloubky

Page 47: Průchod grafu do šířky

Průchod grafu do hloubky

Page 48: Průchod grafu do šířky

Průchod grafu do hloubky

Page 49: Průchod grafu do šířky

Průchod grafu do hloubky

Page 50: Průchod grafu do šířky

Zásobník

• Využívá se pro průchod do hloubky• Má dvě základní funkce push a pop.• Push – vloží prvek na vrchol zásobníku• Pop – sejme prvek z vrcholu zásobníku

Page 51: Průchod grafu do šířky

Push iniciálního prvku A na zásobník

Page 52: Průchod grafu do šířky

Pop horního prvku zásobníku

Page 53: Průchod grafu do šířky

Push sousedů prvku A na zásobník

Page 54: Průchod grafu do šířky

Pop horního prvku zásobníku

Page 55: Průchod grafu do šířky

Push sousedů prvku B na zásobník

Page 56: Průchod grafu do šířky

Pop horního prvku zásobníku

Page 57: Průchod grafu do šířky

Pop horního prvku zásobníku

Page 58: Průchod grafu do šířky

Pop horního prvku zásobníku

Page 59: Průchod grafu do šířky

Push sousedů prvku C na zásobník

Page 60: Průchod grafu do šířky

Pop horního prvku zásobníku

Page 61: Průchod grafu do šířky

Pop horního prvku zásobníku

Page 62: Průchod grafu do šířky

Na zamyšlenou

• Co se stane budou-li následníci uzlů propleteni mezi sebou?

• Pomocí jakých struktur implementovat zásobník?


Recommended