grafs i arbres introducciómat.uab.cat/~alseda/matdoc/grafsdefimovs-2x2.pdf · grafs i arbres...

Grafs: Definicions i Algorismes Bàsics

Lluís AlsedàDepartament de Matemàtiques

Universitat Autònoma de Barcelonahttp://www.mat.uab.cat/~alseda

Versió 1.0 (2 d’abril de 2019)

Subjecte a una llicència Creative Commons Internacional de Reconeixement-NoComercial-CompartirIgual 4.0 (http://creativecommons.org/licenses/by-nc-sa/4.0/)

Continguts

Grafs i Arbres — Introducció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Grafs i Arbres — Definicions bàsiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Models de representació en memòria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Moviments en grafs — Introducció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Grafs amb arrel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Arbres i Arbres amb arrel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Moviments en arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Grafs amb arrel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Moviments en grafs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

breadth-first search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

depth-first search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Grafs i Arbres — Introducció

Índex

1 Introducció2 Una mica d’història

Lluís Alsedà Grafs: Definicions i Algorismes Bàsics Índex General 1/62

Grafs i Arbres — Introducció1 Un graf combinatori és un parell ordenat G = (V ,E ) de vèrtexs onodes V i un subconjunt E ⊂ V × V del producte cartesià V × V .

En el cas d’un graf no dirigit els elements d’E s’anomenen arestes iles parelles (v ,w) ∈ E es consideren sense ordre (és a dir, hi hauna aresta entre v ∈ V i w ∈ V quan (v ,w) ∈ E o (w , v) ∈ E ).En el cas d’un graf dirigit o orientat els elements d’E s’anomenenfletxes i les parelles (v ,w) ∈ E es consideren amb ordre (és a dir,hi ha una fletxa de v ∈ V a w ∈ V si i només si (v ,w) ∈ E ).

6 4 5

1

3 2

Exemple de graf no dirigit

1 2 5

3 4

Exemple de graf dirigit1http://en.wikipedia.org/wiki/Graph_theory


Grafs i Arbres — Introducció

Els grafs s’utilitzen per representar xarxes de comunicació,organitzacions de dades, dispositius de còmput, fluxos de càlcul, i,actualment, en totes les disciplines des de la lingüística a lasociologia i a la biologia, per posar una llista molt restringidad’exemples.

Per exemple, l’estructura d’enllaços d’un lloc web pot serrepresentada i estudiada mitjançant un graf dirigit, en el qual elsvèrtexs representen pàgines web i arestes dirigides representenenllaços d’una pàgina a una altra.


Una mica d’història

L’article escrit per Leonhard Euler sobre els set ponts deKönigsberg i publicat el 1736 és considerat com el primerdocument en la història de la teoria de grafs. En aquest treball,així com l’escrit per Vandermonde sobre el problema cavaller es vaestudiar la fórmula d’Euler que relaciona el nombre d’arestes,vèrtexs i cares d’un poliedre convex que està en l’origen de latopologia.

Un dels més famosos i estimulants problemes en la teoria de grafsés i ha estat el problema dels quatre colors:

És cert que qualsevol mapa dibuixat en el pla pot tenir les sevesregions acolorides amb quatre colors, de tal manera que duesregions que tenen una frontera comuna tenen diferents colors?


Grafs i Arbres — Definicions bàsiques

Índex

1 Connexió2 Ordre i mida3 València i grau4 Vèrtex terminal5 Camins i llaços


Definicions bàsiques — Connexió

ConnexióUn graf no dirigit és connex quan hi ha un camí entre cada parellde vèrtexs (és a dir, no hi ha vèrtexs inaccessibles).Un graf dirigit és connex quan ho és com a graf no dirigit.Exemple: Els dos grafs de la transparència 2 són connexos.


Definicions bàsiques — Ordre i mida

Ordre d’un grafL’ordre d’un graf és el nombre de vèrtexs |V |.Exemple: Els grafs de la transparència 2 tenen ordre 6 i 5respectivament.

Mida d’un grafLa mida d’un graf és el nombre d’arestes o fletxes |E |.Exemple: Els grafs de la transparència 2 tenen mida 7 i 6respectivament.


Definicions bàsiques — València i grau

Grau d’un vèrtexEl grau o valència és el nombre d’arestes que arriben o surten delvèrtex. Si una aresta connecta un vèrtex amb ell mateix comptadues vegades.Exemple: El vèrtex 4 del graf no dirigit de la transparència 2 tévalència 3 mentre que el vèrtex 5 del graf dirigit té valència 4.

Grau d’un vèrtex — Cas dirigitL’in-grau és el nombre d’arestes que arriben al vèrtex.L’out-grau és el nombre d’arestes que surten del vèrtex.Exemple: El vèrtex 5 del graf dirigit de la transparència 2 téin-grau 3 i out-grau 1.


Definicions bàsiques — Vèrtex terminal

Vèrtex terminalEls vèrtexs que pertanyen a una única aresta (és a dir els vèrtexsde valència 1) s’anomenen terminals o extrems.Exemple: L’únic vèrtex terminal del graf no dirigit de latransparència 2 és el vèrtex 6 i el del graf dirigit és el 4.


Definicions bàsiques — Camins i llaçosCamíUn camí és una successió d’arestes connectades linealment. Si elgraf és orientat el final d’una fletxa ha de ser l’inici de la següent.La llargada d’un camí és el nombre d’arestes que l’integren.Exemple: (6, 4, 3, 2, 1) és un camí de llargada 4 del graf no dirigitde la transparència 2 mentre que 2→ 3→ 1→ 2→ 5→ 5→ 5 ésun camí de llargada 6 del graf orientat.

Llaç o CircuitUn llaç o circuit és un camí tancat. És a dir que el final de ladarrera aresta és el principi de la primera.Exemple: (2, 3, 4, 5, 2) és un llaç de llargada 4 del graf no dirigitde la transparència 2 mentre que 2→ 3→ 1→ 2 és un llaç dellargada 3 del graf orientat.


Models de representació en memòria

Índex

1 Representacions en llista — Llista d’adjacència2 Representacions en llista — Llista d’incidència3 Representacions matricials — Matriu d’adjacència4 Representacions matricials — Matriu d’incidència


Models de representació en memòria

Hi ha diferents formes d’emmagatzemar grafs en memòria.

L’estructura de dades utilitzada depèn tant de l’estructura del grafcom de l’algoritme que s’utilitzi per a manipular el graf. Hi ha dostipus de representacions bàsiques: llistes i estructures matricials.

Per grafs dispersos (amb poques arestes) sovint es prefereix larepresentació com a llista ja que tenen requisits de memòria méspetits.


Representacions en llista — Llista d’adjacènciaLlista d’adjacènciaEls vèrtexs s’emmagatzemen com estructures i cada vèrtexemmagatzema una llista de vèrtexs adjacents. Aquesta estructurade dades permet l’emmagatzematge de dades addicionals sobre elsvèrtexs (per exemple latitud i longitud en els cas de dadesgeogràfiques).

Un exemple en C— El graf no dirigit de la transparència 2typedef struct {

char name;unsigned short nsucc;unsigned short successors[3];

} node_simple;node_simple GrafNO[6]={{’1’, 2, {1, 4}},

{’2’, 3, {0, 2, 4}},{’3’, 2, {1, 3}},{’4’, 3, {2, 4, 5}},{’5’, 3, {0, 1, 3}},{’6’, 1, {3}} };

Fet amb vectors de mida fixada.És més ineficient però més senzill.


Representacions en llista — Llista d’adjacènciaUn altre exemple: el graf no dirigit de la transparència 2typedef struct {

char name[11];double lat, lon;unsigned short nsucc;unsigned short successors[2];

} node;node llistanodes[5]={{"Casa", 41.4833, 2.1333, 1, {1}},

{"Plaça", 41.4667, 2.0833, 2, {2, 4}},{"Cruïlla", 41.3818, 2.1685, 1, {0}},{"Font", 40.41925, -3.69327, 1, {4}},{"Casa", 42.5, 1.6, 1, {4}}};

llistanodes[0] llistanodes[1] llistanodes[2] llistanodes[3] llistanodes[4]

name[11]=

Çasa"

lat=

41.4833

lon=

2.1333

nsucc=

1successors[2]=

{1}

name[11]=

"Plaça"

lat=

41.4667

lon=

2.0833

nsucc=

2successors[2]=

{2,4

}

name[11]=

Çruïlla"

lat=

41.3818

lon=

2.1685

nsucc=

1successors[2]=

{0}

name[11]=

"Fon

t"lat=

40.41925

lon=

-3.69327

nsucc=

1successors[2]=

{4}

name[11]=

Çasa"

lat=

42.5

lon=

1.6

nsucc=

1successors[2]=

{4}

Fet amb vectors de mida fixada.És més ineficient però més senzill.


Representacions en llista — Llista d’incidènciaLlista d’incidènciaVèrtexs i arestes s’emmagatzemen com a estructures. Cada vèrtexemmagatzema les seves arestes incidents, i cada arestaemmagatzema els seus vèrtexs incidents. Aquesta estructura dedades permet l’emmagatzematge de dades addicionals sobrevèrtexs i arestes.

Un exemple en C— El graf dirigit de la transparència 2typedef struct {

char name[11];double lat, lon;

} node;

node llnod[5] = {{"Casa", 41.4833, 2.1333},{"Plaça", 41.4667, 2.0833},{"Cruïlla", 41.3818, 2.1685},{"Font", 40.41925, -3.69327},{"Casa", 42.5, 1.6} };

typedef struct {unsigned short begin;unsigned short end;

} dir_edge;

unsigned short mida_graf = 6;

dir_edge arestes[mida_graf] = {{0, 1}, {1, 2}, {2, 0},{1, 4}, {3, 4}, {4, 4}

};


Representacions matricials — Matriu d’adjacència

Matriu d’adjacènciaÉs matriu (bidimensional — de dos índexs), en la qual les filesrepresenten els vèrtexs origen i les columnes representen vèrtexsfinals. El lloc i , j de la matriu diu el nombre de fletxes que van de ia j . En un graf no dirigit aquesta matriu és simètrica. Les dadesaddicionals sobre arestes i vèrtexs s’han d’emmagatzemar apart.

Una altra vegada el graf dirigit de la transparència 2

0 1 0 0 00 0 1 0 11 0 0 0 00 0 0 0 10 0 0 0 1


Representacions matricials — Matriu d’incidènciaMatriu d’incidènciaUna matriu booleana bidimensional, en la qual les files representenels vèrtexs i les columnes representen les arestes. Les entradesindiquen si el vèrtex en una fila és incident a l’aresta d’unacolumna. Per grafs dirigits +1 indica que el vèrtex és l’origen del’aresta i −1 indica que el vèrtex és el final de l’aresta.

Un cop més el graf dirigit de la transparència 2Les arestes estàn numerades com segueix:α1 = 1→ 2, α2 = 2→ 3, α3 = 3→ 1, α4 = 2→ 5, α5 = 4→ 5.

1 0 −1 0 0−1 1 0 1 00 −1 1 0 00 0 0 0 10 0 0 −1 −1

Notis que aquest graf noes pot representard’aquesta manera.L’aresta 5→ 5 no es potrepresentar.


Moviments en grafs — IntroduccióA diferència dels vectors, llistes enllaçades i altres estructures dedades lineals, que es poden recórrer de manera canònica en ordrelineal, els arbres i grafs poden travessar-se de diverses maneresessencialment diferents donat que no són linealment ordenats.

Travessar un graf implica una iteració sobre tots els nodes i, fixatun node, hi ha més d’un possible node següent (no som en unaestructura de dades lineal). Per tant, en un marc de computacióseqüencial calen algorismes i regles que determinin en cada casl’elecció del node següent i que regulin el tractament dels altresnodes adjacents (romanents) per a visitar-els posteriorment.

Bàsicament hi ha dues filosofies de moviments en grafs:En profunditat: l’elecció del node següent prioritzaincrementar la profunditat.Per nivells: l’elecció del node següent prioritza mantenir laprofunditat.


Moviments en grafs — IntroduccióDonat que un graf és una estructura de dades autoreferencial(definida recursivament), el recorregut es pot implementar demanera molt natural i clara per recursió (en aquest cas, els nodesdiferits s’emmagatzemen implícitament a la pila).Observacions/problemes de la noció de profunditat

No és una noció absoluta. Clarament depèn de quin és elnode origen.Com veurem, la definició és senzilla i canònica (independentdel recorregut realitzat) quan hi ha un camí únic entre el nodeorigen i cada un dels altres nodes.

El primer problema és fàcil de resoldre: solament cal concretarsempre quin és el node origen.El segon problema és més difícil de resoldre. Ho farem en duesetapes: inicialment tractarem el cas fàcil dels arbres (pelsquals, donats dos nodes, hi ha un únic camí que els uneix).Després serà més fàcil tractar el cas general d’un graf arbitrari.


Grafs amb arrel

Índex

1 Concretant el node origen2 Fulles i Vèrtexs de Ramificació


Grafs amb arrel — Concretant el node origenGrafs amb arrelUn graf s’anomena amb arrel si hi ha un vèrtex que n’ha estatdesignat (i que serà el node origen).

Un graf dirigit amb arrel:

1

2

3 5

4

Un graf no dirigit amb arrel:

1

5

2

4

36


Grafs amb arrel — Fulles i Vèrtexs de RamificacióFullaUna fulla d’un arbre amb arrel és qualsevol vèrtex terminal o devalència 1 que sigui diferent de l’arrel.

Vèrtex de RamificacióUn vèrtex de ramificació és qualsevol vèrtex de valència més granque dos que sigui diferent de l’arrel.

Exemple pels grafs amb arrel de la transparència 21Exemple pel graf dirigitEl vèrtex 4 és la única fulla.Els vèrtexs 2 i 5 són deramificació.

Exemple pel graf no dirigitEl vèrtex 6 és la única fulla.Els vèrtexs 2, 4 i 5 són deramificació.

Observació: La valència d’un vèrtex no depèn del node arrelPer tant, les fulles i els vèrtexs de ramificació d’un graf són independents delnode arrel exceptuant el propi node arrel (que abandona el seu caràcter de fullao node de ramificació en ser designat arrel).


Arbres i Arbres amb arrel

Índex

1 Arbres — Únicament arc-connexos2 Arbres amb arrel: Fixant el node origen3 Arbres amb arrel — Profunditat d’un vèrtex4 Arbres amb arrel — Profunditat de l’arbre5 Arbres amb arrel — Pares i Fills6 Arbres n-aris


Arbres 2 — Únicament arc-connexos

Definició d’ArbreUn arbre és un graf connex i sense llaços (circuits).

Equivalentment:Un arbre és un graf únicament arc-connex: Dos vèrtexsqualssevol estan connectats per un únic camí.

Propietats dels arbresAfegint una aresta qualsevol a unarbre (no orientat) es forma un llaç.Esborrant qualsevol aresta l’arbre esdesconnecta.Un arbre amb n vèrtexs téexactament n − 1 arestes (laCaracterística d’Euler és igual a 1).

Exemple: un arbre

2http://en.wikipedia.org/wiki/Tree_(graph_theory)Lluís Alsedà Grafs: Definicions i Algorismes Bàsics Índex General 24/62

Arbres amb arrel: Fixant el node origenArbres amb arrelUn arbre s’anomena amb arrel si hi ha un vèrtex que n’ha estatdesignat (i que serà el node origen).

Exemple: Un arbre amb arrel Exemple — Un arbre amb arrel:el node 1

1

2 3

4 5 6

7 8 9

Profunditat0

1

2

3

Exemple: Els vèrtexs 4, 7, 8 i 9 son fulles onodes terminals.Els vèrtexs 2 i 5 són nodes de ramificació.


Arbres amb arrel — Profunditat d’un vèrtex

Definició: Profunditat d’un vèrtexEn un arbre amb arrel la profunditat d’un vèrtex es defineix com ladistància d’aquest node a l’arrel.Distància: La distància entre dos nodes es mesura com la llargadade l’únic camí que els connecta (recordem que un arbre ésúnicament arc-connex).Òbviament la distància d’un node a ell mateix és 0.Nota: La profunditat de l’arrel és 0.

Exemple: Profunditats de l’arbre amb arrel de la transparència 25:

Profunditat 0 1 2 3

Vèrtexs

1 2 4 73 5 8

6 9

Exemple: La profunditat del node v = 51 −→ 2 −→ 5 és l’únic camí que uneixl’arrel amb el node 5 i aquest camí que téllargada 2.


Arbres amb arrel — Profunditat d’un vèrtexNota Important (recordatòria)Les profunditats dels vèrtexs d’unarbre amb arrel depènen de l’arrel.

Profunditats de l’exemple de la dreta(compareu amb l’exemple anterior)

Profunditat 0 1 2 3 4 5

Vèrtexs{

6 3 1 2 4 79 5 8

Observacions:Quan movem l’arrel del node 1 al node 6:

l’únic vèrtex que manté la profunditatés el 3.

Recordatori: Les fulles i els vèrtexsterminals no varien (donat que les duesarrels tenen valència 2).

Exemple: L’arbre de la pàgina 25amb el vèrtex 6 com a arrel

6

3 9

1

2

4 5

7 8

Profunditat0

1

2

3

4

5


Arbres amb arrelLa Profunditat com a ordenació de vèrtexsNota (explicitant un comentari anterior)

Un arbre amb arrel defineix un ordre parcial al conjunt de vèrtexsen la direcció creixent de profunditat (veure els arbres amb arrel deles transparències 25 i 27).L’arrel és el vèrtex més petit i les fulles són els elements maximals.


Arbres amb arrel — Profunditat de l’arbre

Definició: Profunditat de l’arbreLa profunditat d’un arbre amb arrel es defineix com la màximaprofunditat dels vèrtexs (com abans depèn de l’arrel escollida).

ExempleL’arbre amb arrel 1 de la transparència 25 té profunditat 3.El mateix arbre amb arrel 6 de la transparència 27 té profunditat 5.


Arbres amb arrel — Pares i FillsDefinició: pareDonat un arbre amb arrel i un vèrtex v de profunditat p > 0 (és adir diferent de l’arrel), el pare de v es defineix com l’únic vèrtex deprofunditat p − 1 adjacent a v . Equivalentment, el pare de v ésl’únic node de l’únic camí que connecta l’arrel amb v , que ésadjacent a v .Òbviament l’arrel no té pare (de fet és l’únic vèrtex que no té pare).

Exemple: Pares de l’arbre de la pàgina 25

vèrtexs 1 2 3 4 5 6 7 8 9pares – 1 1 2 2 3 5 5 6

Exemple: Pares de l’arbre de la pàgina 27

vèrtexs 1 2 3 4 5 6 7 8 9pares 3 1 6 2 2 – 5 5 6


Arbres amb arrel — Pares i FillsDefinició: fillSigui un arbre amb arrel i un vèrtex v de profunditat p ≥ 0. Unnode de profunditat p + 1 adjacent a v s’anomena fill de v .

Les fulles no tenen fills i són els únics vèrtexs que no tenen fills.Un vèrtex que no sigui una fulla pot tenir més d’un fill.

Exemple: Fills de l’arbre de la pàgina 25

vèrtexs 1 2 3 4 5 6 7 8 9

fills{ 2 4 6 – 7 9 – – –

3 5 8

Exemple: Fills de l’arbre de la pàgina 27

vèrtexs 1 2 3 4 5 6 7 8 9

fills{ 2 4 1 – 7 3 – – –

5 8 9


Arbres n-aris

Arbre n−ariUn arbre n−ari és un arbre amb arrel per al qual cada vèrtex técom a màxim n fills.Els arbres 2−aris s’anomenen binaris i els 3−aris s’anomenenternaris.

ExempleEls arbres amb arrel de les transparències 25 i 27 són arbres binaris.


Moviments en arbres

Índex

1 Profunditat: depth-first search — preordre2 Profunditat: depth-first search — enordre3 Profunditat: depth-first search — postordre4 Per nivells: breadth-first search


Moviments en arbres 3 en profunditat: depth-first searchpreordre

DescripcióEn aquest algorisme de cercaprimer es visita (llista) cada nodepel que es viatja. Seguidaments’avança cap al fill esquerre iquan es torni a passar, de pujada,per aquest node s’avançarà capal fill dret. Ordre de visita:

F, B, A, D, C, E, G, I, H

3https://en.wikipedia.org/wiki/Tree_traversalLluís Alsedà Grafs: Definicions i Algorismes Bàsics Índex General 34/62

Moviments en arbres en profunditat: depth-first searchpreordre — pseudocodi

Algorisme: preordre recursiuprocedure preordre(node)

if (node = null) thenreturn

end ifvisita(node)preordre(node.left)preordre(node.right)

end procedure

ComentariEl control inicial s’ha de fer perdetectar quan som a una fulla itallar la recursivitat ja que, enaquest cas, no podem baixar mésavall.

Algorisme: preordre iteratiuprocedure PreordreIteratiu(nodearrel)

s ← StackBuits.push(nodearrel)while (not s.EsBuit) do

node ← s.popvisita(node)if (node.right 6= null) then

s.push(node.right)end ifif (node.left 6= null) then

s.push(node.left)end if

end whileend procedure

ComentariS’entén que no fem trampa entrant una arrelnul·la.


Moviments en arbres en profunditat: depth-first searchenordre

DescripcióPrimer s’avança cap al fillesquerre de cada node pel que esviatja. Seguidament, quan estorna a passar, de pujada, peraquest node es visita (llista) is’avança cap al fill dret. Ordre de visita:

A, B, C, D, E, F, G, H, I


Moviments en arbres en profunditat: depth-first searchenordre — pseudocodi

Algorisme: enordre recursiuprocedure enordre(node)

if (node = null) thenreturn

end ifenordre(node.left)visita(node)enordre(node.right)

end procedure

Algorisme: enordre iteratiuprocedure EnordreIteratiu(nodearrel)

s ← StackBuitnode ← nodearrelwhile (true) do

if (node 6= null) thens.push(node)node ← node.left

elseif (s.EsBuit) then return; end ifnode ← s.popvisita(node)node ← node.right

end ifend while

end procedure


Moviments en arbres en profunditat: depth-first searchpostordre

DescripcióPrimer s’avança cap al fillesquerre de cada node pel que esviatja. Seguidament, quan estorna a passar, de pujada, peraquest node s’avança cap al filldret. Finalment, la terceravegada que es passa pel node, depujada provinent del fill dret, esvisita (llista) el node.

Ordre de visita:A, C, E, D, B, H, I, G, F


Moviments en arbres en profunditat: depth-first searchpostordre — pseudocodi

Algorisme: postordre iteratiuprocedure PostordreIteratiu(arrel)

s ← StackBuitv ← arrel; darrerV ← null;while (true) do

if (v 6= null) thens.push(v); v ← v.left;

elseif (s.EsBuit) then return; end ifpeekv ← s.peekif (peekv.right 6= null and darrerV 6= peekv.right) then

v ← peekv.rightelse

visita(peekv); darrerV ← s.pop;end if

end ifend while

end procedure

Algorisme:postordre recursiuprocedure postordre(v)

if (v = null) thenreturn

end ifpostordre(v.left)postordre(v.right)visita(v)

end procedure

peek mira la informa-ció de l’element superiorde la pila (el darrer queha entrat) però no treuaquest element de la pilacom fa pop.


Moviments en arbres per nivells:breadth-first search

DescripcióEs llisten els nodes pernivell de profunditat donatprioritat a l’esquerra.

Ordre de visita:F, B, G, A, D, I, C, E, H

Algorisme: breadth-first search (iteratiu)procedure BreadthFirstSearch(arrel)

q ← CuaBuidaq.encua(arrel)while (not q.EsBuida) do

node ← q.desencuavisita(node)if (node.left 6= null) then

q.encua(node.left)end ifif (node.right 6= null) then

q.encua(node.right)end if



Grafs amb arrel

Índex

1 Profunditat d’un vèrtex2 Exemple3 Propietats de la profunditat


Grafs amb arrel — Profunditat d’un vèrtexDefinició: Profunditat d’un vèrtexEn un graf amb arrel la profunditat d’un vèrtex es defineix com ladistància mínima de l’arrel al vèrtex seleccionat.Distància mínima:Donats dos vèrtexs α i β, la distància mínima d’α a β esmesura com la llargada més petita de tots els camins que vand’α a β (notis que, en un graf, hi pot haver més d’un d’aquestcamins — fins i tot hi pot haver més d’un camí de llargadamínima d’α a β).En un graf dirigit pot no haver-hi cap camí d’α a β. En aquestcas la distància d’α a β és ∞ per conveni.Òbviament la distància d’un node a ell mateix és 0.

Definició: Profunditat d’un graf amb arrelLa profunditat d’un graf amb arrel es defineix com la màximaprofunditat dels vèrtexs.


Grafs amb arrel — Exemple: profunditats de la pàgina 21Profunditats del graf (dirigit) del’esquerra

Profunditat 0 1 2 ∞

Vèrtexs{ 1 2 3 4

5La profunditat del graf es 2

Profunditats del graf (no dirigit)de la dreta

Profunditat 0 1 2 3

Vèrtexs{ 1 2 4 6

5 3La profunditat del graf es 3

Exemple: Càlcul de la profunditat del vèrtex 4 del graf (no dirigit)de la dreta de la transparència 21Molts camins van de l’arrel al node 4 (i no n’hi ha de més curts):

1 −→ 5 −→ 41 −→ 2 −→ 5 −→ 41 −→ 2 −→ 3 −→ 41 −→ 5 −→ 2 −→ 3 −→ 41→ 2→ 5→ 1→ 2→ 5→ 1→ 5→ 2→ 3→ 4

El de llargada més petita és 1 −→ 5 −→ 4, que té llargada 2.Lluís Alsedà Grafs: Definicions i Algorismes Bàsics Índex General 43/62

Grafs amb arrel — Propietats de la profunditat

De les definicions i exemples anteriors es dedueix:La profunditat de l’arrel és 0.Les profunditats dels vèrtexs d’un graf amb arrel depènen del’arrel.Per tant, la profunditat d’un graf amb arrel depèn de l’arrelescollida.

El calcul de la profunditat d’un graf amb arrel (i per tantde les profunditats de tots els seus vèrtexs) requereix elcàlcul de les distàncies mínimes (camins més curts) del’arrel a cada node.

En un graf amb arrel no dirigit i connex, la profunditat decada node està definida. No obstant, en un graf amb arreldirigit (encara que sigui connex) pot passar que hi hagi nodesamb profunditat infinita.


Moviments en grafs

Índex

1 Per nivells: breadth-first search — pseudocodi2 Per nivells: breadth-first search — Exemple en C3 El resultat — Observacions4 Arbre minimal d’expansió5 Per nivells: breadth-first search — pseudocodi — amb

memòria de pares6 Profunditat: depth-first search — pseudocodi7 Profunditat: depth-first search — Exemple en C


Moviments en grafs per nivells: breadth-first searchLa funció BFS per grafs en pseudocodi (amb dues millores)

Algorisme: breadth-first search per grafsprocedure BFS(graf G, ordre, arrel)

depth[ordre] ← inicialitzat a ∞ . Inicialment per controlar si un node ha estat vi-sitat o no. Millorat per calcular la profunditat.

depth[arrel] ← 0 . Arrel visitada ( 6=∞) i profunditat 0.q ← CuaBuida; q.encua(arrel); . Inicialització.while (not q.EsBuida) do

node ← q.desencua; visita(node);for i i ← 0, node.numadj-1 do . Per tractar un nombre arbitrari de nodes adjacents

(possiblement diferent) a cada node.adj ← node.successor[i]if (depth[adj] = ∞) then . L’i-èssim node adjacent no ha estat visitat

q.encua(adj)depth[adj] ← depth[node] + 1 . adj visitat ( 6=∞). Calculem la pro-

funditat a partir de la de node.end ifend for



Moviments en grafs per nivells: breadth-first searchEl programa

#include <stdio.h>

typedef struct {char name;double lat, lon;unsigned short nsucc;unsigned short successors[3];

} node;

void BFS(node *G, unsigned short ordre, unsigned short source);

void main (void) {node GrafO[5] = { {’1’, 41.4833, 2.1333, 1, {1}},

{’2’, 41.4667, 2.0833, 2, {2, 4}},{’3’, 41.3818, 2.1685, 1, {0}},{’4’, 40.41925, -3.69327, 1, {4}},{’5’, 42.5, 1.6, 1, {4}} };

node GrafNO[6] = { {’1’, 41.4833, 2.1333, 2, {1, 4}},{’2’, 41.4667, 2.0833, 3, {0, 2, 4}},{’3’, 41.3818, 2.1685, 2, {1, 3}},{’4’, 40.41925, -3.69327, 3, {2, 4, 5}},{’5’, 42.5, 1.6, 3, {0, 1, 3}},{’6’, 41.9842, 2.8239, 1, {3}} };

puts("\nDesplegament del graf orientat: arrel = 1\n"); BFS(GrafO, 5U, 0U);puts("\nDesplegament del graf orientat: arrel = 5\n"); BFS(GrafO, 5U, 4U);puts("\nDesplegament del graf no orientat: arrel = 1\n"); BFS(GrafNO, 6U, 0U);puts("\nDesplegament del graf no orientat: arrel = 6\n"); BFS(GrafNO, 6U, 5U);

}


Moviments en grafs per nivells: breadth-first searchEl resultat: Veure les observacions de les pàgines 43 i 44

Desplegament del graf orientat: arrel = 1----------------------------------------------------------Vertex 1: Profunditat = 0; Lat = 41.483300; Lon = 2.133300Vertex 2: Profunditat = 1; Lat = 41.466700; Lon = 2.083300Vertex 3: Profunditat = 2; Lat = 41.381800; Lon = 2.168500Vertex 5: Profunditat = 2; Lat = 42.500000; Lon = 1.600000

Desplegament del graf orientat: arrel = 5----------------------------------------------------------Vertex 5: Profunditat = 0; Lat = 42.500000; Lon = 1.600000

Desplegament del graf no orientat: arrel = 1----------------------------------------------------------Vertex 1: Profunditat = 0; Lat = 41.483300; Lon = 2.133300Vertex 2: Profunditat = 1; Lat = 41.466700; Lon = 2.083300Vertex 5: Profunditat = 1; Lat = 42.500000; Lon = 1.600000Vertex 3: Profunditat = 2; Lat = 41.381800; Lon = 2.168500Vertex 4: Profunditat = 2; Lat = 40.419250; Lon =-3.693270Vertex 6: Profunditat = 3; Lat = 41.984200; Lon = 2.823900

Desplegament del graf no orientat: arrel = 6----------------------------------------------------------Vertex 6: Profunditat = 0; Lat = 41.984200; Lon = 2.823900Vertex 4: Profunditat = 1; Lat = 40.419250; Lon =-3.693270Vertex 3: Profunditat = 2; Lat = 41.381800; Lon = 2.168500Vertex 5: Profunditat = 2; Lat = 42.500000; Lon = 1.600000Vertex 2: Profunditat = 3; Lat = 41.466700; Lon = 2.083300Vertex 1: Profunditat = 3; Lat = 41.483300; Lon = 2.133300

Desplegament delgraf no orientat: arrel = 1

1

5 2

4 3

6


Moviments en grafs per nivells: breadth-first searchObservacions sobre l’algorisme breadth-first search

Torna un dels camins mes curts de l’arrel a cada node del graf.Nota: Això NO és equivalent a dir que torna el camí mescurt entre dos nodes qualssevol de l’arbre.De fet, torna un arbre d’expansió minimal.

DefinicióUn arbre d’expansió minimal d’un graf connex és un arbred’expansió on cada camí que uneix l’arrel amb un vertex arbitrari vté llargada mínima entre tots els camins del graf que uneixen l’arreli v .

ExempleL’arbre d’expansió de la transparència anterior és el que quedamarcat en vermell.


Arbre d’expansióDefinicióUn arbre d’expansió (spanning tree, en anglès) d’un graf connex ésun subconjunt d’arestes del graf que és un arbre i connecta tots elsvèrtexs del graf.Observacions

Un graf no connex no té arbre d’expansió (ja que els arbres són connexos).Un graf pot tenir més d’un arbre d’expansió.Si totes les arestes d’un graf G són també arestes d’un arbre d’expansióT , llavors G és un arbre que coincideix amb T . És a dir, un arbre té unúnic arbre d’expansió que és ell mateix.Un arbre d’expansió d’un graf connex també es pot definir com unconjunt màxim d’arestes que no continguin cicles, o com un conjuntmínim d’arestes que connectin tots els vèrtexs.En particular, un graf connex sempre té un arbre d’expansió i aquest arbrees pot obtenir esborrant arestes de manera que cada operació d’esborraruna aresta trenqui un circuit (llaç).Exemple: Al graf de la transparència 48 s’obté l’arbre d’expansióesborrant les dues arestes negres.


Moviments en grafs per nivells: breadth-first search

Però com sabem quines són les arestes de l’arbre d’expansió?(notem que la funció BFS no ho diu).

Amb una versió revisada de l’algorisme que recorda “el pare” decada node (és a dir com hem arribat al node en calcular el camímés curt).


Moviments en grafs per nivells: breadth-first searchLa funció BFS per grafs en amb memòria de pares

Algorisme: breadth-first search per grafs amb memòria de paresprocedure BFS(graf G, ordre, arrel)

depth[ordre] ← inicialitzat a ∞ . Inicialment per controlar si un node ha estat vi-sitat o no. Millorat per calcular la profunditat.

pare[ordre] ← . Declaraciódepth[arrel] ← 0; pare[arrel] ← ∞; . Arrel visitada (6= ∞) i profunditat 0.

A més l’arrel no té pare.q ← CuaBuida; q.encua(arrel); . Inicialització.while (not q.EsBuida) do

node ← q.desencua; visita(node);for i i ← 0, node.numadj-1 do . Per tractar un nombre arbitrari de nodes adjacents

(possiblement diferent) a cada node.adj ← node.successor[i]if (depth[adj] = ∞) then . L’i-èssim node adjacent no ha estat visitat

q.encua(adj)depth[adj] ← depth[node] + 1 . adj visitat (6=∞). Calculem la pro-

funditat a partir de la de node.pare[adj] ← node . Recordem el pare. Es el node per on hi hem arribat.

end ifend for



Moviments en grafs per nivells: breadth-first searchEl resultat amb especificació de pares

Desplegament del graf orientat: arrel = 1--------------------------------------------------------------------------------------------Vertex 1 (num = 1) visitat. Profunditat = 0. Info: Lat = 41.483300; Lon = 2.133300Vertex 2 (num = 2) visitat. Profunditat = 1. Pare = 1. Info: Lat = 41.466700; Lon = 2.083300Vertex 3 (num = 3) visitat. Profunditat = 2. Pare = 2. Info: Lat = 41.381800; Lon = 2.168500Vertex 5 (num = 5) visitat. Profunditat = 2. Pare = 2. Info: Lat = 42.500000; Lon = 1.600000

Desplegament del graf orientat: arrel = 5--------------------------------------------------------------------------------------------Vertex 5 (num = 5) visitat. Profunditat = 0. Info: Lat = 42.500000; Lon = 1.600000

Desplegament del graf no orientat: arrel = 1--------------------------------------------------------------------------------------------Vertex 1 (num = 1) visitat. Profunditat = 0. Info: Lat = 41.483300; Lon = 2.133300Vertex 2 (num = 2) visitat. Profunditat = 1. Pare = 1. Info: Lat = 41.466700; Lon = 2.083300Vertex 5 (num = 5) visitat. Profunditat = 1. Pare = 1. Info: Lat = 42.500000; Lon = 1.600000Vertex 3 (num = 3) visitat. Profunditat = 2. Pare = 2. Info: Lat = 41.381800; Lon = 2.168500Vertex 4 (num = 4) visitat. Profunditat = 2. Pare = 5. Info: Lat = 40.419250; Lon =-3.693270Vertex 6 (num = 6) visitat. Profunditat = 3. Pare = 4. Info: Lat = 41.984200; Lon = 2.823900

Desplegament del graf no orientat: arrel = 6--------------------------------------------------------------------------------------------Vertex 6 (num = 6) visitat. Profunditat = 0. Info: Lat = 41.984200; Lon = 2.823900Vertex 4 (num = 4) visitat. Profunditat = 1. Pare = 6. Info: Lat = 40.419250; Lon =-3.693270Vertex 3 (num = 3) visitat. Profunditat = 2. Pare = 4. Info: Lat = 41.381800; Lon = 2.168500Vertex 5 (num = 5) visitat. Profunditat = 2. Pare = 4. Info: Lat = 42.500000; Lon = 1.600000Vertex 2 (num = 2) visitat. Profunditat = 3. Pare = 3. Info: Lat = 41.466700; Lon = 2.083300Vertex 1 (num = 1) visitat. Profunditat = 3. Pare = 5. Info: Lat = 41.483300; Lon = 2.133300


Moviments en grafs per nivells: breadth-first searchLa funció BFS en C

#include <limits.h> // Per USHRT_MAX#include <string.h> // Per memset

void print_node(node *G, unsigned short v, unsigned short d, unsigned short p){fprintf(stdout, "Vertex %c (num = %u) visitat. Profunditat = %u. ", G[v].name, v+1, d);if(p != USHRT_MAX) fprintf(stdout, "Pare = %u. ", p+1);fprintf(stdout, "Info: Lat = %f; Lon = %f\n", G[v].lat, G[v].lon);

}

void BFS( node *G, unsigned short ordre, unsigned short source ){UnaCua LaCua = { NULL };unsigned short depth[ordre]; memset(depth, USHRT_MAX, ordre*sizeof(unsigned short));unsigned short pare[ordre];

encua(source, &LaCua); depth[source]=0U; pare[source] = USHRT_MAX;

while( !EsBuida(LaCua) ){ register unsigned short v, i, s;v = desencua(&LaCua); print_node(G, v, depth[v], pare[v]);for(i=0; i < G[v].nsucc; i++) { s = G[v].successors[i];

if(depth[s] == USHRT_MAX){ encua(s, &LaCua); depth[s] = depth[v] + 1; pare[s] = v; }}

}}

Observació

USHRT_MAX és el nombre més gran que cap a un unsigned short. És a dir, en el móndels unsigned short, USHRT_MAX és ∞.


Moviments en grafs per nivells: breadth-first searchLa funció BFS en C

ExerciciFent servir el vector de pares programar un procediment queescrigui el camí mínim trobat de l’arrel a cada un dels nodes.

ObservacionsQueda més compacte (però és mes difícil) si es troben elsnodes extremals i s’escriuen els camins mínims trobats del’arrel a cada un d’aquests nodes.Per a calcular els camins cal anar endarrere (de fills a pares) idesprés girar els camins.


Moviments en grafs per nivells: breadth-first searchFuncions de tractament de cues amb llistes enllaçades

Declaració dels elements de la cuatypedef struct CuaElem {

unsigned short vertex;struct CuaElem *seg;

} CuaElem;

Declaració de la cua (contenidor)typedef struct {

CuaElem *start;CuaElem *end;

} UnaCua;

Funcions de tractament de cues amb listes enllaçades#include <stdlib.h> // Per la funció exit()

int EsBuida( UnaCua Q ){ return ( Q.start == NULL ); }

void encua( unsigned short vert2Q, UnaCua *Q ){CuaElem *aux=(CuaElem *) malloc(sizeof(CuaElem));if( aux == NULL) { fprintf(stderr, "ERROR de memòria a ’encua’\n"); exit(3); }aux->vertex=vert2Q; aux->seg=NULL;

if( Q->start ) Q->end->seg=aux; else Q->start=aux;Q->end=aux;

}

unsigned short desencua( UnaCua *Q ){CuaElem *aux = Q->start;unsigned short v = Q->start->vertex;Q->start=Q->start->seg;free(aux);return v;

}


Moviments en grafs en profunditat: depth-first searchLa funció DFS per grafs en pseudocodi

Algorisme: depth-first search per grafsprocedure DFS(graf G, ordre, arrel)

visitat[ordre] ← inicialitzat a 0 . Per controlar si un node ha estat visitat o no.s ← StackBuits.push(arrel)while (not s.EsBuit) do

node ← s.popif (visitat[node]) then continue;visitat[node] ← 1visita(node)for i i ← 0, node.numadj-1 do . Per tractar un nombre arbitrari de nodes ad-

jacents (possiblement diferent) a cada node.Condiciona molt l’ordre de visita dels nodes.adj ← node.successor[i]

if (not visitat[adj]) thens.push(adj)

end ifend for


Un node v pot estar a la pila diverses vegadesJa que pot ser adjacent a múltiples nodes exploratsperò no visitats, i cada un d’aquests nodes afegeix unacòpia de v a la pila. Òbviament només traurem de lapila una d’aquestes còpies: la darrera que hi hem afegit.


Moviments en grafs en profunditat: depth-first searchLa funció DFS per grafs en pseudocodi

L’Algorisme depth-first search per grafsNo és igual que per arbres ni que el breadth-first search pergrafs (pàgina 52) canviant cues per stacks.

ObservacionsRealitza correctament el recorregut “en profunditat” (veure lapàgina 60) encara que l’ordre de visita dels nodes depèn de lacombinatòria del graf i de l’ordre en que s’expansionen elsnodes adjacents.No calcula correctament la profunditat.També obtenim un arbre d’expansió encara que, en aquestcas, no és minimal (ja que no es calcula bé la profunditat).


Moviments en grafs en profunditat: depth-first searchEl programa

#include <stdio.h>typedef struct {

char name;double lat, lon;unsigned short nsucc;unsigned short successors[3];

} node;

void BFS(node *G, unsigned short ordre, unsigned short source);

void main (void) {node GrafO[5] = { {’1’, 41.4833, 2.1333, 1, {1}},

{’2’, 41.4667, 2.0833, 2, {2, 4}},{’3’, 41.3818, 2.1685, 1, {0}},{’4’, 40.41925, -3.69327, 1, {4}},{’5’, 42.5, 1.6, 1, {4}} };

node GrafNO[6] = { {’1’, 41.4833, 2.1333, 2, {1, 4}},{’2’, 41.4667, 2.0833, 3, {0, 2, 4}},{’3’, 41.3818, 2.1685, 2, {1, 3}},{’4’, 40.41925, -3.69327, 3, {2, 4, 5}},{’5’, 42.5, 1.6, 3, {0, 1, 3}},{’6’, 41.9842, 2.8239, 1, {3}} };

puts("\nDesplegament del graf orientat: arrel = 1\n"); DFS(GrafO, 5U, 0U);puts("\nDesplegament del graf orientat: arrel = 5\n"); DFS(GrafO, 5U, 4U);puts("\nDesplegament del graf no orientat: arrel = 1\n"); DFS(GrafNO, 6U, 0U);puts("\nDesplegament del graf no orientat: arrel = 6\n"); DFS(GrafNO, 6U, 5U);

}


Moviments en grafs en profunditat: depth-first searchEl resultat: Veure les observacions de les pàgines 43 i 44

Desplegament del graf orientat: arrel = 1-------------------------------------------------Vertex 1 visitat: Lat = 41.483300; Lon = 2.133300Vertex 2 visitat: Lat = 41.466700; Lon = 2.083300Vertex 5 visitat: Lat = 42.500000; Lon = 1.600000Vertex 3 visitat: Lat = 41.381800; Lon = 2.168500

Desplegament del graf orientat: arrel = 5-------------------------------------------------Vertex 5 visitat: Lat = 42.500000; Lon = 1.600000

Desplegament del graf no orientat: arrel = 1-------------------------------------------------Vertex 1 visitat: Lat = 41.483300; Lon = 2.133300Vertex 5 visitat: Lat = 42.500000; Lon = 1.600000Vertex 4 visitat: Lat = 40.419250; Lon =-3.693270Vertex 6 visitat: Lat = 41.984200; Lon = 2.823900Vertex 3 visitat: Lat = 41.381800; Lon = 2.168500Vertex 2 visitat: Lat = 41.466700; Lon = 2.083300

Desplegament del graf no orientat: arrel = 6-------------------------------------------------Vertex 6 visitat: Lat = 41.984200; Lon = 2.823900Vertex 4 visitat: Lat = 40.419250; Lon =-3.693270Vertex 5 visitat: Lat = 42.500000; Lon = 1.600000Vertex 2 visitat: Lat = 41.466700; Lon = 2.083300Vertex 3 visitat: Lat = 41.381800; Lon = 2.168500Vertex 1 visitat: Lat = 41.483300; Lon = 2.133300

Desplegament delgraf no orientat: arrel = 1

1

5

2

4

36


Moviments en grafs per nivells: depth-first searchLa funció DFS en C

#include <string.h> // Per memset

void print_node(node *G, unsigned short v){fprintf(stdout, "Vertex %c (num = %u) visitat: Lat = %f; Lon = %f\n",

G[v].name, v+1, G[v].lat, G[v].lon);}

void DFS( node *G, unsigned short ordre, unsigned short source ){ register unsigned short i, adj;UnStack LaPila = { NULL }; push(source, &LaPila);unsigned short visitat[ordre]; memset(visitat, 0U, ordre*sizeof(unsigned short));

while(!EsBuit(LaPila)){if(visitat[(source = pop(&LaPila))]) continue;visitat[source] = 1; print_node(G, source);for(i=0; i < G[source].nsucc; i++)

if(!visitat[(adj = G[source].successors[i])]) push(adj, &LaPila);}

}

ExerciciModificar el procediment anterior per a afegir el vector de pares ila memòria de pares. Escriure els pares a la sortida del programa.


Moviments en grafs en profunditat: depth-first searchFuncions de tractament d’stacks amb llistes enllaçades

Declaració dels elements de l’stacktypedef struct StackElem {

unsigned short vertex;struct StackElem *lower;

} StackElem;

Declaració de l’stack (contenidor)typedef struct {

StackElem *start;} UnStack;

Funcions de tractament d’stacks amb llistes enllaçades#include <stdlib.h> // Per la funció exit()

int EsBuit( UnStack S ){ return ( S.start == NULL ); }void push( unsigned short vert2S, UnStack *S ){

StackElem *aux=(StackElem *) malloc(sizeof(StackElem));if( aux == NULL) { fprintf(stderr, "ERROR de memòria a ’push’\n"); exit(3); }aux->vertex=vert2S;aux->lower=S->start;S->start=aux;

}

unsigned short pop( UnStack *S ){StackElem *aux = S->start;unsigned short v = S->start->vertex;S->start=S->start->lower;free(aux);return v;

}


grafs i arbres introducciómat.uab.cat/~alseda/matdoc/grafsdefimovs-2x2.pdf · grafs i arbres...

Documents