slides over Grafen en BFS

Grafen en BFS
Mark Lekkerkerker
24 februari 2014
Grafen
Breadth-First Search
Toepassingen
1 Grafen
Wat is een graaf?
Hoe representeer je een graaf?
2 Breadth-First Search
Het Breadth-First Search Algoritme
Schillen
De BFS boom
3 Toepassingen
Bipartitie
Cykel zoeken
Samenhangend test
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
2 / 16
Grafen
Breadth-First Search
Toepassingen
Wat is een graaf?
Het abstracte concept van een graaf
I
Modelleert (binaire) relaties tussen objecten
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
3 / 16
Grafen
Breadth-First Search
Toepassingen
Wat is een graaf?
Het abstracte/visuele concept van een graaf
I
Modelleert (binaire) relaties tussen objecten
I
Punten (knopen) zijn objecten
I
Strepen zijn relaties
I
Geometrie niet belangrijk
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
3 / 16
Grafen
Breadth-First Search
Toepassingen
Geometrie niet belangrijk?!
Het gaat om de relatie!
A
B
C
B
N
A
E
O
F
K
I
D
E
L
G
H
Mark Lekkerkerker
J
L
J
=
M
G
F
O
K
C
I
Grafen en BFS
D
H
M
24 februari 2014
N
4 / 16
Grafen
Breadth-First Search
Toepassingen
Wat kun je modelleren?
De mogelijkheden zijn ongekend
I
Elektrische schakeling
I
Quoridor
I
Wie wie de hand schudt op een feestje
I
Internetverbindingen
I
Facebook vrienden
I
(Spoor)wegennet
I
Finite state automatons
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
5 / 16
Grafen
Breadth-First Search
Toepassingen
Uitbreidingen op de graaf
Je kunt het zo gek niet bedenken
I
Gerichte graaf
I
Gewogen graaf
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
6 / 16
Grafen
Breadth-First Search
Toepassingen
Wiskunde
Hoe beschrijf je een graaf?
I
Definitie van een graaf: G = (E , V )
I
m = |E | (aantal elementen in E )
I
n = |V | (aantal elementen in V )
I
Graad van een knoop
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
7 / 16
Grafen
Breadth-First Search
Toepassingen
Wiskunde
Hoe beschrijf je een graaf?
I
Definitie van een graaf: G = (E , V )
I
m = |E | (aantal elementen in E )
I
n = |V | (aantal elementen in V )
I
Graad van een knoop
I
Een (simpel) pad
I
Een (simpele) cykel
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
7 / 16
Grafen
Breadth-First Search
Toepassingen
Wiskunde
Hoe beschrijf je een graaf?
I
Definitie van een graaf: G = (E , V )
I
m = |E | (aantal elementen in E )
I
n = |V | (aantal elementen in V )
I
Graad van een knoop
I
Een (simpel) pad
I
Een (simpele) cykel
I
Samenhang (m ≥ n − 1)
I
Afstand tussen knopen x en y : δ(x, y )
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
7 / 16
Grafen
Breadth-First Search
Toepassingen
Representatie van grafen
Hoe slaat de computer ze op?
Matrixrepresentatie
0
1
0
0
0
0
1
0
0
Lijstrepresentatie
1 0 0 0 0 1 0 0
0 1 0 0 1 0 0 0
1 0 1 0 0 1 0 0
0 1 0 1 1 0 0 0
0 0 1 0 1 0 0 0
1 0 1 1 0 1 0 0
0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
Mark Lekkerkerker
Grafen en BFS
Adj[A] = {B, G }
Adj[B] = {A, C , F }
Adj[C ] = {B, D, G }
Adj[D] = {C , E , F }
Adj[E ] = {D, F }
Adj[F ] = {B, D, E , G }
Adj[G ] = {A, C , F }
Adj[X ] = {Y }
Adj[Y ] = {X }
24 februari 2014
8 / 16
Grafen
Breadth-First Search
Toepassingen
Representatie van grafen
Wat is de complexiteit van deze representaties?
Actie
Geheugen
Is xy een kant?
Geef een buur van x
Doe S voor all buren van x
Mark Lekkerkerker
Matrices
n2
O(1)
O(n)
n
Grafen en BFS
Lijsten
m (mits m > n)
O(n)
O(1)
graad
24 februari 2014
8 / 16
Grafen
Breadth-First Search
Toepassingen
Het Breadth-First Search Algoritme
Eigenschappen van BFS
I
Onderzoek een graaf
I
Exploreer dichtstbijzijnde knopen eerst
I
Heel algemeen
I
Vind het kortste pad in een ongewogen graaf
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
9 / 16
Grafen
Breadth-First Search
Toepassingen
Het Breadth-First Search Algoritme
Idee achter BFS
I
Onderzoek eerst de beginknoop.
I
Onderzoek dan eerst al zijn aangrenzende knopen.
I
Onderzoek dan al de aangrenzende knopen van deze knopen.
I
Onderzoek daarna alle aangrenzende knopen van deze knopen.
I
Herhaal dit principe...
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
9 / 16
Grafen
Breadth-First Search
Toepassingen
Het Breadth-First Search Algoritme
Bereken in O(n + m) een BFS boom!
Q ← lege Queue;
foreach v in V do color[v ] ← wit; d[v ] ← ∞; π[v ] ← nil;
color[s] ← grijs; d[s] ← 0;
Q.Enqueue(s);
while Q is niet leeg do
u ← Q.Dequeue();
foreach v in u.Adjacent do
if color[v ] = wit then
color[v ] ← grijs; d[v ] ← d[u] + 1; π[v ] ← u;
Q.Enqueue(v );
end
end
color[u] ← zwart;
end
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
9 / 16
Grafen
Breadth-First Search
Toepassingen
Schil de graaf door BFS
Eigenschappen van de BFS
I
Schil i bevat alle knopen x waarvoor geldt δ(x, s) = i.
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
10 / 16
Grafen
Breadth-First Search
Toepassingen
Schil de graaf door BFS
Eigenschappen van de BFS
I
Schil i bevat alle knopen x waarvoor geldt δ(x, s) = i.
I
Buur v van knoop u in schil i zit in schil i − 1, i of i + 1.
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
10 / 16
Grafen
Breadth-First Search
Toepassingen
Schil de graaf door BFS
Eigenschappen van de BFS
I
Schil i bevat alle knopen x waarvoor geldt δ(x, s) = i.
I
Buur v van knoop u in schil i zit in schil i − 1, i of i + 1.
I
Knoop u in schil i > 0 heeft tenminste 1 buur in schil i − 1.
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
10 / 16
Grafen
Breadth-First Search
Toepassingen
Schil de graaf door BFS
Eigenschappen van de BFS
I
Schil i bevat alle knopen x waarvoor geldt δ(x, s) = i.
I
Buur v van knoop u in schil i zit in schil i − 1, i of i + 1.
I
Knoop u in schil i > 0 heeft tenminste 1 buur in schil i − 1.
I
Als schil i geen knopen bevat, dan bevat schil i + 1 er ook geen.
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
10 / 16
Grafen
Breadth-First Search
Toepassingen
Schil de graaf door BFS
Eigenschappen van de BFS
I
Schil i bevat alle knopen x waarvoor geldt δ(x, s) = i.
I
Buur v van knoop u in schil i zit in schil i − 1, i of i + 1.
I
Knoop u in schil i > 0 heeft tenminste 1 buur in schil i − 1.
I
Als schil i geen knopen bevat, dan bevat schil i + 1 er ook geen.
I
Het algoritme exploreert de graaf schil voor schil
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
11 / 16
Grafen
Breadth-First Search
Toepassingen
Schil de graaf door BFS
Eigenschappen van de BFS
I
Schil i bevat alle knopen x waarvoor geldt δ(x, s) = i.
I
Buur v van knoop u in schil i zit in schil i − 1, i of i + 1.
I
Knoop u in schil i > 0 heeft tenminste 1 buur in schil i − 1.
I
Als schil i geen knopen bevat, dan bevat schil i + 1 er ook geen.
I
Het algoritme exploreert de graaf schil voor schil
I
Na terminatie: d[u] = δ(s, u).
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
11 / 16
Grafen
Breadth-First Search
Toepassingen
De BFS boom
De predecessor graaf, gemaakt door BFS
I
Voorganger-subgraaf gedefinieerd in π
I
Uitkomst π non-deterministisch
I
Niet elke BFS boom kan gemaakt worden door BFS
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
12 / 16
Grafen
Breadth-First Search
Toepassingen
Bipartitie
Deel de graaf op in twee
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
13 / 16
Grafen
Breadth-First Search
Toepassingen
Cykel zoeken
Zoek een cykel in een graaf
I
Door π kunnen we cykels detecteren.
I
Hierdoor kunnen we bekijken of een graaf een boom is
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
14 / 16
Grafen
Breadth-First Search
Toepassingen
Samenhangend test
Quoridor; is een locatie nog bereikbaar?
http://www.fupa.com/play/BoardGame-free-games/quoridor.html
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
15 / 16
Samenvatting
Wat hebben we vandaag behandeld?
I
Het concept van grafen
I
Computer representatie van grafen
I
Non determinisme door representatie
I
BFS
Mark Lekkerkerker
Grafen en BFS
24 februari 2014
16 / 16

Download Report