grafs: definicions i algorismes bàsicsalseda/matdoc/grafsdefimovs.pdfgrafsiarbres—introducció 1...

Grafs: Definicions i Algorismes Bàsics

Lluís Alsedà

Departament de MatemàtiquesUniversitat Autònoma de Barcelonahttp://www.mat.uab.cat/~alseda

Versió 3.1 (6 de maig de 2021)

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

http://creativecommons.org/licenses/by-nc-sa/4.0/

Continguts

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

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

Connectivitat en grafs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

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

Moviments en grafs — Introducció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Arbres i Arbres amb arrel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Moviments en arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Rooted graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Rooted graphs traversal: Breadth-first search . . . . . . . . . . . . . . . . . . . . . . 50

Rooted graphs traversal: Depth-first search . . . . . . . . . . . . . . . . . . . . . . . . 71

Algorismes per comprovar la connexió de grafs i comptar el nombre decomponents connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

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/91

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


http://en.wikipedia.org/wiki/Graph_theory


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.

2

2Figura extreta de Wikipedia



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 Ordre i mida2 València i grau3 Vèrtex terminal4 Camins i llaços


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 pàgina 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 pàgina 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 pàgina 2 té valència3 mentres 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 pàgina 2 té in-grau 3 iout-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 la pàgina 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 pàgina 2 mentre que 2→ 3→ 1→ 2→ 5→ 5→ 5 és uncamí 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 pàgina 2 mentre que 2→ 3→ 1→ 2 és un llaç de llargada 3del graf orientat.


Connectivitat en grafs

Índex

1 Connectivitat en grafs no dirigits2 Connectivitat en grafs dirigits


Connectivitat en grafs no dirigits

ConnexióUn graf no dirigit és connex quanhi ha un camí entre cada parellde vèrtexs (és a dir, no hi havèrtexs inaccessibles).

Component connexaUna component connexa d’ungraf no orientat és un subgrafconnex maximal.Notis que cada vèrtex i cadaaresta pertany a una únicacomponent connexa.

Exemple: un graf no connexamb dues components connexes.

6 4 5

1

3 27

8

9

10


Connectivitat en grafs dirigits

Connexió febleUn graf dirigit s’anomena feblement connex quan és connex com agraf no dirigit. És a dir, quan en substituir totes les seves arestes(dirigides) per arestes no dirigides obtenim un graf (no dirigit)connex.

Exemple:El graf dirigit de la pàgina 2

1 2 5

3 4


Connectivitat en grafs dirigits

Semi-connexióUn graf dirigit s’anomena unilateralment connex o semi-connexquan, donats dos vèrtexs qualssevol u, v , conté un camí dirigit deu a v o un camí dirigit de v a u.

Connexió fortaUn graf dirigit s’anomena fortament connex quan, donats dosvèrtexs qualssevol u, v , conté un camí dirigit de u a v i un camídirigit de v a u. Una component connexa forta és un subgrafmaximal fortament connex.


Components fortament connexes

Exemple: un graf dirigit no fortament connex, amb trescomponents fortament connexes.

0 1

2

3

4


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 pàgina 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 dirigit de la pàgina 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.483

3lon=

2.13

33nsucc=

1successors[2]=

{1}

name[11

]=

"Plaça"

lat=

41.466

7lon=

2.08

33nsucc=

2successors[2]=

{2,4

}

name[11

]=

Çruïlla"

lat=

41.381

8lon=

2.16

85nsucc=

1successors[2]=

{0}

name[11

]=

"Fon

t"lat=

40.419

25lon=

-3.693

27nsucc=

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 arestaemmagatzema els seus vèrtexs incidents. A més, opcionalment,cada vèrtex pot emmagatzemar les seves arestes incidents.Aquesta estructura de dades permet l’emmagatzematge de dadesaddicionals sobre vèrtexs i arestes (per exemple noms, pesos,. . . ).

Un exemple en C— El graf dirigit de la pàgina 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 pàgina 20 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 pàgina 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.


Arbres i Arbres amb arrel

Índex

1 Arbres — Únicament arc-connexos2 Arbres amb arrel: Fixant el node origen3 Arbres amb arrel: Fulles i Vèrtexs de Ramificació4 Arbres amb arrel — Profunditat d’un vèrtex5 Arbres amb arrel — Profunditat de l’arbre6 Arbres amb arrel — Pares i Fills7 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

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

http://en.wikipedia.org/wiki/Tree_(graph_theory)

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: 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: l’arbre amb arrel de la pàgina anteriorLes fulles són els vèrtexs 4, 7, 8 i 9.Els vèrtexs 2 i 5 són de ramificació.

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 arbre 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 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 pàgina 28:

Profunditat 0 1 2 3

Vèrtexs

1 2 4 7

3 5 86 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 28amb 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 pagines 28 i 31).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 pàgina 28 té profunditat 3.El mateix arbre amb arrel 6 de la pàgina 31 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 28

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 31

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 28

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 31

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 pàgines 28 i 31 són arbres binaris.


Moviments en arbres

Índex

1 En profunditat: depth-first search — preordre2 En profunditat: depth-first search — enordre3 En 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

4https://en.wikipedia.org/wiki/Tree_traversalLluís Alsedà Grafs: Definicions i Algorismes Bàsics Índex General 38/91

https://en.wikipedia.org/wiki/Tree_traversal

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



Rooted graphs

Índex

1 Rooted graphs: Specifying the source node2 An example of a rooted graph3 Depths in rooted graphs4 Rooted graphs — Depth properties


Rooted graphs

A rooted graph (also called a pointed graph or a flow graph) is agraph in which one vertex has been distinguished as the root.

DefinitionsA leaf of a rooted graph is any vertex of valence 1 different fromthe root. A branching vertex is any vertex with valence greaterthan two that is different from the root.

Remark: The valence of a vertex does not depend on the rootTherefore, the leaves and branching vertices of a graph areindependent of the root node except the root node itself (whichabandons its leaf or branching character when it is designated tobe the root).


An example of a rooted graph (with root A)

A

B

D

C

E

G

I

F H

J K

Examples on the definitionsThis rooted graph has the vertices J and K as leaves, and B, D,E , F , G , H and I as branching vertices.


Depths in rooted graphsDefinition: Depth of a vertexIn a rooted graph the depth of a vertex is defined as the minimumdistance from the root to the selected vertex.Minimum distance:Given two vertices α and β, the minimum distance from α to βis measured as the shortest length of a path from α to β (notethat in a graph there may be more than one of these paths —there may even be more than one path of minimum length fromα to β).Obviously the distance of a node to itself is 0.On the other hand, in a graph there may be no path from α toβ. In this case the distance from α to β is ∞ by convention.

Definition: Depth of a rooted graphThe depth of a rooted graph is defined as the maximum depth ofthe vertices.


Rooted graphs — Depth properties

From the above definitions and examples it follows:The depth of the root is 0.The depths of the vertices of a rooted graph depend on thechosen root.Therefore, the depth of a rooted graph depends on the root.

The computation of the depth of a rooted graph (andtherefore of the depths of all its vertices) requires thecomputations of the minimum distances (shorter paths)from the root to each node.

In a connected undirected rooted graph all nodes have finitedepth. However, on a directed rooted graph (even if it isconnected) there might exist nodes with infinite depth.


Rooted graphs traversal: Breadth-first search

Índex

1 Rooted graphs traversal and the depth function: breadth-firstsearch algorithm

2 An example3 Comments on the depth function for rooted graphs4 Comments on graph traversal with breadth-first search5 Spanning Trees and Minimal Spanning Trees6 An implementation of the breadth-first search algorithm in C


Rooted graphs traversal and the depth function:the breadth-first search algorithm

Graph traversal or graph search refers to the process of visitingeach vertex in a graph. Such traversals are classified by the orderin which the vertices are visited.

A breadth-first search (BFS) is a technique for traversing a finitegraph. BFS visits the sibling vertices before visiting the childvertices, and a queue is used in the search process.

This algorithm finds a shortest path from the root of the graph toevery one of its vertices, thus computing the depths of all vertices.


The Breadth-first search algorithm

Pseudocode of Breadth-first search with parents memory for graphsprocedure BFS(graph G, order, source, parent[order])

depth[order] ← initialized to ∞ .To store the depths of all nodes, and to controlwhether a node has been already visited

q ← EmptyQueue . Initialization

q.enqueue(source) . Initialization

depth[source] ← 0 . source has depth 0 and it has been already enqueued ( 6= ∞)

parent[source] ←∞ . source has no parent

while (not q.IsEmpty) donode ← q.dequeuefor each adj ∈ node.successors do

if (depth[adj] = ∞) then . adj has not been enqueued (visited) previously

q.enqueue ← adjdepth[adj] ← depth[node]+1 .

node is already visited (depth[node] 6= ∞)depth[adj] is derived from depth[node]

parent[adj] ← node . Setting parent as the node arriving to adj

end ifend for



An example of the Breadth-first search algorithmComputing a minimal spanning tree

A0 A

B

1 B

D

1 D

C

2 C

E

2 E

G

3 G

I

3 I

F

4 F

H

4 H

A

B D C E G I F H

depth 0

1 1 2 2 3 3 4 4

parent nil

A A B B E E G I

Q



A0 A

B1 B

D1 D

C

2 C

E

2 E

G

3 G

I

3 I

F

4 F

H

4 H

A B D

C E G I F H

depth 0 1 1

2 2 3 3 4 4

parent nil A A

B B E E G I

Q



A0 A

B1 B

D1 D

C2 C

E2 E

G

3 G

I

3 I

F

4 F

H

4 H

A B D C E

G I F H

depth 0 1 1 2 2

3 3 4 4

parent nil A A B B

E E G I

Q



A0 A

B1 B

D1 D

C2 C

E2 E

G3 G

I3 I

F

4 F

H

4 H

A B D C E G I

F H

depth 0 1 1 2 2 3 3

4 4

parent nil A A B B E E

G I

Q



A0 A

B1 B

D1 D

C2 C

E2 E

G3 G

I3 I

F4 F H

4 H

A B D C E G I F

H

depth 0 1 1 2 2 3 3 4

4

parent nil A A B B E E G

I

Q



A0 A

B1 B

D1 D

C2 C

E2 E

G3 G

I3 I

F4 F H4 H

A B D C E G I F Hdepth 0 1 1 2 2 3 3 4 4parent nil A A B B E E G I

Q



A0 A

B1 B

D1 D

C2 C

E2 E

G3 G

I3 I

F4 F H4 H


Q


Comments on the depth function for rooted graphsAll depthsThe depth of every node in the rooted graph of the previousexample is listed in the table, and included in the graph itself (thenumber at the left of every node’s box).

The depth of the whole graph is 4.

Example: Why the depth of node G in the above graph is 3Recall that in a rooted graph the depth of a vertex is defined as the minimumdistance from the root to the selected vertex. So, let us write some of thepaths from A to G in the above graph.

A −→ B −→ E −→ G . a shortest path from A to G — of length 3

A −→ D −→ E −→ G . another shortest path from A to G — recall the non-unicity

A −→ D −→ B −→ E −→ G . wrong: A → D → B is not minimal

A −→ D −→ B −→ E −→ I −→ H −→ GA −→ D −→ E −→ G −→ I −→ H −→ G . non-sense turning around a circuit

A→ D → E → G → I → H → G → I → H → G . more non-sense circuit turning


Comments on graph traversal with breadth-first search

RemarkThe breadth-first search algorithm finds a shortest path from theroot of the graph to every one of its vertices, thus computing thedepths of all vertices.

RemarkThis is NOT equivalent to the computation of the shortest pathbetween any pair of nodes of the graph.

In fact the BFS algorithm returns a minimal spanning tree.

ExampleThe minimal spanning tree of the previous example is the one(whose arrows are) marked in blue.


Spanning Tree

DefinitionA spanning tree of a connected graph is a subset of edges of thegraph that connects all its vertices, and is a tree.

RemarksA non-connected graph has no spanning tree (since trees are connectedand spanning trees must contain all vertices).Non-unicity: A graph can have more than one spanning tree.If all edges of a graph are also edges of a spanning tree, then the graphcoincides with its spanning tree. Therefore, any tree coincides with its(unique) spanning tree.A spanning tree of a connected graph can also be defined both as amaximal set of edges that do not contain cycles, or as a minimal set ofedges connecting all vertices.In particular, a connected graph always has a spanning tree. Moreover,this spanning tree can be obtained by deleting edges so that each deletionbreaks a circuit (loop).


Minimal Spanning Tree

DefinitionA minimal spanning tree of a connected graph is a spanning treesuch that every path α in the spanning tree, starting at the rootvertex, has minimum length among all paths in the graph startingat the root and ending at the same vertex as α.

ExampleSee the spanning tree (marked in blue) in the previous example.


Implementation of the breadth-first search algorithm in CThe main BFS code

typedef struct { char name; unsigned short nsucc, successors[3]; } graph_node;

void graph_node_print(graph_node *Graph, unsigned short v, unsigned short d, unsigned short p){char static head_print = 0;if(!head_print){ head_print = 1;

fprintf(stdout, "Visit | Depth |\nOrder | found | Parent\n------|-------|-------\n"); }fprintf(stdout, "%c (%u) |%4u |", Graph[v].name, v, d);if(p != USHRT_MAX) fprintf(stdout, "%2c (%u)", Graph[p].name, p);fprintf(stdout, "\n");

}

void BFS( graph_node *Graph, unsigned short order, unsigned short source ){Queue Q = { NULL, NULL };unsigned short depth[order], parent[order];memset(depth, USHRT_MAX, order*sizeof(unsigned short));enqueue(source, &Q); depth[source]=0U; parent[source] = USHRT_MAX;

while( !IsEmpty(Q) ){ register unsigned short v, i, s;v = dequeue(&Q); graph_node_print(Graph, v, depth[v], parent[v]);for(i=0; i < Graph[v].nsucc; i++) {

s = Graph[v].successors[i];if(depth[s] == USHRT_MAX){ enqueue(s, &Q); depth[s] = depth[v] + 1; parent[s] = v; }

}}}

int main (void) {graph_node GraphDem[9] = { {’A’, 2, {1,3}}, {’B’, 2, {2,4}}, {’C’, 0, {}}, {’D’, 2, {1,4}},

{’E’, 3, {2,6,8}}, {’F’, 2, {3,7}}, {’G’, 2, {5,8}}, {’H’, 1, {6}}, {’I’, 1, {7}} };

BFS(GraphDem, 9U, 0U);}

Output: depths andthe spanning tree

Visit | Depth |Order | found | Parent------|-------|-------A (0) | 0 |B (1) | 1 | A (0)D (3) | 1 | A (0)C (2) | 2 | B (1)E (4) | 2 | B (1)G (6) | 3 | E (4)I (8) | 3 | E (4)F (5) | 4 | G (6)H (7) | 4 | I (8)

Rem

ark:

USHR

T_MA

Xis

thelargestnu

mberthat

canbe

stored

inan

unsi

gned

shor

tvaria

ble.

Inotherwords,inthe“w

orld”of

unsi

gned

shor

t’s,

USHR

T_MA

Xis

∞.

Direct assignment at declaration time as initialization.


Implementation of the breadth-first search algorithm in CInitializations and queue functions

#include <stdio.h>#include <stdlib.h> // For exit() and malloc()#include <limits.h> // For USHRT_MAX#include <string.h> // For memset

typedef struct QueueElementstructure {unsigned short vertex;struct QueueElementstructure *seg;

} QueueElement;

typedef struct { QueueElement *start, *end; } Queue;int IsEmpty( Queue Q ){ return ( Q.start == NULL ); }

int enqueue( unsigned short vert2Q, Queue *Q ){QueueElement *aux = (QueueElement *) malloc(sizeof(QueueElement)); if( aux == NULL ) return 0;

aux->vertex=vert2Q; aux->seg=NULL;if( Q->start ) Q->end->seg=aux; else Q->start=aux;Q->end = aux;return 1;

}

unsigned int dequeue( Queue *Q ){ if( IsEmpty(*Q) ) return UINT_MAX;QueueElement *node_inicial = Q->start;unsigned int v = node_inicial->vertex;

Q->start = Q->start->seg;free(node_inicial);return v;

}

The number of elements nel of the queue is notused in this application. Hence, it is omitted.

Similarly, the function to initialise the queue isnot necessary as we use direct assignment whendeclaring the queue:

Queue Q = { NULL, NULL };


Implementation of the BFS in C: an exercise

Optional ExerciseBy using the parents vector, create a procedure that writes the shortest path found byBFS from the root to each of the nodes.

RemarkIt is more compact (but more difficult) to find first the leavesof the spanning tree, and then write the minimum paths fromthe root to each of these nodes.To compute the paths, go backwards (from children toparents — starting at the end of the paths) and then reversethe paths.


Rooted graphs traversal: Depth-first search

Índex

1 The Depth-first search algorithm2 An example3 Comments on graph traversal with depth-first search4 A second example (with a different root)5 An implementation of the depth-first search algorithm in C


Rooted graphs traversal: Depth-first search

The depth-first search algorithm for graphsdoes not work as for trees, and likewise it is not similar to thebreadth-first search algorithm for graphs (page 52) withqueues replaced by stacks.

Remarks: on the depth-first search algorithm for graphsIt traverses successfully the graph “in depth” (see the examplestarting on page 74) though the order of visit of the nodesdepends on the combinatorics of the graph and the order inwhich adjacent nodes are expanded.It does not compute the depth function correctly.It correctly computes a spanning tree, although in this case itis not necessarily minimal (since it does not calculate well thedepth function).


The Depth-first search algorithm

Pseudocode of Depth-first search with parents memory for graphsprocedure DFS(graph G, order, root, parent[order])

visited[order] ← initialized to false . To control whether a node has been visited or not.

s ← EmptyStacks.push(root)parent[root] ←∞ . The root has no parent.

while (not s.IsEmpty) donode ← s.popif (visited[node]) then continue . A vertex may have been placed several times in

the stack. When processing the first of theseinstances the vertex is visited. After this, the re-maining instances of the vertex must be ignored.

visited[node] ← truevisit(node)for each adj ∈ node.successors do .

It determines the order in which the nodes arevisited, their parents, and a spanning tree.

if (not visited[adj]) then . Visited nodes do not need to be re-visited.

parent[adj] ← nodes.push(adj)

end ifend for


A node v can be placed in the stack several timessince it can be adjacent to several nodes explored but notvisited, and each of these nodes adds a copy of v to thestack. Obviously we will only remove one of these copiesfrom the stack: the last one we added.


An example of the Depth-first search algorithmThe undirected graph from page 2 (with vertices labeled with capital letters for clarity)Finding a spanning tree (not necessarily minimal)

A E D

C

F

B

Visited nodesordering 1

2 3 4 5 6

node A

E D F C

parent

A E D D

Stack1 A



A E D

C

F

B

Visited nodesordering 1

2 3 4 5 6

node A

E D F C

parent

A E D D

Stack2 E B



A E D

C

F

B

Visited nodesordering 1 2

3 4 5 6

node A E

D F C

parent A

E D D

Stack3 D B B



A E D

C

F

B

Visited nodesordering 1 2 3

4 5 6

node A E D

F C

parent A E

D D

Stack4 F C B B



A E D

C

F

B

Visited nodesordering 1 2 3 4

5 6

node A E D F

C

parent A E D

D

Stack5 C B B



A E D

C

F

B

Visited nodesordering 1 2 3 4 5

6

node A E D F Cparent A E D D

Stack6 B B B



A E D

C

F

B

Visited nodesordering 1 2 3 4 5 6node A E D F C Bparent A E D D C

Stack7 B B


Comments on graph traversal with depth-first search

The depth-first search algorithmtraverses the whole graph “in depth” visiting all graph’s nodes butit does not compute the depth function correctly.

In fact the DFS algorithm returns a spanning tree (which is notnecessarily minimal).

ExampleThe spanning tree of the previous example is the one (whosearrows are) marked in blue.


A second example of the Depth-first search algorithmThe same graph as before (the undirected graph from page 2) with a diffrent root

F

A E D

C

B

Visited nodesordering 1 2 3 4 5 6node F D E B C Aparent F D E B B


Implementation of the depth-first search algorithm in CThe main DFS code

typedef unsigned short u_short;typedef struct { char name; u_short nsucc, successors[3]; } graph_node;void graph_node_print(graph_node *G, u_short v, u_short p, u_short s){

if(v == s) { fprintf(stdout,"\n\n ordering | parent\n----------|-------\n%4c (%u) |\n", G[v].name, v

); } else fprintf(stdout, "%4c (%u) | %c (%u)\n", G[v].name, v, G[p].name, p);}

void DFS( graph_node *Graph, u_short order, u_short source ){register u_short i;u_short parent[order];Stack St = NULL;char visited[order]; memset(visited, 0, order);push(source, &St); parent[source] = USHRT_MAX;

while(!IsEmpty(St)){ u_short node = pop(&St);if(visited[node]) continue;visited[node] = 1;graph_node_print(Graph, node, parent[node], source);for(i=0; i < Graph[node].nsucc; i++) {

u_short adj = Graph[node].successors[i];if(!visited[adj]) { push(adj, &St); parent[adj] = node; }

}}}

int main (void) {graph_node GrafNO[6] = { {’A’, 2, {1, 4}}, {’B’, 3, {0, 2, 4}}, {’C’, 2, {1, 3}},

{’D’, 3, {2, 4, 5}}, {’E’, 3, {0, 1, 3}}, {’F’, 1, {3}} };DFS(GrafNO, 6U, 0U);DFS(GrafNO, 6U, 5U);

}

Output:Traversal andthe spanning tree

ordering | parent----------|-------

A (0) |E (4) | A (0)D (3) | E (4)F (5) | D (3)C (2) | D (3)B (1) | C (2)

ordering | parent----------|-------

F (5) |D (3) | F (5)E (4) | D (3)B (1) | E (4)C (2) | B (1)A (0) | B (1)

Rem

ark:

USHR

T_MA

Xis

thelargestnu

mberthat

canbe

stored

inan

unsi

gned

shor

tvaria

ble.

Inotherwords,inthe“w

orld”of

unsi

gned

shor

t’s,

USHR

T_MA

Xis

∞.


Implementation of the depth-first search algorithm in CInitializations and queue functions

#include <stdio.h>#include <stdlib.h> // For exit() and malloc()#include <limits.h> // For USHRT_MAX#include <string.h> // For memset

typedef struct StackElementstructure {unsigned short vertex;struct StackElementstructure *lower;

} StackElement;

typedef StackElement * Stack;int IsEmpty( Stack S ){ return ( S == NULL ); }unsigned short pop( Stack *S ){

Stack aux = *S;unsigned short v = (*S)->vertex;

*S = (*S)->lower;free(aux);

return v;}

int push( unsigned short vert2S, Stack *S ){StackElement *aux = (StackElement *) malloc(sizeof(StackElement)); if( aux == NULL ) return 0;

aux->vertex = vert2S;aux->lower = *S;*S = aux;return 1;

}


Algorismes per comprovar la connexió de grafs i comptar elnombre de components connexes

Índex

1 Grafs no dirigits: com detectar la connexió i comptar elnombre de components connexes

2 Grafs dirigits: connexió feble3 Grafs dirigits: connexió forta


Grafs no dirigits: com detectar la connexió i comptar elnombre de components connexes

Algorisme: comprovant la connexió en grafs no dirigits

1 Seleccionar un vèrtex aleatori s que usarem com arrel.2 Realitzar un un recorregut del graf usant BFS o DFS, prenent el vèrtex s

com arrel.3 En acabar el recorregut comprovar si hem visitat tots els vèrtexs del graf.

El graf és connex si i només si hem recorregut tots els vèrtexs del graf.El graf, en ser connex, té una component connexa.

Algorisme: comptant el nombre de components connexes en grafs no dirigitsEl nombre de components connexes d’un graf no dirigit és el nombre devegades que cal iterar l’algorisme anterior (és a dir, l’algorisme que comprova laconnexió en grafs no dirigits), prenent com a arrel un vèrtex no visitat en lesiteracions anteriors, fins que hàgim visitat tots els vèrtexs.

Nota: Com hem dit abans, si la primera vegada que apliquem l’algorisme quecomprova la connexió en grafs no dirigits visitem tots els vèrtexs del graf, el grafés connex i, per tant, té una component connexa.


Grafs dirigits: connexió feble

Observació òbviaPer detectar si un graf dirigit és feblement connex i comptar el seunombre de components connexes febles s’usen els algorismes de lapàgina anterior, després de convertir el graf en NO dirigit.

ExerciciJustificar com es converteix un graf dirigit en un no dirigit per acada un dels quatre models de representació de grafs en memòria(explicats a partir de la pàgina 17).


Grafs dirigits: connexió forta

Algorisme: comprovant ineficientment la connexió forta en grafs dirigitsIterar, per a cada vertex s del graf, el següent

ProcedimentRecórrer el graf usant BFS o DFS, prenent s com a arrel i comprovar sis’han visitat tots els vèrtexs del graf.En aquest cas sabem que hi ha un camí (orientat) que va de s a cadaun dels vèrtexs del graf.En cas contrari el graf no pot ser fortament connex ja que hi ha vèrtexsinaccessibles a partir d’s.

Resumint: un graf és fortament connex si el procediment anterior es pot rea-litzar per a cada vèrtex del graf visitant, cada vegada, tots els altres vèrtexs delgraf.Alternativament, la primera vegada que el procediment anterior falli (és a dir,es trobin vèrtexs inaccessibles) sabem que el graf no és fortament connex.



Una comprovació eficient de la connexió forta en grafs dirigits esbasa en la següent

ObservacióUn graf dirigit és fortament connex si i només si per un vertex sfixat es compleixen les dues condicions següents:

1 Existeix un camí (dirigit) d’s a cada vertex del graf.2 Per a cada vertex u del graf existeix un camí dirigit de u a s.

Observem que la condició (2) és equivalent a la (1) si girem totesles arestes del graf.

ExerciciJustificar com es giren les arestes d’un graf dirigit per a cada undels quatre models de representació de grafs en memòria (explicatsa partir de la pàgina 17).



La observació anterior dóna lloc al següent

Algorisme: comprovant la connexió forta en grafs dirigits

1 Seleccionar un vèrtex aleatori s que usarem com arrel.2 Realitzar un recorregut del graf usant BFS o DFS, prenent el vèrtex s


En cas negatiu el graf no és fortament connex.En cas afirmatiu:

4 Girar totes les arestes del graf.5 Realitzar un nou recorregut del graf usant BFS o DFS, prenent el vèrtex s


El graf és fortament connex si i només si hem visitat tots els vèrtexs delgraf.

El graf, quan és fortament connex, té exactament una component fortamentconnexa.



Algorisme:comptant el nombre de components fortament connexes en grafs dirigitsEl nombre de components fortament connexes d’un graf no dirigit és elnombre de vegades que cal iterar l’algorisme anterior (és a dir, l’algorisme quecomprova la connexió forta en grafs dirigits), prenent com a arrel un vèrtex novisitat en les iteracions anteriors, fins que hàgim visitat tots els vèrtexs.

Nota: Si la primera vegada que apliquem l’algorisme que comprova la connexióforta en grafs no dirigits visitem tots els vèrtexs del graf, el graf és connex i, pertant, té una única component fortament connexa.


grafs: definicions i algorismes bàsicsalseda/matdoc/grafsdefimovs.pdfgrafsiarbres—introducció 1...

Documents