From ff2a3c568eae2311a522a583aaa0922898393176 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 24 May 2011 14:59:51 +0200 Subject: [PATCH] Oziveni starych prednasek o DFS+BFS a Dijkstrovi. Nutno predelat. --- 2009/3-dfs/3-dfs.tex => 3-grafy/3-grafy.tex | 4 ++-- {2009/3-dfs => 3-grafy}/Makefile | 2 +- {2009/3-dfs => 3-grafy}/img1_stvorec.eps | 0 {2009/3-dfs => 3-grafy}/img2_dfs.eps | 0 {2009/3-dfs => 3-grafy}/img3_dfs.eps | 0 {2009/3-dfs => 3-grafy}/img4_susedia.eps | 0 {2009/3-dfs => 3-grafy}/img5_dfso.eps | 0 {2009/3-dfs => 3-grafy}/img7_hrany.eps | 0 {2009/3-dfs => 3-grafy}/imgn_nei.eps | 0 {2009/3-dfs => 3-grafy}/imgn_o4.eps | 0 {2009/3-dfs => 3-grafy}/praseci-graf.eps | Bin .../11-dijkstra.tex => 6-dijkstra/6-dijkstra.tex | 0 {2007/11-dijkstra => 6-dijkstra}/Makefile | 2 +- all/Makefile | 2 +- 14 files changed, 5 insertions(+), 5 deletions(-) rename 2009/3-dfs/3-dfs.tex => 3-grafy/3-grafy.tex (98%) rename {2009/3-dfs => 3-grafy}/Makefile (68%) rename {2009/3-dfs => 3-grafy}/img1_stvorec.eps (100%) rename {2009/3-dfs => 3-grafy}/img2_dfs.eps (100%) rename {2009/3-dfs => 3-grafy}/img3_dfs.eps (100%) rename {2009/3-dfs => 3-grafy}/img4_susedia.eps (100%) rename {2009/3-dfs => 3-grafy}/img5_dfso.eps (100%) rename {2009/3-dfs => 3-grafy}/img7_hrany.eps (100%) rename {2009/3-dfs => 3-grafy}/imgn_nei.eps (100%) rename {2009/3-dfs => 3-grafy}/imgn_o4.eps (100%) rename {2009/3-dfs => 3-grafy}/praseci-graf.eps (100%) rename 2007/11-dijkstra/11-dijkstra.tex => 6-dijkstra/6-dijkstra.tex (100%) rename {2007/11-dijkstra => 6-dijkstra}/Makefile (61%) diff --git a/2009/3-dfs/3-dfs.tex b/3-grafy/3-grafy.tex similarity index 98% rename from 2009/3-dfs/3-dfs.tex rename to 3-grafy/3-grafy.tex index b183ac4..796f6a4 100644 --- a/2009/3-dfs/3-dfs.tex +++ b/3-grafy/3-grafy.tex @@ -1,12 +1,12 @@ \input ../lecnotes.tex -\prednaska{3}{Prohledání do~¹íøky a do~hloubky}{()} +\prednaska{3}{Prohledání do~¹íøky a do~hloubky}{} \h{Prohledání do~¹íøky (BFS) {\I Breadth-First Search} } Jde o grafový algoritmus, který postupnì prochází v¹echny vrcholy v~dané komponentì souvislosti. Algoritmus nejprve projde v¹echny sousedy poèáteèního vrcholu, poté sousedy sousedù, atd\dots -Díky tomuto zpùsobu procházení se nìkdy té¾ nazývá \uv{\I algoritmus vlny }, nebo» se z~poèáteèního vrcholu ¹íøí pomyslná vlna, která v~ka¾dém kroku nalezne v¹echny uzly, které mají od~poèáteèního vrcholu stejnou vzdálenost. Algoritmus se tedy skvìle hodí napøíklad pro hledání nejkra¹í cesty mezi dvìma vrcholy v~grafu. +Díky tomuto zpùsobu procházení se nìkdy té¾ nazývá \uv{\I algoritmus vlny}, nebo» se z~poèáteèního vrcholu ¹íøí pomyslná vlna, která v~ka¾dém kroku nalezne v¹echny uzly, které mají od~poèáteèního vrcholu stejnou vzdálenost. Algoritmus se tedy skvìle hodí napøíklad pro hledání nejkra¹í cesty mezi dvìma vrcholy v~grafu. \figure{praseci-graf.eps}{Praseèí graf}{55mm} diff --git a/2009/3-dfs/Makefile b/3-grafy/Makefile similarity index 68% rename from 2009/3-dfs/Makefile rename to 3-grafy/Makefile index 62ff1bc..6337daa 100644 --- a/2009/3-dfs/Makefile +++ b/3-grafy/Makefile @@ -1,3 +1,3 @@ -P=3-dfs +P=3-grafy include ../Makerules diff --git a/2009/3-dfs/img1_stvorec.eps b/3-grafy/img1_stvorec.eps similarity index 100% rename from 2009/3-dfs/img1_stvorec.eps rename to 3-grafy/img1_stvorec.eps diff --git a/2009/3-dfs/img2_dfs.eps b/3-grafy/img2_dfs.eps similarity index 100% rename from 2009/3-dfs/img2_dfs.eps rename to 3-grafy/img2_dfs.eps diff --git a/2009/3-dfs/img3_dfs.eps b/3-grafy/img3_dfs.eps similarity index 100% rename from 2009/3-dfs/img3_dfs.eps rename to 3-grafy/img3_dfs.eps diff --git a/2009/3-dfs/img4_susedia.eps b/3-grafy/img4_susedia.eps similarity index 100% rename from 2009/3-dfs/img4_susedia.eps rename to 3-grafy/img4_susedia.eps diff --git a/2009/3-dfs/img5_dfso.eps b/3-grafy/img5_dfso.eps similarity index 100% rename from 2009/3-dfs/img5_dfso.eps rename to 3-grafy/img5_dfso.eps diff --git a/2009/3-dfs/img7_hrany.eps b/3-grafy/img7_hrany.eps similarity index 100% rename from 2009/3-dfs/img7_hrany.eps rename to 3-grafy/img7_hrany.eps diff --git a/2009/3-dfs/imgn_nei.eps b/3-grafy/imgn_nei.eps similarity index 100% rename from 2009/3-dfs/imgn_nei.eps rename to 3-grafy/imgn_nei.eps diff --git a/2009/3-dfs/imgn_o4.eps b/3-grafy/imgn_o4.eps similarity index 100% rename from 2009/3-dfs/imgn_o4.eps rename to 3-grafy/imgn_o4.eps diff --git a/2009/3-dfs/praseci-graf.eps b/3-grafy/praseci-graf.eps similarity index 100% rename from 2009/3-dfs/praseci-graf.eps rename to 3-grafy/praseci-graf.eps diff --git a/2007/11-dijkstra/11-dijkstra.tex b/6-dijkstra/6-dijkstra.tex similarity index 100% rename from 2007/11-dijkstra/11-dijkstra.tex rename to 6-dijkstra/6-dijkstra.tex diff --git a/2007/11-dijkstra/Makefile b/6-dijkstra/Makefile similarity index 61% rename from 2007/11-dijkstra/Makefile rename to 6-dijkstra/Makefile index a8acb25..31c4b79 100644 --- a/2007/11-dijkstra/Makefile +++ b/6-dijkstra/Makefile @@ -1,3 +1,3 @@ -P=11-dijkstra +P=6-dijkstra include ../Makerules diff --git a/all/Makefile b/all/Makefile index c3b0fe3..9f596b5 100644 --- a/all/Makefile +++ b/all/Makefile @@ -1,5 +1,5 @@ P=ads -X:=$(shell for a in 1 2 5 7 8 9 ; do echo ../$$a-*/$$a-*.tex ; done) +X:=$(shell for a in 1 2 3 5 6 7 8 9 ; do echo ../$$a-*/$$a-*.tex ; done) %universe: all ChangeLog -- 2.39.2