bredden först

Information about bredden först

Published on February 7, 2008

Author: Silvestre

Source: authorstream.com

Content

Bredden först i en oriktad graf:  Markera noden som besökt och lägg in den i kön. q = (A) Ta fram första elementet (A), q = ( ) Ta sedan fram grannmängden till A S = {B, F, E} Bredden först i en oriktad graf Slide2:  För var och en av grannarna S = {B, F, E}: B är inte besökt, besök B och lägg in B i kön q = (B) Slide3:  F är inte besökt, besök F och lägg in F i kön q = (B, F) För var och en av grannarna S = {B, F, E}: B är inte besökt, besök B och lägg in B i kön q = (B) Slide4:  E är inte besökt, besök E och lägg in E i kön q = (B, F, E) F är inte besökt, besök F och lägg in F i kön q = (B, F) För var och en av grannarna S = {B, F, E}: B är inte besökt, besök B och lägg in B i kön q = (B) Slide5:  q = (B, F, E), ta fram första elementet (B) q = (F, E) Ta sedan fram grannmängden till B S = {A, F, C} För var och en av grannarna: A och F är besökta Slide6:  q = (B, F, E), ta fram första elementet (B) q = (F, E) Ta sedan fram grannmängden till B S = {A, F, C} För var och en av grannarna: A och F är besökta C är inte besökt, besök C och lägg in C i kön q = (F, E, C) Slide7:  q = (F, E, C), ta fram första elementet (F) q = (E, C) Ta sedan fram grannmängden till F S = {B, A, E, I} B, A, och E är besökta Slide8:  q = (F, E, C), ta fram första elementet (F) q = (E, C) Ta sedan fram grannmängden till F S = {B, A, E, I} B, A, och E är besökta I är inte besökt, besök I och lägg in I i kön q = (E, C, I) Slide9:  q = (E, C, I), ta fram första elementet (E) q = (C, I) Ta sedan fram grannmängden till E S = {A, F, I} För var och en av grannarna: Alla är besökta Slide10:  q = (C, I), ta fram första elementet (C) q = (I) Ta sedan fram grannmängden till C S = {B, G} För var och en av grannarna: B är besökt Slide11:  q = (C, I), ta fram första elementet (C) q = (I) Ta sedan fram grannmängden till C S = {B, G} För var och en av grannarna: B är besökt G är är inte besökt, besök G och lägg in G i kön q = (I, G) Slide12:  q = (I, G), ta fram första elementet (I) q = (G) Ta sedan fram grannmängden till I S = {E, F, J} E och F är besökta Slide13:  q = (I, G), ta fram första elementet (I) q = (G) Ta sedan fram grannmängden till I S = {E, F, J} E och F är besökta J är inte besökt, besök J och lägg in J i kön q = (G, J) Slide14:  q = (G, J), ta fram första elementet (G) q = (J) Ta sedan fram grannmängden till G S = {C, J, K} C och J är besökta Slide15:  q = (G, J), ta fram första elementet (G) q = (J) Ta sedan fram grannmängden till G S = {C, J, K} C och J är besökta K är inte besökt, besök K och lägg in K i kön q = (J, K) Slide16:  q =(J, K), ta fram första elementet (J) q = (K) Ta sedan fram grannmängden till J S = {I, G} Båda är besökta q = (K), ta fram första elementet (K) q = () Ta sedan fram grannmängden till K S = {G} Den är besökt. Nu är kön tom och algoritmen klar. Bredden först i en riktad graf:  Markera noden som besökt. q = (a), ta fram första elem ur q. Leta reda på grannarna = {c, e, d} Markera c som besökt. Stoppa in i kön q = (c) Markera e som besökt. Stoppa in i kön q = (c, e) Markera d som besökt. Stoppa in i kön q = (c, e, d) Ta första ur kön q = (e, d), c har inga grannar. Ta första ur kön q = (d). e har grannen = {b} Markera b som besökt. Stoppa in i kön q = (d, b) Ta första ur kön q = (b). Grannarna redan besökta. Ta första ur kön q = (). Grannarna redan besökta. Kön tom. Klart! Bredden först i en riktad graf

Related presentations


Other presentations created by Silvestre

Music and TOK
15. 01. 2008
0 views

Music and TOK

CAP08Lesson7
08. 05. 2008
0 views

CAP08Lesson7

VALENTINI WANKA 1165498491
07. 05. 2008
0 views

VALENTINI WANKA 1165498491

LSE Olympics slides
02. 05. 2008
0 views

LSE Olympics slides

2007525222912917
30. 04. 2008
0 views

2007525222912917

2005511164441155
24. 04. 2008
0 views

2005511164441155

2005317110534 9
22. 04. 2008
0 views

2005317110534 9

cooperation latvia
17. 04. 2008
0 views

cooperation latvia

B4 Qian 0215
15. 04. 2008
0 views

B4 Qian 0215

ZigBee Master
08. 04. 2008
0 views

ZigBee Master

Health Care Waste
18. 01. 2008
0 views

Health Care Waste

numbergendercase
11. 01. 2008
0 views

numbergendercase

cis bhs fhs foodborne 36957 7
12. 01. 2008
0 views

cis bhs fhs foodborne 36957 7

opinion
13. 01. 2008
0 views

opinion

ConsBeh Pt 2of3 PsyInfl
13. 01. 2008
0 views

ConsBeh Pt 2of3 PsyInfl

Child Protection
17. 01. 2008
0 views

Child Protection

biosummer04 yang keynote
17. 01. 2008
0 views

biosummer04 yang keynote

Satellite Testing
17. 01. 2008
0 views

Satellite Testing

COEL ExtRev
16. 01. 2008
0 views

COEL ExtRev

rabenhorstDRCS
19. 01. 2008
0 views

rabenhorstDRCS

Vermont Challenge poster Ding
21. 01. 2008
0 views

Vermont Challenge poster Ding

Cocoaine Chapter 6
22. 01. 2008
0 views

Cocoaine Chapter 6

AFEI NCO presentation
23. 01. 2008
0 views

AFEI NCO presentation

dubaitwo
24. 01. 2008
0 views

dubaitwo

Decision Making 10 06 p
05. 02. 2008
0 views

Decision Making 10 06 p

SCHLEGEL Thomas
12. 02. 2008
0 views

SCHLEGEL Thomas

crager xmastree1
22. 01. 2008
0 views

crager xmastree1

EDEA 630 Chapter 12 PowerPoint
28. 01. 2008
0 views

EDEA 630 Chapter 12 PowerPoint

Chapter 14
29. 01. 2008
0 views

Chapter 14

Activating Your Heart
29. 01. 2008
0 views

Activating Your Heart

Rome UPU PostCode StefanLindholm
17. 01. 2008
0 views

Rome UPU PostCode StefanLindholm

OS0607 YWANG what is good soil
22. 01. 2008
0 views

OS0607 YWANG what is good soil

CellPhones
30. 01. 2008
0 views

CellPhones

Keeoing Fit and Healthy
07. 02. 2008
0 views

Keeoing Fit and Healthy

Metamorphism
10. 01. 2008
0 views

Metamorphism

AW1
21. 01. 2008
0 views

AW1

MLA Documentation
14. 02. 2008
0 views

MLA Documentation

pps 308
14. 02. 2008
0 views

pps 308

Generic
22. 02. 2008
0 views

Generic

220 L13 Constantine
25. 02. 2008
0 views

220 L13 Constantine

48 The Hearts of the Children
08. 03. 2008
0 views

48 The Hearts of the Children

TZ Course and trip
14. 03. 2008
0 views

TZ Course and trip

injury guidelines
15. 03. 2008
0 views

injury guidelines

College Prep for HS Students
19. 03. 2008
0 views

College Prep for HS Students

bh us 02 smith biometric
24. 03. 2008
0 views

bh us 02 smith biometric

ATTC 1981 2007
16. 03. 2008
0 views

ATTC 1981 2007

lenovo
14. 04. 2008
0 views

lenovo

Peds Indonesia
14. 01. 2008
0 views

Peds Indonesia

Trish Skillman Presentation
16. 01. 2008
0 views

Trish Skillman Presentation

KKurani 2 14 07
08. 02. 2008
0 views

KKurani 2 14 07

condon
09. 01. 2008
0 views

condon

anthony russell
10. 01. 2008
0 views

anthony russell

Marketingweek2
04. 02. 2008
0 views

Marketingweek2

SGP03
28. 02. 2008
0 views

SGP03

HKPresentationJmSeig neur
10. 04. 2008
0 views

HKPresentationJmSeig neur

s3 Calzadilla Sarmiento
22. 01. 2008
0 views

s3 Calzadilla Sarmiento

Budzet Mon 2007 ang
07. 03. 2008
0 views

Budzet Mon 2007 ang

Villeneuve Can Rpt
24. 01. 2008
0 views

Villeneuve Can Rpt

GlobalIT Class4
31. 03. 2008
0 views

GlobalIT Class4

icongo a z funds raise
15. 02. 2008
0 views

icongo a z funds raise

habitat cluj
23. 01. 2008
0 views

habitat cluj

caringsocietypostKuu rne nov01
20. 02. 2008
0 views

caringsocietypostKuu rne nov01

MELL ASU 0708CCPOverview
10. 01. 2008
0 views

MELL ASU 0708CCPOverview

SETA 2 ETHICAL ATTITUDEs
17. 01. 2008
0 views

SETA 2 ETHICAL ATTITUDEs

Flex Benefit Coordinator
09. 01. 2008
0 views

Flex Benefit Coordinator

filmteaching
05. 02. 2008
0 views

filmteaching