Prohledávání grafů - Historie editací

Acolade: kategorizace

2014-02-20T06:35:34Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:35
Řádka 1:		Řádka 1:
−
	== Barvení grafu ==		== Barvení grafu ==
	Pro přehlednost při procházení grafem jednostlivé vrcholy obarvujeme		Pro přehlednost při procházení grafem jednostlivé vrcholy obarvujeme
Řádka 43:		Řádka 42:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

Tester: /* Prohledávání do hloubky */

2011-08-26T08:29:22Z

Prohledávání do hloubky

← Starší verze		Verze z 26. 8. 2011, 08:29
Řádka 42:		Řádka 42:
	Jsou-li grafy orientovány, je vhodné začínat na vrcholu, do kterého nevede hrana, aby nedošlo ke zbytečnému roztržení grafu na komponenty		Jsou-li grafy orientovány, je vhodné začínat na vrcholu, do kterého nevede hrana, aby nedošlo ke zbytečnému roztržení grafu na komponenty

−	{{~~kiv-~~fav-bzinf}}	+	{{fav-kiv-bzinf}}

Tester: /* Prohledávání do hloubky */

2011-08-26T08:28:40Z

Prohledávání do hloubky

← Starší verze		Verze z 26. 8. 2011, 08:28
Řádka 41:		Řádka 41:

	Jsou-li grafy orientovány, je vhodné začínat na vrcholu, do kterého nevede hrana, aby nedošlo ke zbytečnému roztržení grafu na komponenty		Jsou-li grafy orientovány, je vhodné začínat na vrcholu, do kterého nevede hrana, aby nedošlo ke zbytečnému roztržení grafu na komponenty
		+
		+	{{kiv-fav-bzinf}}

Tester v 9. 8. 2011, 10:33

2011-08-09T10:33:11Z

← Starší verze		Verze z 9. 8. 2011, 10:33
Řádka 1:		Řádka 1:
−	Barvení grafu: Grafy je možné během průchodu obarvovat, tedy tak, že vrcholy nezpracované jsou bílé, ty které jsme navštívili obarvíme na šedo a ty které jsme navštívili a zpracovali obarvíme na černo. Progledávací algoritmy končí, pokud jsou všechny vrcholy černé nebo pokud nalezneme požadovaný vrchol

		+	== Barvení grafu ==
		+	Pro přehlednost při procházení grafem jednostlivé vrcholy obarvujeme

		+	* '''bílá''' - tento vrchol algoritmus ještě nezpracoval
		+	* '''šedá''' - vrchol byl navštíven, ale ještě se k němu budeme vracet
		+	* '''černá''' - vrchol je zpracován, už se k němu vracet nebudeme

−	== Do šírky ==	+	Na začátku jsou všechny vrcholy samozřejmě bílé a postupně během průchodu je teprve bravujeme.
		+
		+	Prohledávací algoritmus končí v případech, kdy:
		+	* nalezneme požadovaný vrchol
		+	* nebo jsou všechny vrcholy grafu obarvené na černo
		+
		+
		+	== Prohledávání do šírky ==
	(breadth-first search, BFS)		(breadth-first search, BFS)
−	~~fronta nejdriv vyberu a obarvim na cerno~~	+
		+	Realizace pomocí fronty
		+
	Vybereme počátecní vrchol, obarvíme na šedo a projdeme všechny jeho sousedy. Nenalezneme-li řešení, obarvíme počáteční vrchol na černo a pokračujeme výběrem každého z jeho sousedů a opet projdeme jejich sousedy, které obarvujeme. Sousedy zatím nevybíráme, zpracováváme nejprve vrcholy právě vybraného vrcholu tak dlouho, dokud tento není obarven na černo.		Vybereme počátecní vrchol, obarvíme na šedo a projdeme všechny jeho sousedy. Nenalezneme-li řešení, obarvíme počáteční vrchol na černo a pokračujeme výběrem každého z jeho sousedů a opet projdeme jejich sousedy, které obarvujeme. Sousedy zatím nevybíráme, zpracováváme nejprve vrcholy právě vybraného vrcholu tak dlouho, dokud tento není obarven na černo.
−	Lze také k vrcholům ukládat předchudce a pocet hran od pocátecního vrcholu, címž získáme (nejkratší) cestu k počátečnímu vrcholu a její délku. Prohledáním celého grafu získáme BFS strom. Implementace pomocí fronty, složitost O(\|H\| + \|V \|).

		+	Lze také k vrcholům ukládat předchudce a pocet hran od pocátecního vrcholu, címž získáme (nejkratší) cestu k počátečnímu vrcholu a její délku. Prohledáním celého grafu získáme BFS strom. Implementace pomocí fronty, složitost O(\|H\| + \|V\|).
		+
		+
		+	== Prohledávání do hloubky ==
		+	(depth-first search, DFS)
		+
		+	Realizace pomocí zásobníku
		+
		+	Z počátecního vrcholu jdeme do jeho prvního souseda, z něj do jeho prvního souseda atd., které obarvujeme na šedo. Vybíráme ze sousedů vrcholy, které jsou bílé, které okamžite barvíme na šedo. Pokud projdeme všechny vrcholy, obarvíme vrchol na černo. a vracíme se na šedý vrchol.
		+	Pokračujeme do nalezení hledaného vrcholu nebo prohledání všech.
		+
		+	Prohledáním celého grafu získáme DFS strom. Implementace rekurzí nebo zásobníkem, složitost O(\|H\|+\|V \|).

−	~~== Do hloubky ==~~
−	~~(depth-first search, DFS) zasobnik~~

−	Z pocátecního vrcholu jdeme do jeho prvního souseda, z něj do jeho prvního souseda atd., které obarvujeme na šedo. Vybíráme ze sousedů vrcholy, které jsou bílé, které okamžite barvíme na šedo. Pokud projdeme všechny vrcholy, obarvíme vrchol na černo. a vracíme se na šedý vrchol.
−	~~Pokračujeme do nalezení hledaného vrcholu nebo prohledání všech. Prohledáním celého grafu získáme DFS strom. Implementace rekurzí nebo zásobníkem, složitost O(\|H\|+\|V \|).~~

	Hrany orientovaného grafu: Stromové hrany (patrící do stromu, jejich směr je od výchozího vrcholu), Zpětné hrany (opačná hrana ke hraně stromové, vytváří malý cyklus, směr je do výchozího bodu), dopředné (nemusí ležet ve strome, ale její vyrcholy v něm leží, jakésy zkratky stromem) a križující (opacné k dopredným, nebo hrany mezi stromy lesa). Zpětné a křižující hrany indikují cykly v grafu.		Hrany orientovaného grafu: Stromové hrany (patrící do stromu, jejich směr je od výchozího vrcholu), Zpětné hrany (opačná hrana ke hraně stromové, vytváří malý cyklus, směr je do výchozího bodu), dopředné (nemusí ležet ve strome, ale její vyrcholy v něm leží, jakésy zkratky stromem) a križující (opacné k dopredným, nebo hrany mezi stromy lesa). Zpětné a křižující hrany indikují cykly v grafu.

Tester v 9. 8. 2011, 09:51

2011-08-09T09:51:20Z

← Starší verze		Verze z 9. 8. 2011, 09:51
Řádka 1:		Řádka 1:
	Barvení grafu: Grafy je možné během průchodu obarvovat, tedy tak, že vrcholy nezpracované jsou bílé, ty které jsme navštívili obarvíme na šedo a ty které jsme navštívili a zpracovali obarvíme na černo. Progledávací algoritmy končí, pokud jsou všechny vrcholy černé nebo pokud nalezneme požadovaný vrchol		Barvení grafu: Grafy je možné během průchodu obarvovat, tedy tak, že vrcholy nezpracované jsou bílé, ty které jsme navštívili obarvíme na šedo a ty které jsme navštívili a zpracovali obarvíme na černo. Progledávací algoritmy končí, pokud jsou všechny vrcholy černé nebo pokud nalezneme požadovaný vrchol

−	~~Hledání do~~ šírky (breadth-first search, BFS) fronta nejdriv vyberu a obarvim na cerno	+
		+
		+	== Do šírky ==
		+	(breadth-first search, BFS)
		+	fronta nejdriv vyberu a obarvim na cerno
	Vybereme počátecní vrchol, obarvíme na šedo a projdeme všechny jeho sousedy. Nenalezneme-li řešení, obarvíme počáteční vrchol na černo a pokračujeme výběrem každého z jeho sousedů a opet projdeme jejich sousedy, které obarvujeme. Sousedy zatím nevybíráme, zpracováváme nejprve vrcholy právě vybraného vrcholu tak dlouho, dokud tento není obarven na černo.		Vybereme počátecní vrchol, obarvíme na šedo a projdeme všechny jeho sousedy. Nenalezneme-li řešení, obarvíme počáteční vrchol na černo a pokračujeme výběrem každého z jeho sousedů a opet projdeme jejich sousedy, které obarvujeme. Sousedy zatím nevybíráme, zpracováváme nejprve vrcholy právě vybraného vrcholu tak dlouho, dokud tento není obarven na černo.
	Lze také k vrcholům ukládat předchudce a pocet hran od pocátecního vrcholu, címž získáme (nejkratší) cestu k počátečnímu vrcholu a její délku. Prohledáním celého grafu získáme BFS strom. Implementace pomocí fronty, složitost O(\|H\| + \|V \|).		Lze také k vrcholům ukládat předchudce a pocet hran od pocátecního vrcholu, címž získáme (nejkratší) cestu k počátečnímu vrcholu a její délku. Prohledáním celého grafu získáme BFS strom. Implementace pomocí fronty, složitost O(\|H\| + \|V \|).

−	Do hloubky (depth-first search, DFS) zasobnik	+
		+	== Do hloubky ==
		+	(depth-first search, DFS) zasobnik
		+
	Z pocátecního vrcholu jdeme do jeho prvního souseda, z něj do jeho prvního souseda atd., které obarvujeme na šedo. Vybíráme ze sousedů vrcholy, které jsou bílé, které okamžite barvíme na šedo. Pokud projdeme všechny vrcholy, obarvíme vrchol na černo. a vracíme se na šedý vrchol.		Z pocátecního vrcholu jdeme do jeho prvního souseda, z něj do jeho prvního souseda atd., které obarvujeme na šedo. Vybíráme ze sousedů vrcholy, které jsou bílé, které okamžite barvíme na šedo. Pokud projdeme všechny vrcholy, obarvíme vrchol na černo. a vracíme se na šedý vrchol.
	Pokračujeme do nalezení hledaného vrcholu nebo prohledání všech. Prohledáním celého grafu získáme DFS strom. Implementace rekurzí nebo zásobníkem, složitost O(\|H\|+\|V \|).		Pokračujeme do nalezení hledaného vrcholu nebo prohledání všech. Prohledáním celého grafu získáme DFS strom. Implementace rekurzí nebo zásobníkem, složitost O(\|H\|+\|V \|).

Tester: Založena nová stránka: Barvení grafu: Grafy je možné během průchodu obarvovat, tedy tak, že vrcholy nezpracované jsou bílé, ty které jsme navštívili obarvíme na šedo a ty které jsm...

2011-08-08T15:01:39Z

Založena nová stránka: Barvení grafu: Grafy je možné během průchodu obarvovat, tedy tak, že vrcholy nezpracované jsou bílé, ty které jsme navštívili obarvíme na šedo a ty které jsm...

Nová stránka

Barvení grafu: Grafy je možné během průchodu obarvovat, tedy tak, že vrcholy nezpracované jsou bílé, ty které jsme navštívili obarvíme na šedo a ty které jsme navštívili a zpracovali obarvíme na černo. Progledávací algoritmy končí, pokud jsou všechny vrcholy černé nebo pokud nalezneme požadovaný vrchol

Hledání do šírky (breadth-first search, BFS) fronta nejdriv vyberu a obarvim na cerno
Vybereme počátecní vrchol, obarvíme na šedo a projdeme všechny jeho sousedy. Nenalezneme-li řešení, obarvíme počáteční vrchol na černo a pokračujeme výběrem každého z jeho sousedů a opet projdeme jejich sousedy, které obarvujeme. Sousedy zatím nevybíráme, zpracováváme nejprve vrcholy právě vybraného vrcholu tak dlouho, dokud tento není obarven na černo.
Lze také k vrcholům ukládat předchudce a pocet hran od pocátecního vrcholu, címž získáme (nejkratší) cestu k počátečnímu vrcholu a její délku. Prohledáním celého grafu získáme BFS strom. Implementace pomocí fronty, složitost O(|H| + |V |).

Do hloubky (depth-first search, DFS) zasobnik
Z pocátecního vrcholu jdeme do jeho prvního souseda, z něj do jeho prvního souseda atd., které obarvujeme na šedo. Vybíráme ze sousedů vrcholy, které jsou bílé, které okamžite barvíme na šedo. Pokud projdeme všechny vrcholy, obarvíme vrchol na černo. a vracíme se na šedý vrchol.
Pokračujeme do nalezení hledaného vrcholu nebo prohledání všech. Prohledáním celého grafu získáme DFS strom. Implementace rekurzí nebo zásobníkem, složitost O(|H|+|V |).

Hrany orientovaného grafu: Stromové hrany (patrící do stromu, jejich směr je od výchozího vrcholu), Zpětné hrany (opačná hrana ke hraně stromové, vytváří malý cyklus, směr je do výchozího bodu), dopředné (nemusí ležet ve strome, ale její vyrcholy v něm leží, jakésy zkratky stromem) a križující (opacné k dopredným, nebo hrany mezi stromy lesa). Zpětné a křižující hrany indikují cykly v grafu.

Je-li graf rozdelen do nekolika izolovaných cástí, zbudou po prvním prohledávání bílé vrcholy. Mužeme vybrat jeden jako další pocátecní a znovu z neho spustit vyhledávání, prípadne postup opakovat, pokud zustanou opet bílé vrcholy. Získáme tím les stromů.

Jsou-li grafy orientovány, je vhodné začínat na vrcholu, do kterého nevede hrana, aby nedošlo ke zbytečnému roztržení grafu na komponenty