Eilė ir stekas gauna savo darbą

Ketvirtoje pamokoje pastatei eilę ir steką. Penktoje parodei, kad rekursija ir atskiras stekas yra tas pats algoritmas.

Abi tos pamokos baigėsi pažadu. Ketvirtoji:

Pakeisk eilę steku ir gausi paiešką į gylį — teisingą programą, atsakančią į kitą klausimą. Abi pastatysi 14 pamokoje.

Štai ta pamoka. Ir eilė su steku čia ne iliustruoja — jos dirba.

Grafas, kurį nagrinėsi

Bibliotekos tinklas „skaitytojai taip pat skolinosi": viršūnė — knyga, briauna jungia dvi knygas, kurias kas nors pasiskolino vieną po kitos.

Tokio tinklo forma nėra atsitiktinė. Skaitytojas skolinasi eilę knygų, tad kiekvienas skaitymo pėdsakas yra grandinė; sankryžos atsiranda tik ten, kur du skaitytojai pasirinko tą pačią knygą.

Ilgos grandinės, retos sankryžos — lygiai tokia pat forma kaip viešojo transporto tinklas. Todėl aštuntame žingsnyje transit bus palyginimas, o ne analogija.

Vienintelis skirtumas tarp dviejų paieškų

BFS ir DFS yra ta pati programa. Abi turi rinkinį dar neaplankytų viršūnių, abi ima iš jo po vieną, abi sudeda kaimynus atgal.

Skiriasi vienas dalykas: iš kurio galo imama.

	iš kur ima	kas tai yra
BFS	iš priekio	eilė (4 pamoka)
DFS	iš galo	stekas (4 pamoka)

Dvi eilutės kodo. Ir dėl to jos atsako į skirtingus klausimus.

Spėk prieš skaitydamas toliau

Abi paieškos randa kelią, jei kelias yra. Abi teisingos.

Ar DFS rastas kelias bus toks pat trumpas kaip BFS rastas? O jei ne — kiek ilgesnis: procentais, kartais, ar dar kitaip?

Užsirašyk atsakymą. Penktame žingsnyje pamatuosi, ir skaičius greičiausiai bus didesnis, negu norėsi rašyti.