Definujte vzdálenost dvou vrcholů v neohodnoceném grafu. Dále popište algoritmus BFS a diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.

Vzdálenost dvou vrcholů v neohodnoceném grafu

• vzdálenost dvou vrcholů u, v N v grafu je délka nejkratší u-v-cesty

→ cesta - sekvence unikátních vrcholů a hran - v0, e1, v1, e2,… taková, že ei = {vi-1,v} a ei ∈ E(G)

⚠️ v cestě se neopakují vrcholy ani hrany ⚠️

Pokud jsou koncové vrcholy u,v mluvíme o této cestě jako o u-v-cestě

• délka této cesty je počet hran této sekvence

Jak najít vzdálenost dvou vrcholů v grafu (algoritmus BFS)

• prohledávání grafu do šířky

BFS(graf G, vrchol start, vrchol end)
{
	Pro každý vrchol v ∈ V(G):
		stav(v) = nenalezený
		D(v) := undefined
	
	Q := fronta obsahující vrchol start
	stav(start) = otevřený
	D(s) = 0

	Dokud je fronta Q neprázdná
	{
		v = Q[0];

		Pro všechny sousedy w vrcholu v:
			Pokud stav(w) = nenalezený
				stav(w) = otevřený
				D(w) := D(v) + 1
				P(w) := v
				Přidej w na konec fronty Q

			stav(v) = uzavřený
			Vrať (D,P)
	}

BFS fáze a hladiny