Algoritmica grafurilor si aplicatii

Prefaţă

1 Introducere în algoritmi

11.1 Limbajulpseudocod ................................ 2

1.2 Elementedeanalizaalgoritmilor.......................... 10

1.2.1 Metodasubstituţiei............................. 14

1.2.2 Schimbareadevariabilă .......................... 14

1.2.3 Metodaiterativă .............................. 15

1.2.4 Teoremamaster............................... 16

1.3 Exerciţii ....................................... 18

2 Grafuri. Grafuri neorientate29

2.1 Noţiunidebază................................... 29

2.2 Operaţiipegrafuri ................................. 35

2.3 Moduri de reprezentare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.4 Parcurgereagrafurilor ............................... 42

2.4.1 Parcurgerea în lăţime (BFS-Breadth First Search) . . . . . . . . . . . . 42

2.4.2 ParcurgereaD(D-Depth) ........................ 46

2.4.3 Parcurgereaînadâncime(DFS-DepthFirstSearch) ........... 47

2.5 Componenteconexe................................. 51

2.6 Muchiecritică.................................... 52

2.7 Punctedearticulaţie ................................ 59

2.8 Componentebiconexe................................ 61

2.9 Exerciţii ....................................... 63

3 Grafuri euleriene şi hamiltoniene69

3.1 GrafuriEuleriene .................................. 69

3.1.1 Algoritm pentru determinarea unui ciclu eulerian . . . . . . . . . . . . 70

3.1.2 AlgoritmulluiRosenstiehl ......................... 73

3.1.3 AlgoritmulluiFleury............................ 77

3.2 GrafuriHamiltoniene................................ 79

3.2.1 Problemacomis–voiajorului ........................ 81

3.3 Exerciţii ....................................... 91

4 Arbori. Arbori binari97

4.1 Arboribinari .................................... 98

4.1.1 Moduri de reprezentare . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.1.2 Metodedeparcurgere............................101

4.2 Arboribinaridecăutare ..............................107

viiiCUPRINS4.2.1 Arboribinaridecăutareoptimali .....................115

4.3 Aplicaţie-codificareHuffman ...........................117

4.4 Arboriternaridecăutare..............................120

4.5 Exerciţii .......................................124

5 Heap-uri131

5.1 Heap-uri binare (Min-heapuri sauMax-heapuri).................132

5.1.1 Inserareaunuielement ...........................133

5.1.2 Ştergereaelementuluiminim........................133

5.1.3 Creareaunuiheap .............................135

5.1.4 Ordonarefolosingheap-uri-HeapSort ..................138

5.2 Aplicatie-Coadăcupriorităţi...........................140

5.3 Heap-uriFibonacci .................................142

5.3.1 CreareaunuiHeapFibonacci .......................143

5.3.2 Reuniunea a două heap-uri Fibonacci . . . . . . . . . . . . . . . . . . . 144

5.3.3 Inserareauneivalorinoi ..........................145

5.3.4 Aflareanoduluiminim ...........................145

5.3.5 Ştergereanoduluiminim..........................145

5.3.6 Descreştereavaloriiuneichei........................148

5.3.7 Ştergereaunuinod .............................151

5.4 Exerciţii .......................................151

6 Arbori oarecare159

6.1 Moduri de reprezentare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

6.2 Metodedeparcurgere................................163

6.3 Arborideacoperiredecostminim.........................163

6.3.1 AlgoritmulluiBoruvka...........................167

6.3.2 AlgoritmulluiPrim.............................167

6.3.3 Structuridedatepentrumulţimidisjuncte................171

6.3.4 AlgoritmulluiKruskal ...........................175

6.4 AlgoritmulLCA(lowestcommonancestor)....................178

6.4.1 Arborecartezian ..............................179

6.4.2LCA⇒RMQ(transformarea problemei determinăriiLCAîn prob-lema determinăriiRMQ)..........................182

6.4.3 Algoritmi pentru calcululRMQ(rangeminimumquery) ........183

6.4.4 NumerotareaDewey ............................185

6.5 Exerciţii .......................................187

7 Grafuri orientate201

7.1 Noţiunidebază...................................201

7.2 Parcurgereagrafurilor ...............................203

7.3 Sortareatopologică.................................207

7.4 Componentetareconexe ..............................210

7.4.1 AlgoritmulluiKosaraju ..........................212

7.4.2 AlgoritmulluiTarjan............................215

7.4.3 AlgoritmulluiGabow ...........................219

7.5 Exerciţii .......................................221