Nội dung

ALGORITHMS ROBERT SEDGEWICK BROWN UNNER!MY ADDISON-WESLEY PUBLISHING COM P ANY Reading, Massachusetts l Menlo Park, California London l Amsterdam l Don Mills, Ontario l Sydney To Adam, Brett, Robbie and especially Linda This book is in the Addison-Wesley Series in Computer Science Consulting Editor Michael A. Harrison Sponsoring Editor James T. DeWolfe Library of Congress Cataloging in Publication Data Sedgewick, Robert, 1946Algorithms. 1. Algorithms. I. Title. QA76.6.S435 1 9 8 3 ISBN O-201 -06672-6 519.4 82-11672 Reproduced by Addison-Wesley from camera-ready copy supplied by the author. Reprinted Copyright 0 with corrections, August 1984 1983 by Addison-Wesley Publishing Company, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without prior written permission of the publisher. Printed in the United States of America. ISBN o-201-06672-6 FGHIJ-HA-8987654 Preface This book is intended to survey the most important algorithms in use on computers today and to teach fundamental techniques to the growing number of people who are interested in becoming serious computer users. It is appropriate for use as a textbook for a second, third or fourth course in computer science: after students have acquired some programming skills and familiarity with computer systems, but before they have specialized courses in advanced areas of computer science or computer applications. Additionally, the book may be useful as a reference for those who already have some familiarity with the material, since it contains a number of computer implementations of useful algorithms. The book consists of forty chapters which are grouped into seven major parts: mathematical algorithms, sorting, searching, string processing, geometric algorithms, graph algorithms and advanced topics. A major goal in the development of this book has been to bring together the fundamental methods from these diverse areas, in order to provide access to the best methods that we know for solving problems by computer for as many people as possible. The treatment of sorting, searching and string processing (which may not be covered in other courses) is somewhat more complete than the treatment of mathematical algorithms (which may be covered in more depth in applied mathematics or engineering courses), or geometric and graph algorithms (which may be covered in more depth in advanced computer science courses). Some of the chapters involve mtroductory treatment of advanced material. It is hoped that the descriptions here can provide students with some understanding of the basic properties of fundamental algorithms such as the FFT or the simplex method, while at the same time preparing them to better appreciate the methods when they learn them in advanced courses. The orientation of the book is towards algorithms that are likely to be of practical use. The emphasis is on t,eaching students the tools of their trade to the point that they can confidently implement, run and debug useful algorithms. Full implementations of the methods discussed (in an actual programming language) are included in the text, along with descriptions of the operations of these programs on a consistent set of examples. Though not emphasized, connections to theoretical computer science and the analysis of algorithms are not ignored. When appropriate, analytic results are discussed to illustrate why certain algorithms are preferred. When interesting, the relationship of the practical algorithms being discussed to purely theoretical results is described. More information of the orientation and coverage of the material in the book may be found in the Introduction which follows. One or two previous courses in computer science are recommended for students to be able to appreciate the material in this book: one course in . .. 111 iv programming in a high-level language such as Pascal, and perhaps another course which teaches fundamental concepts of programming systems. In short, students should be conversant with a modern programming language and have a comfortable understanding of the basic features of modern computer systems. There is some mathematical material which requires knowledge of calculus, but this is isolated within a few chapters and could be skipped. There is a great deal of flexibility in the way that the material in the book can be taught. To a large extent, the individual chapters in the book can each be read independently of the others. The material can be adapted for use for various courses by selecting perhaps thirty of the forty chapters. An elementary course on “data structures and algorithms” might omit some of the mathematical algorithms and some of the advanced graph algorithms and other advanced topics, then emphasize the ways in which various data structures are used in the implementation. An intermediate course on “design and analysis of algorithms” might omit some of the more practically-oriented sections, then emphasize the identification and study of the ways in which good algorithms achieve good asymptotic performance. A course on “software tools” might omit the mathematical and advanced algorithmic material, then emphasize means by which the implementations given here can be integrated for use into large programs or systems. Some supplementary material might be required for each of these examples to reflect their particular orientation (on elementary data structures for “data structures and algorithms,” on mathematical analysis for “design and analysis of algorithms,” and on software engineering techniques for “software tools”); in this book, the emphasis is on the algorithms themselves. At Brown University, we’ve used preliminary versions of this book in our third course in computer science, which is prerequisite to all later courses. Typically, about one-hundred students take the course, perhaps half of whom are majors. Our experience has been that the breadth of coverage of material in this book provides an “introduction to computer science” for our majors which can later be expanded upon in later courses on analysis of algorithms, systems programming and theoretical computer science, while at the same time providing all the students with a large set of techniques that they can immediately put to good use. The programming language used throughout the book is Pascal. The advantage of using Pascal is that it is widely available and widely known; the disadvantage is that it lacks many features needed by sophisticated algorithms. The programs are easily translatable to other modern programming languages, since relatively few Pascal constructs are used. Some of the programs can be simplified by using more advanced language features (some not available in Pascal), but this is true less often than one might think. A goal of this book is to present the algorithms in as simple and direct form as possible. The programs are not intended to be read by themselves, but as part of the surrounding text. This style was chosen as an alternative, for example, to having inline comments. Consistency in style is used whenever possible, so that programs which are similar, look similar. There are 400 exercises, ten following each chapter, which generally divide into one of two types. Most of the exercises are intended to test students’ understanding of material in the text, and ask students to work through an example or apply concepts described in the text. A few of the exercises at the end of each chapter involve implementing and putting together some of the algorithms, perhaps running empirical studies to learn their properties. Acknowledgments Many people, too numerous to mention here, have provided me with helpful feedback on earlier drafts of this book. In particular, students and teaching assistants at Brown have suffered through preliminary versions of the material in this book over the past three years. Thanks are due to Trina Avery, Tom Freeman and Janet Incerpi, all of whom carefully read the last two drafts of the book. Janet provided extensive detailed comments and suggestions which helped me fix innumerable technical errors and omissions; Tom ran and checked the programs; and Trina’s copy editing helped me make the text clearer and more nearly correct. Much of what I’ve written in this book I’ve learned from the teaching and writings of Don Knuth, my thesis advisor at Stanford. Though Don had no direct influence at all on this work, his presence may be felt in the book, for it was he who put the study of algorithms on a scientific footing that makes a work such as this possible. Special thanks are due to Janet Incerpi who initially converted the book into QX format, added the thousands of changes I made after the “last draft,” guided the files through various systems to produce printed pages and even wrote the scan conversion routine for Ylj$ that we used to produce draft manuscripts, among many other things. The text for the book was typeset at the American Mathematical Society; the drawings were done with pen-and-ink by Linda Sedgewick; and the final assembly and printing were done by Addison-Wesley under the guidance of Jim DeWolf. The help of all the people involved is gratefully acknowledged. Finally, I am very thankful for the support of Brown University and INRIA where I did most of the work on the book, and the Institute for Defense Analyses and the Xerox Palo Alto Research Center, where I did some work on the book while visiting. Robert Sedgewick Marly-le-Roi, France February, 1985’ Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 . . . . 9 Algorithms, Outline of Topics 1. Preview. . . . . . . . . . . . . . . . . . . . . . . Pascal, Euclid’s Algorithm, Recursion, Analysis of Algorithms Implementing Algorithms MATHEMATICAL ALGORITHMS 2. Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 21 Polynomials, Matrices, Data Structures 3. Random Numbers . . . . . . . . . . . . . . . . . . . . . . . 33 Applications, Linear Congruential Method, Additive Congruential Method, Testing Randomness, Implementation Notes 4. Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Evaluation, Interpolation, Multiplication, Recurrences, Matriz Multiplication Divide-and-conquer 5. Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . 57 A Simple Example, Outline of the Method, Variations and Extensions 6. Curve Fitting . . . . . . . . . . . . . . . . . . . . . . . . . 67 Polynomaal Interpolation, Spline Interpolation, Method of Least Squares 7. Integration . . . . . . . . . . . . . . . . . . . . . . Symbolac Adaptive . . . . 79 Integration, Simple Quadrature Methods, Compound Methods, Quadrature SORTING 8. Elementary Sorting Methods . . . . . . . . . . . . . . . . . . 91 Rules of the Game, Selection Sort, Insertion Sort, Shellsort, Bubble Sort, Distribution Counting, Non-Random Files 9. Quicksort . . . . . . . . . . . . . . , , . , . . . . . * . . 103 The Baszc Algorithm, Removing Recursion, Small Subfiles, Median-of- Three Partitioning 10. Radix Sorting . . . . . . . . . . . , . . . . . . . . . . . . 115 Radiz Ezchange Sort, Straight Radix Sort, A Linear Sort 11. Priority Queues . . . . . . . . . . . . . . . . . . . . . . 127 . . . 143 Elementary Implementations, Heap Data Structure, Algorithms on Heaps, Heapsort, Indirect Heaps, Advanced Implementations 12. Selection and Merging . . . . . . . . . . . . . . . . . Selection, Mergang, Recursion Revisited 13. External Sorting . . . . . . . . . . . . . . . . . . . . . Sort-Merge, Balanced Multiway Merging, Replacement Selectzon, Practical Considerations, Polyphase Merging, An Easier Way vi . 155 vii SEARCHING 14. Elementary Searching Methods . . . . . . . . . . . . . . . . 171 Sequential Searching, Sequential List Searchang, Binary Search, Binary ‘Pree Search, Indirect Binary Search Trees 15. Balanced Trees . . . . . . . . . . . . . . . . . . . . . . Top-Down 2-9-4 Trees, Red-Black Trees, Other Algorithms 16. Hashing . . . . . . . . . . . . . . . . . , . . . . . . . 187 201 Hash Functions, Separate Chaining, Open Addresszng, Analytic Results 17. Radix Searching . . . . . . . . . . . . . . . . . . . . . . Digital Search Trees, Patricia Radix Search Wes, M&iway 213 Radar Searching, 18. External Searching . . . . . . . . ,, . . . . . . . . . . . . . 225 Indexed Sequential Access, B- nees, Extendible Hashing, Virtual Memory STRING PROCESSING 19. String Searching . . . . . . . . . . . . . . . . . . . . . . 241 A Short History, Brute-Force Algorithm, Knuth-Morris-Pratt Algorzthm, Bayer-Moore Algorithm, Rabin-Karp Algorithm, Multiple Searches 20. Pattern Matching . . . . . . . . . . . . . . . . . . . . . 257 Describing Patterns, Pattern Matching Machznes, Representzng the Machine, Simulating the Machine 21. Parsing , . . . . . . . . . . . . . . . . . . . . . . . . . 269 Conteti-Free Grammars, Top-Down Parsing, Bottom-Up Parsing, Compilers, Compiler-Compilers 22. File Compression . . . . . . . . . . . . . . . . . . . . . . 283 Run-Length Encoding, Variable-Length Encoding 23. Cryptology . . . . . . . . . . . . . . . . . . . . . . . . . 295 Rules of the Game, Simple Methods, Encrypt:!on/Decryption Machines, Publzc-Key Cryptosystems GEOMETRIC ALGORITHMS 24. Elementary Geometric Methods . . . . . . . . . . . . . . . . 307 Poznts, Lines, and Polygons, Line Intersection, Simple Closed Path, Inclusaon in 4 Polygon, Perspective 25. Finding the Convex Hull . . . . . . . . . . . . . . . . . . . Rules of the Game, Package Wrapping, The Graham Scan, 321 Hull Selection, Performance Issues 26. Range Searching . . . . . . . . . . . . . . . . . . . . . . . 335 Elementary Methods, Grad Method, 2D Trees, Multidimensaonal Range Searching 27. Geometric Intersection . , . . . . . . . . . . . . . . . . . . 349 Horizontal and Vertical Lines, General Line Intersection 28. Closest Point Problems . . . . . . . . . . . . . . . . . . . 361 Closest Paar, Voronoi Diagrams Vlll GRAPH ALGORITHMS 29. Elementary Graph Algorithms . . . . . . . . . . . . . . . . . 373 Glossary, Representation, Depth-First Search, Mazes, Perspectzve 30. Connectivity . . . . . . . . . . . . . . . . . . . . . . . 389 Biconnectivity, Graph Traversal Algorzthms, Union-Find Algorithms 31. Weighted Graphs . . . . . . . . . . . . . . . . . . . . . 407 . 421 Mmimum Spanning Tree, Shortest Path, Dense Graphs, Geometrzc Problems 32. Directed Graphs . . . . . . . . . . . . . . . . . . . . Depth-Farst Search, Transitwe Closure, Topological Sorting, Strongly Connected Components 33. Network Flow . . . . . . . . . . . . . . . . . . . The Network Flow Problem, Ford-Adkerson . . 433 . . 443 . . 457 . . 471 . . 483 Method, Network Searching 34. Matching . . . . . . . . . . . . . . . . . . , . . . . . Bapartite Graphs, Stable Marriage Problem, Advanced Algorathms ADVANCED TOPICS 35. Algorithm Machines . . . . . . . . . . . . . . . . . . . General Approaches> Perfect ShujIes, Systolic Arrays 36. The Fast Fourier Transform . . . . . . . . . . . . . . . Evaluate, Multiply, Interpolate, Complez Roots of Unity, Evaluation at the Roots of Unity, Interpolatzon at the Roots of Unity, Implementation 37. Dynamic Programming . . . . . . . . . . . . . . . . . . Knapsack Problem, Matriz Chain Product, Optimal Binary Search Trees, Shortest Paths, Time and Space Requirements 38. Linear Programming . . . . . . . . . . . . . . . . . . . . 497 Lznear Programs, Geometric Interpretation, The Simplex Method, Implementation 39. Exhaustive Search . . . . . . . . . . . . . . . . . . . Exhaustive Search in Graphs, Backtrackzng, Approximation Algorithms . . 513 . 527 Permutation Generation, 40. NP-complete Problems . . . . . . . . . . . . . . . . Deterministic and Nondeterministic Polynomial- Time Algorzthms, NP-Completeness, Cook’s Theorem, Some NP-Complete Problems . ................................................................ .......................................... : ........ ..... : ..... : ... : : ... ........... ... ..... : ...... : ... : ... : ... : .... .:: .... . . ‘LE. : : ..... : : : ... ... : : : ...... : .. ........... : ... ....... . : ... : .... : . * ..: ... .: ... :.: ................................. ...... : .... ........ . :: .. : .......................................... . .. ... : ... ........ : .... : . .:. ... : : -..: ... ..:........ : ... : ... : :: ........ : . .:: . : ....... : : ... : .:.‘: .. . .................... : ... : : .. : .... I .... . . .:. ..... : ............... : ... : : .. : ... ... : ... :..:. ... . .:. . : ....... : ...... ..'...: .:.....:..:...:. : : : ... : ... : ... : ..... . .:. . : .. ..... .:: : : .................... .:. : .... : : : . ........................................ :.a: ... : :: ..: ... : .... : .... . .:. : .:. : ... : .... : .:..: . ............................................... ........... : .... :::.: :.: : *.- : :.: :::.: -:.: ........... ..................................... ................................................ .......................................... .:. : ... : :.:: ... : :: : .... : ... : .:. : : .. : :..: .... : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . :..: :..: .:. : :. :.:. : .:..:-:. : .:. : :. :.:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -:.::.: : :: : :: . .. .. .* . . . . . . . . . . . . . :.:. . . . . . . . . . . . . . . . . : ::: .:: : :. :-:-. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . :. :.::: :. : .:: : :. : :..: :. : :*. :.:. :-:. . . . . . . . . . . . . . . . . . . . . . . . . *.. . . . . . . . . . . . . ........ . .:: . : ....... : ........ . . .:. . : .. : .... : ...... . :. . : . :. :: . :. . : . :. : : . :... : . ::. .............................. .... :. : :. : :. : :..: :. :-:. : :. : :. : :. : :. : .. : .:. : ... : ... : ... : ... : ... : ... : ... : .... : :: : . . I, . . . . . . . . ::.. . .:. ..:a: . . . . . . .:. : . . . :..: ..:.. ........ ...... ... : ........... : ... ::. ... . . ..: ........ . ... : ... : .... . ... : .... . ..................... . . . . . . . . . . . . . . . . . . . . . * . . . . . . *.. . :. : :. : :. : :. : ::: :. : :. :.:. : :. : :: ............. : ... : ... : ... : : .. : ... : . - -.,- : : ..:....: . .::. :.. :... : ..::. ..: . .:. ..::. :... ........ .:... : .... ... : ......... : .:. . : .. :...:: ...... :.:,,; .*. : . . . : . ..‘. . . . : . . . : . . . : . . . : . . . : . . . : . . . : . . . . : . . . : . . . : .*. : . . . : . . . : . . . . . .*. : .*. : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .-... . . . . . . . . . . . . . . . . a:: . ..: . .:.*. . . . : :.. . . . . . . . . . . . . . . ..: : . . . :.:.. :.... : . . . . . ..: : . . . : . . ::.. . . . . . . . . . . . . . . . . . . . . . . . . . :-. :*:. ................................ ...................................................... ............................................... : .: ..: ... : .... :.: ... . .... .:. : ... :; .... . .... . . ... : ... : .... . ::: ... : ... : ... : .‘: : .:. : ... : ... : ................... : .............. ..... ..:....:. . : .. ..: .. : ..... *:: . .:. . :.: .: ... : ........ . . .: “1 : ....... : ........ . . ::. . :.. ... . . : ....... ................................................................ ... : .... : : .. : ... : :: :.::: ... : ... : .... : : .. : ... : :: : ::: ... : ... :-.:. : : .. : ... : :: : ::: ... : . ......................................................................................... : ..... ............. . ........................... ..~................ ..... ... : .... : ... :‘.:. : ... : .... . : .. : ... : .... : ... : .:. : ... : ::.: ... : ... :.::: ... : .:. : ... : .... . ... : . ..... ..: .. .:. . :.: ..... : .: ..... . . ::. . : ....... : .... . .. . . .: ... : ...... . : ..... .:: . .:. . : ....... : ....... ............................ .............................. : ............ .... . ... : .::: ... : .... : ::.: ... : .:. : ... : .... : .... . : .. : .:. : ... :: ... : .... . ... : .:. : ... :.::: .... . . ......... : ... .:. ... . ......... : ......... : ... .:. ... . ......... : ......... : ... .:. ... . ......... : . .... . .. . : ... ; :. .. . .... : .... . .. . : .... . : .. :. ... : .,.,,: .:: : ... : : .. :. ... : ..: .: .. . : ... : : .. :: ... : .... . . ................................................................ ............................................................. : .............................. ................................................. : ............................. ... : ... : .... : .... : : .. : ... : ... : ... : :: : .:. : :.“: ... : ... : ... : ... : -....: ... : : .. : .I. : ... : ... : . ........ . . ::. . ::. .... . : ........ . : .:. ..: .. 1-i .. : .: ...... . . :: ... : .. : .... : ...... :.: . .:. . :.: ...... . .... . . ... : .... . .... . .. . : ... : ... : ... : : ... .:. . : ..... ....... . ................ . ..... ....................... : .. : ....... : ... : ::: ... : :: : ... : ... : ... : : .. : ... : .... : . ............................................. : ...................... .: .................... ..: ... ................................. : ................................. : ....... ... : ... : .... : ... : ... : ... : .:. : ... : ... : ... : .... . ... : ... : ... : ... : .... : ... : ... : ... : .:. : ... : . ....... . . .:. . : ....... : ....... . . .:. . : ....... : ....... . . .:. . : ....... : ....... . . .:. . : ....... : ...... ......................... ......................... ..................... :..: .... : ::. : ... :.:: : :.:: ... : .:. : .... :.: .. : :.,.: :: : .::: ... : .... : -....: : .. : .:. : :: :.::: .... . . ........................ . . : ....... .:. . .:. ..... : ..... . .................. : ....... : .......... : .... . .. . : ... : : .. : .... : .... . . -:.: -.: : ... : :: ::: : *:.: -.: : ... : :: ::: : -:.: ... . : ... : : .. : .... ............... : ............... : ..... .., ........ . ..... .:. ..... : ............... ............... . ..... .:. ..... ; ............... : ............... . ..... .:. ..... : ............. .... . ... : .:. : ... : .... : .... . ... : .;. : ... : .... : . .., .: ... : .;. : ... : .... : .... . ... : .:. : ... : .... : .... . . ......................................................... ..~..~. ......... : ... .:. ... . ......... : ......... : ... .:. ... . ......... : ......... : ... .:. ... . .......... ..... : ..... : ..... : ..... : ..... : ..... : ..... : ..... : ..... : ..... : ..... : ..... : ..... ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : ... : . . .:..: . . . . . . . :... . ..: .:... . . . . . . . . . . . . . . . . . . . . . . . ...,: ..; : . . . . : . . . . . . . :*. . :. . : : . . s-:. . : . I . . . . . . . :. -.: :‘. :.:. : ::: :: : :. : ::. :-:. : ::: . : :