•Graph = ( V, E ) •V
recursieve datastructuren
definities
vertices, nodes, objecten, knopen, punten
•E
college 13
edges, arcs, kanten, pijlen, lijnen verbinding tussen 2 knopen
•Voorbeelden graphs
steden en verbindingswegen objecten en inheritance relaties mensen en familiebanden het internet: computers en communicatiekanalen FSM ...
1
soorten
2
plaatjes
algemeen: een edge verbindt twee knopen
•a picture paints a 1000 words ...
d.w.z. E ⊆ P ( V x V ) of ( u, v ) ∈ E ⇒ u, v ∈ V
veel verschillende manieren van tekenen
•directed, digraph ( u, v ) is geordend ( b.v. eenrichtingsstraat, inheritance, .. ) kant van u naar v impliceert niet een kant van v naar u
Zutphen
Amsterdam
u heet origin, bron; v heet destination, doel
29
39
•undirected
Utrecht
( u, v ) is niet geordend, soms schrijf je { u, v }
58
48
( u, v ) ∈ E ⇒ ( v, u ) ∈ E door alles dubbel op te slaan te simuleren met directed
Den Bosch
•weighted er hangt een waarde aan een edge ( b.v. afstand, kosten, .. )
Arnhem 19
43
Nijmegen 59
•labelled Venlo
iedere knoop heeft unieke naam ( b.v. naam van stad, .. ) 3
4
1
meer definities
paden
•2 vertices are adjacent, buren, if they are endpoints of an edge •outgoing edges:
•pad, path rijtje knopen waarbij er steeds een kant is tussen opeenvolgende knopen
•cycle
all directed edges with node as origin
pad met zelfde begin en eindpunt
•outdegree, uitgraad: aantal outgoing edges •incoming edges:
•simple path iedere knoop maar één keer in het pad, bevat geen cycles
all directed edges with node as destination
•indegree, ingraad: aantal incoming edges •degree, graad: number of incident edges degree = indegree + outdegree
•directed path bevat alleen directed edges in de goede richting
•forest, bos graaf zonder cycles 5
6
verbonden
verschil met bomen
•een graaf is verbonden, connected, als
•boom
er 'n pad is tussen ieder paar knopen uit die graaf verbinding hoeft niet uniek te zijn er mogen cycles in zitten
acyclic graaf met tussen ieder paar knopen precies één cycle-vrij pad d.w.z. een samenhangend bos
•gerichte boom Amsterdam 39 Utrecht 48 Den Bosch
Zutphen 58 43
directed acyclic graph with a root er is één cyclevrij pad van de root naar iedere andere knoop indegree ( root ) = 0 indegree ( andere knoop ) = 1
29 Arnhem 19 Nijmegen
•een boom is dus een speciaal soort graaf
59 Venlo 7
8
2
subgraph
representaties •verschillende mogelijkheden
•graph H is subgraph van G indien
beste keuze hangt af van probleem directed graph is meestal het handigst undirected als directed in twee richtingen
H = ( VH, EH ) G = ( VG, EG ) VH ⊆ VG ∧ EH ⊆ EG iedere graaf is dus een subgraaf van zichzelf
•enkele mogelijkheden: als bomen als rijen van knopen en edges als verbindingsmatrix ...
•spanning subgraaf knopen gelijk, kanten deelverzameling VH = VG ∧ EH ⊆ EG net voldoende kanten om alle knopen te bereiken
•simple graph
•spanning tree een spanning subgraaf die boom is 9
voorbeelden representatie A
B
•met boom knopen A
B
E
D
+handig, hergebruik van bestaand dingen +uitgaande gerichte kanten prima als pointer te representeren •maar –lastig om alle knopen te bezoeken –soms zelfs onmogelijk
D C
•knopen en edges knopen = { A, B, C, D, E } edges = { (A,A), (A,B) , (B,D), (B,E) , (C,E), (D,E) , (E,B), (E,D) }
•verbindings matrix →naar ↓ van
10
graph met boomknopen
E
C
geen self-loop: edge van de vorm ( x, x ) iedere edge ( x, y ) hooguit één keer, niet meerdere directe wegen
A
B
C
D
E
A
1
1
0
0
1
B
0
0
0
1
1
C
0
0
0
0
1
D
0
0
0
0
1
E
0
1
0
1
0
– niet samenhangend – gericht naar beginpunt
–lastig om een bepaalde knoop te vinden •voor ‘n algemene graaf dus geen goed idee 11
12
3
graph met boomknopen 2
graph als rij van knopen en kanten
•problemen op te lossen met rij van kopen •vaak handiger om index in rij te gebruiken dan pointer •aantal knopen en max aantal kanten is vast
class Knoop { ... }; typedef int KnoopID; class Kant {public: KnoopID origin, dest; }; class Graph {public: Knoop knopen [ nKnopen ]; Kant kanten [ nKanten ]; };
typedef int KnoopID; nummertje tussen class Knoop 0 en nKnopen {public: KnoopID kanten [ maxOutDegree ]; int outDegree; }; lijsten lossen dit class Graph probleem op {public: Knoop knopen [ nKnopen ]; };
nummertje tussen 0 en nKnopen
•simpel, direct volgens theorie, grootte kan ook dynamisch •zoeken van kanten bij knoop is O ( nKanten )
aantal kanten dat echt bestaat
13
14
verbindingsmatrix
tabel met kanten
•geef knopen weer een nummertje •sla in matrix op of er een verbinding is
•sla per knoop de uitgaande edges op eenvoudig om uitgaande edges te vinden class Graph { KnoopID **edges; // eigenlijk KnoopID edges[maxv][maxd]; int *degree; // eigenlijk int degree [maxv]; int nedges, maxv, maxd; public: grootte dynamisch, maken met new Graph ( char filename [] );
bool edges [ nKnopen ] [ nKnopen ] ;
•lekker direct
kan ook gewicht zijn
maar meerdere directe wegen kan niet
•voor graph met weinig verbindingen inefficiënt b.v. kaart van Manhattan ( New York ) 15 avenues, 200 straten dus 3000 kruisingen en 6000 verbindingsstraten verbindingsmatrix van kruisingen: matrix met 9.000.000 elementen, meer dan factor 1000 te veel ! sparse matrix
void insertEdge ( int x, int y, bool directed ); friend ostream& operator << ( ostream& os, Graph& g ); };
15
16
4
algoritmen
MST: Minimum Spanning Tree
•veel bekende algoritmen voor graphen
•weighted graph: G = ( V, E ); E = ( v, u, W ) •zoek de goedkoopste manier om alle knopen te verbinden
graph traversal •Breadth-first search •Depth-first search •principe gelijk aan bomen, nu knopen kleuren om te zien waar je geweest bent
dit is natuurlijk een boom •uit een cycle kan een verbinding weg •alle knopen moeten verbonden worden, dus geen bos
kortste paden zoeken componenten bepalen ...
voorbeelden: kabel voor tv en internet, waterleiding,..
•twee standaard algoritmen Krukskal Prim ( of Prim-Jarník ) van ieder algoritme weer wat variaties
•sommige problemen nog niet (efficiënt) opgelost TSP: kortste pad dat alle knopen bezoekt
17
MST volgens Prim
18
MST volgens Prim 2 •altijd lokaal beste kiezen is een greedy algoritme
•kleur verbonden knopen, tree-knopen •begin op een vrij te kiezen knoop
hier werkt dat goed voorwaarde is wel dat het gewicht nooit negatief is
kleur die knoop er zijn nog geen verbindingen
•om efficiënt de goedkoopste verbinding te kunnen kiezen administreren we per knoop de goedkoopste verbinding
• while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
19
20
5
weighted graph struct Edge { KnoopID k; int w; };
edge toevoegen
structuur i.p.v. kaal KnoopID
class Graph { Edge **edges; int *degree; int nedges, maxv, maxd; leest graph uit file public: Graph ( char filename [ ] ); void insertEdge ( int x, int y, int w, bool directed=true ); friend ostream& operator << ( ostream& os, Graph& g ); friend KnoopID* prim ( Graph& g, KnoopID start, int& v, int& t ); };
void Graph :: insertEdge ( int x, int y, int v, bool directed ) { if ( degree [ x ] < maxd ) { edges [ x ] [ degree [ x ] ] . k = y; edges [ x ] [ degree [ x ] ] . w = v; degree [ x ] += 1; nedges += 1; if ( !directed && x != y) insertEdge ( y, x, v ); } else cout << "insertEdge(" << x << "," << y << "," << v << ") past niet meer\n"; }
21
22
afdrukken van graph
MST volgens Prim
•per knoop de edges •voor iedere edge destination en gewicht
• while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; soort dynamic programming }
ostream& operator << ( ostream& os, Graph& g ) { for ( int n=0; n
•gebruik rij voor kortste edge naar non-tree nodes •kleur knopen in boolean rij •functie Prim levert rij met ouders op geeft lengte en totaal gewicht via reference argumenten 23
24
6
voorbeeld Prim 0 9
10
4
4
knoop ouder afstand
5
1
11 2
1
2
5
6
7
6
3
0
1
1
0
2
2
0 9
8
7
0
2
2
5
6
6
3
7
8
9
1 0
2
2
3
9
4
10
6 7
9
8
1
1
5
8
7
while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
knoop ouder afstand
5
3
6
9
4
11
1
5
8
4
1
4 7
10
3
3
begin in knoop 1
voorbeeld Prim
8
while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
9
25
26
voorbeeld Prim 0 9
10
4
4
knoop ouder afstand
5
1
0 11
2
1
2
5
6
3
7
6
3
7
voorbeeld Prim
8
8
9 while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
1
1 2
0
1 0
1
9
2
3
3
4
10
4
4
knoop ouder afstand
5
1
0 11
2
1
2
5
6
3
7
5 6
10
5
6
3
8
8
7
9
8 9
while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
korter pad gevonden
27
1 0
2
1
3
2
4 7
1
1
2 3 10
5 6
5
7
6
8
7
9
8
28
7
voorbeeld Prim 0 9
10
4
4
knoop ouder afstand
5
1
0 11
2
1
2
5
6
3
7
6
3
voorbeeld Prim 1
1
0
2
1
2
3
2
3
4 7
8
0
1 9
8
7
9 while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
5
7
6
8
7
9
8
4
knoop ouder afstand
5
0 11
2
2
5
6
3
10 2
4
1
1
5 6
10
6
3
1
1
0
2
1
3
2
4 7
8
1 2 3 10
5
8
9 while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
6
2
5
7
3
6
8
7
9
8
29
30
voorbeeld Prim 0 9
10
4
4
knoop ouder afstand
5
1
0 11
2
1
2
5
6
3
7
6
3
voorbeeld Prim 1
1
0
2
1
2
3
2
3
4 7
8
8
9 while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
0
1 9
7
3
6
8
3
7
9
knoop ouder afstand
5
0
2
2
5
6
3
7 5
4
11
1
5 2
4
1
10
6
10
6
3
7
8
9 while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; } 31
1 0
2
1
3
2
4
8
8
1
1
2 3 10
5 6
2
5
7
3
6
8
3
7
9
3
8
32
8
voorbeeld Prim 0 9
10
4
knoop ouder afstand
4
5
1
0 11
2
1
2
5
6
3
7
6
3
7
voorbeeld Prim
8
8
9 while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
1
1
0
1 0
2
1
2
3
2
3
4
0
10
5
9
2
5
7
3
6
8
3
7
9
3
8
4
4
knoop ouder afstand
5
1
0 11
2
1
2
5
6
3
7
4
6
10
6
3
7
8
8
9 while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
eindelijk een afstand bekend
1
1
0
2
1
3
2
3
4
0
10
5
4
4
6
2
5
7
3
6
8
3
7
9
3
8
34
Prim in C++
Prim 2: edge toevoegen while ( ! intree [ v ] ) { intree [ v ] = true; totaal += dist [ v ];
KnoopID* prim ( Graph& g, KnoopID start, int& size, int& totaal ) { size = g.maxv; totaal = 0; bool
* intree
= new bool
[ size ];
* dist
= new int
[ size ];
KnoopID * parent
2
klaar !
33
int
1
= new KnoopID [ size ];
for ( int i=0; i<size; i+=1 ) { intree [ i ] = false; dist [ i ] = INF; parent [ i ] = -1; } KnoopID v = start; dist [ v ] = 0; .... 35
...
beste edge en ouder aanpassen
for ( int j=0; j
w ) { dist [ k ] = w; parent [ k ] = v; } } Dijkstra 36
9
Prim beste nieuwe edge zoeken int d = INF; for ( int n=0; n<size; n+=1 ) if ( ! intree [ n ] && dist [ n ] < d ) { d = dist [ n ]; v = n; }
greedy algoritmen
zoek kortste verbinding
•veel gebruikt om beste te zoeken •idee: kies dat wat lokaal het beste lijkt •altijd redenatie nodig waarom het werkt •tegenvoorbeeld: kortste pad van x naar y begin in x volg steeds de goedkoopste edge totdat we in y zijn
} return parent; }
A
3
zelfs als we cycles voorkomen werkt dit niet
7
1 3
X
Y
2
5
2
4
B
37
MST volgens Kruskal
38
voorbeeld kruskal
•geef iedere knoop z’n eigen cluster • while ( meer dan 1 cluster )
0 9
verbind 2 klusters via de goedkoopste edge
10
4
4
clusters
5
1
0 11
2
1
•ook dit is een greedy algoritme
2
5
6
3
7
6
3
1 2 3 4
7
8
8
9
5 6 7 8 9
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge } 39
40
10
voorbeeld kruskal 0 9
10
4
4
clusters
5
1
1
2
5
6
3
2
9
3
6
8
clusters
5
0,1,2
2
2
5
7
6
3
5 6
7
8
7 8
8
8
9
9
9
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge }
3 4
6
3
7
9
4
11
1
6
8
4
1
5 7
10
4
3
7
0
0,1 11
2
voorbeeld kruskal
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge } 41
42
voorbeeld kruskal 0 9
10
4
4
clusters
5
1 2
2
5
6
3
7
6
3
0
0,1,2,3 11
1
voorbeeld kruskal 4
9
5
8
8
4
4
clusters
5
1
0,1,2,3 11
2
1
6
2
5
6
3
7 7
10
7
8 9
6
3
4,5 6 7 8
7
8
9
8
9
9
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge }
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge } 43
44
11
voorbeeld kruskal 0 9
10
4
4
clusters
5
1
1
2
5
6
3
4,5
9
7
6
4
4
clusters
5
1
0,1,2,3,6,7 11
2
1
2
5
4,5 8
6
9
3
9 7
10
8
3
7
0
0,1,2,3,6 11
2
voorbeeld kruskal
7
8
8
6
3
7
8
8
9
9
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge }
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge } 45
46
voorbeeld kruskal 0 9
10
4
4
clusters
5
1
2
5
0
0,1,2,3,6,7,8 11
2
1
voorbeeld kruskal
6
4,5
9
9
10
6
3
4
clusters
5
1
0,1,2,3,6,7,8,9 11
2
1
3
7
4
2
5
4,5
6
3 7
7
8
8
6
3
7
8
8
9
9
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge }
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge } 47
48
12
voorbeeld kruskal 0 9
10
4
4
kortste pad clusters
5
1
•gegeven unweighted graph
0,1,2,3,4,5,6,7,8,9
wat is het kortste pad tussen 2 knopen breadth first search zal het netjes vinden
11 2
1
2
5
6
klaar !
•gegeven weigthed graph
3
7
6
3
7
kortste pad is niet meer goedkoopste pad Dijkstra’s algoritme: voeg steeds de de goedkoopste knoop toe bijna gelijk aan Prim’s algoritme
8
8
9
while ( meer dan 1 cluster ) { verbind 2 klusters via goedkoopste edge }
als de graph niet samenhangend is vind je zo wel alle componenten
•distance bevat de afstanden •pad vinden door parents te volgen
49
Dijkstra shortest path algorithm
50
Dijkstra in C++
•berekent kortste afstand tot wortel
while ( ! intree [ v ] ) { intree [ v ] = true; for ( int j=0; j dist [ v ] + w ) { dist [ k ] = dist [ v ] + w; parent [ k ] = v; } anders }
voor alle knopen in de graph
•dist [ u ] is afstand tot gekleurde knopen in het begin D [ v ] = 0 D [ u ] = ∞, voor u ≠ v als er geen direct pad is
•selecteer ongekleurde knoop met kleinste D [ u ] •pas afstand van alle buren van u aan: edge relaxation: verbeter gaandeweg de schatting if ( D[u] + W(u,z) < D[z] ) D[z] = D[u] + W(u,z) lijkt op dynamic programming
dan Prim
Prim 51
52
13
# knopen, max degree, #kanten
voorbeeld
• graph 10 6 11 011 122 233 454 265 376 387 398 039 0 4 10 3 5 11
0 9
10
4
4
5 11
2
1
2
5
6
3
7
6
3
7
0
1
1
1
# knopen, max degree, #kanten
knoop ouder afstand
8
8
1 0
2
1
2
3
2
3
4
0
10
5
4
4
6
2
5
7
3
6
8
3
7
9
3
8
•graph 10 6 11 011 122 233 454 265 376 387 398 039 0 4 10 3 5 11
9
pad van 3 naar 5 met gewicht 11
while ( er zijn ongekleurde knopen ) { zoek goedkoopste kant van gekleurde naar naar ongekleurde knoop; voeg verbinding toe aan boom; kleur destination; }
Prim
53
pad van 3 naar 5 met gewicht 11
voorbeeld • prim: De ouders, 1 is root 0: 1 1: -1 2: 1 3: 2 4: 0 5: 4 6: 2 7: 3 8: 3 9: 3 Totaal gewicht is 46
• Dijkstra: Afstanden vanaf 1 0: 1 1: 0 2: 2 3: 5 4: 11 5: 15 6: 7 7: 11 8: 12 9: 13
54
wat hebben we gedaan •graphen komen vaak voor enkele representaties en algoritmen
•representatie van graphen met pointers, verbindingen per knoop of matrix beste keuze hangt van doel en algoritme af
•enkele bekende algoritmen Prim, Kruskal, Dijkstra, Floyd, Ford-Fulkerson •er bestaan vele variaties
er is literatuur over nog veel meer algoritmen
•nauwelijks in dictaat of ons boek 55
14
