Algoritmica grafurilor si aplicatii

Cuprins: 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