Preface |
|
xxiii | |
Acknowledgments |
|
xxv | |
Authors |
|
xxvii | |
|
|
1 | (42) |
|
|
3 | (12) |
|
Object-Oriented Design and This Book |
|
|
4 | (1) |
|
|
5 | (1) |
|
Invariants and Representation Properties |
|
|
6 | (1) |
|
Interfaces and Data Abstraction |
|
|
7 | (1) |
|
Case Study on Conceptual Design: Historical Event Collection |
|
|
8 | (2) |
|
Case Study on Structural Design: Trees |
|
|
10 | (3) |
|
|
13 | (2) |
|
Selecting an Abstract Data Type |
|
|
15 | (20) |
|
|
16 | (3) |
|
|
19 | (2) |
|
|
21 | (1) |
|
|
21 | (2) |
|
|
23 | (1) |
|
Positioning and Finding Elements |
|
|
24 | (4) |
|
Manually Positioned Collections |
|
|
26 | (1) |
|
Algorithmically Positioned Collections |
|
|
26 | (2) |
|
|
28 | (7) |
|
|
35 | (8) |
|
|
35 | (1) |
|
Parts II and III Presentation Structure |
|
|
36 | (5) |
|
|
36 | (2) |
|
|
38 | (2) |
|
|
40 | (1) |
|
|
41 | (2) |
|
II COLLECTION DATA STRUCTURES AND ALGORITHMS |
|
|
43 | (2) |
|
|
45 | (794) |
|
|
49 | (24) |
|
|
50 | (1) |
|
|
51 | (3) |
|
Singleton Classes: Empty and Deleted |
|
|
51 | (1) |
|
|
51 | (2) |
|
|
53 | (1) |
|
|
54 | (2) |
|
|
56 | (3) |
|
Object Pool to Reduce Garbage Collection Overhead |
|
|
59 | (1) |
|
|
60 | (2) |
|
Iterators for Traversing Data Structures |
|
|
62 | (1) |
|
|
63 | (7) |
|
Case Study: Maintaining Request Quorums for Byzantine Agreement |
|
|
63 | (1) |
|
|
64 | (1) |
|
|
65 | (2) |
|
|
67 | (1) |
|
Iteration Order and Concurrent Modifications |
|
|
68 | (2) |
|
|
70 | (1) |
|
Visitors for Traversing Data Structures |
|
|
71 | (2) |
|
Partition ADT and the Union-Find Data Structure |
|
|
73 | (16) |
|
Partition Element Interface |
|
|
73 | (1) |
|
Selecting a Data Structure |
|
|
74 | (1) |
|
Union-Find Data Structure |
|
|
74 | (1) |
|
|
75 | (1) |
|
Representation Properties |
|
|
76 | (1) |
|
|
77 | (3) |
|
|
80 | (1) |
|
Case Study: Preserving Locators When Merging Data Structures |
|
|
81 | (2) |
|
|
83 | (4) |
|
|
87 | (2) |
|
|
89 | (6) |
|
|
90 | (2) |
|
Tracked Collection Interface |
|
|
92 | (1) |
|
ADTs Implementing the Collection Interface |
|
|
92 | (3) |
|
Manually Positioned Collections |
|
|
92 | (1) |
|
Algorithmically Positioned Untagged Collections |
|
|
92 | (1) |
|
Algorithmically Positioned Tagged Ungrouped Collections |
|
|
93 | (1) |
|
Algorithmically Positioned Tagged Grouped Collections |
|
|
94 | (1) |
|
|
95 | (12) |
|
|
95 | (1) |
|
Representation Properties |
|
|
96 | (1) |
|
|
96 | (4) |
|
|
96 | (1) |
|
|
97 | (2) |
|
|
99 | (1) |
|
|
100 | (1) |
|
Abstract Locater Inner Class |
|
|
100 | (2) |
|
|
102 | (3) |
|
|
105 | (1) |
|
|
105 | (2) |
|
Positional Collection ADT |
|
|
107 | (14) |
|
|
107 | (2) |
|
Positional Collection Locator Interface |
|
|
109 | (1) |
|
|
110 | (1) |
|
|
110 | (1) |
|
Selecting a Data Structure |
|
|
111 | (5) |
|
Tradeoffs among Array-Based Data Structures |
|
|
114 | (1) |
|
Tradeoffs among List-Based Data Structures |
|
|
115 | (1) |
|
Summary of Positional Collection Data Structures |
|
|
116 | (3) |
|
|
119 | (2) |
|
Abstract Positional Collection |
|
|
121 | (4) |
|
Abstract Positional Collection |
|
|
121 | (1) |
|
|
121 | (1) |
|
|
122 | (3) |
|
|
125 | (46) |
|
|
126 | (2) |
|
Representation Properties |
|
|
128 | (1) |
|
|
128 | (12) |
|
|
128 | (1) |
|
|
129 | (1) |
|
|
130 | (1) |
|
|
131 | (1) |
|
|
132 | (1) |
|
|
133 | (6) |
|
|
139 | (1) |
|
|
140 | (18) |
|
|
143 | (2) |
|
|
145 | (2) |
|
|
147 | (2) |
|
|
149 | (1) |
|
|
149 | (6) |
|
|
155 | (2) |
|
|
157 | (1) |
|
Selection and Median Finding |
|
|
158 | (2) |
|
|
160 | (2) |
|
|
162 | (1) |
|
|
163 | (3) |
|
|
166 | (1) |
|
|
167 | (4) |
|
Circular Array Data Structure |
|
|
171 | (14) |
|
|
171 | (2) |
|
Representation Properties |
|
|
173 | (1) |
|
|
173 | (8) |
|
|
173 | (1) |
|
|
174 | (1) |
|
|
175 | (1) |
|
|
176 | (5) |
|
|
181 | (2) |
|
|
183 | (2) |
|
Dynamic Array and Dynamic Circular Array Data Structures |
|
|
185 | (8) |
|
|
185 | (1) |
|
|
186 | (1) |
|
Representation Properties |
|
|
187 | (1) |
|
|
187 | (3) |
|
|
187 | (1) |
|
|
188 | (1) |
|
|
189 | (1) |
|
|
190 | (1) |
|
|
191 | (2) |
|
Tracked Array Data Structure |
|
|
193 | (24) |
|
|
194 | (3) |
|
Representation Properties |
|
|
197 | (1) |
|
|
198 | (1) |
|
|
198 | (7) |
|
|
198 | (1) |
|
|
199 | (1) |
|
|
199 | (1) |
|
|
200 | (1) |
|
|
201 | (3) |
|
|
204 | (1) |
|
Wrappers for Sorting Tracked Arrays |
|
|
205 | (2) |
|
|
207 | (6) |
|
|
213 | (1) |
|
|
214 | (3) |
|
Singly Linked List Data Structure |
|
|
217 | (40) |
|
|
217 | (3) |
|
Representation Properties |
|
|
220 | (1) |
|
|
220 | (1) |
|
Singly Linked List Methods |
|
|
221 | (11) |
|
Constructors and Factory Methods |
|
|
221 | (1) |
|
|
222 | (1) |
|
|
222 | (2) |
|
|
224 | (1) |
|
|
224 | (7) |
|
|
231 | (1) |
|
Sorting Algorithms Revisited |
|
|
232 | (12) |
|
|
232 | (1) |
|
|
233 | (2) |
|
|
235 | (1) |
|
|
236 | (1) |
|
|
237 | (5) |
|
|
242 | (2) |
|
|
244 | (1) |
|
Selection and Median Finding |
|
|
244 | (2) |
|
|
246 | (5) |
|
|
251 | (3) |
|
|
254 | (3) |
|
Doubly Linked List Data Structure |
|
|
257 | (8) |
|
|
257 | (1) |
|
Representation Properties |
|
|
258 | (1) |
|
Doubly Linked List Item Inner Class |
|
|
259 | (1) |
|
Doubly Linked List Methods |
|
|
259 | (2) |
|
Constructors and Factory Methods |
|
|
259 | (1) |
|
|
260 | (1) |
|
|
260 | (1) |
|
|
261 | (1) |
|
|
261 | (2) |
|
|
263 | (2) |
|
Buffer ADT and Its Implementation |
|
|
265 | (6) |
|
|
265 | (1) |
|
Representation Properties |
|
|
266 | (1) |
|
|
266 | (4) |
|
|
266 | (1) |
|
|
267 | (1) |
|
|
268 | (1) |
|
|
268 | (1) |
|
|
269 | (1) |
|
|
270 | (1) |
|
|
270 | (1) |
|
Queue ADT and Implementation |
|
|
271 | (4) |
|
|
271 | (1) |
|
|
271 | (1) |
|
|
272 | (1) |
|
|
273 | (2) |
|
Stack ADT and Implementation |
|
|
275 | (4) |
|
|
275 | (1) |
|
|
276 | (2) |
|
|
278 | (1) |
|
|
278 | (1) |
|
|
279 | (12) |
|
Case Study: Airline Travel Agent |
|
|
279 | (1) |
|
|
280 | (1) |
|
|
280 | (1) |
|
|
281 | (1) |
|
|
282 | (1) |
|
Selecting a Data Structure |
|
|
283 | (3) |
|
Summary of Set Data Structures |
|
|
286 | (3) |
|
|
289 | (2) |
|
Direct Addressing Data Structure |
|
|
291 | (14) |
|
|
291 | (2) |
|
Representation Properties |
|
|
293 | (1) |
|
Default Direct Addressing Hasher Class |
|
|
293 | (1) |
|
|
293 | (5) |
|
|
293 | (1) |
|
|
294 | (1) |
|
|
294 | (1) |
|
|
295 | (1) |
|
|
296 | (1) |
|
|
296 | (1) |
|
|
297 | (1) |
|
|
298 | (3) |
|
|
301 | (2) |
|
|
303 | (2) |
|
Open Addressing Data Structure |
|
|
305 | (16) |
|
|
305 | (3) |
|
Representation Properties |
|
|
308 | (1) |
|
Default Open Addressing Hasher Class |
|
|
309 | (1) |
|
|
310 | (7) |
|
|
310 | (1) |
|
|
311 | (1) |
|
|
311 | (1) |
|
Selecting a Hash Function |
|
|
312 | (1) |
|
|
313 | (1) |
|
|
314 | (2) |
|
|
316 | (1) |
|
|
317 | (1) |
|
|
318 | (3) |
|
Separate Chaining Data Structure |
|
|
321 | (22) |
|
|
322 | (2) |
|
Representation Properties |
|
|
324 | (1) |
|
|
325 | (1) |
|
Default Separate Chaining Hasher Class |
|
|
326 | (1) |
|
Separate Chaining Methods |
|
|
326 | (8) |
|
|
326 | (2) |
|
|
328 | (1) |
|
|
328 | (1) |
|
|
329 | (2) |
|
|
331 | (2) |
|
|
333 | (1) |
|
|
334 | (5) |
|
|
339 | (1) |
|
|
340 | (3) |
|
|
343 | (10) |
|
Case Study: Huffman Compression |
|
|
343 | (2) |
|
|
345 | (1) |
|
Priority Queue Locator Interface |
|
|
345 | (1) |
|
Selecting a Data Structure |
|
|
346 | (1) |
|
|
347 | (1) |
|
|
347 | (1) |
|
Summary of Priority Queue Data Structures |
|
|
348 | (3) |
|
|
351 | (2) |
|
Binary Heap Data Structure |
|
|
353 | (20) |
|
|
353 | (3) |
|
Representation Properties |
|
|
356 | (1) |
|
|
356 | (11) |
|
|
356 | (1) |
|
|
357 | (1) |
|
|
357 | (1) |
|
|
357 | (1) |
|
|
358 | (3) |
|
|
361 | (5) |
|
|
366 | (1) |
|
|
367 | (1) |
|
|
368 | (2) |
|
|
370 | (3) |
|
Leftist Heap Data Structure |
|
|
373 | (26) |
|
|
373 | (2) |
|
Representation Properties |
|
|
375 | (1) |
|
Leftist Heap Node Inner Class |
|
|
376 | (2) |
|
|
378 | (13) |
|
|
378 | (1) |
|
|
379 | (3) |
|
|
382 | (9) |
|
|
391 | (1) |
|
|
391 | (2) |
|
|
393 | (3) |
|
|
396 | (3) |
|
Pairing Heap Data Structure |
|
|
399 | (24) |
|
|
399 | (3) |
|
Representation Properties |
|
|
402 | (1) |
|
|
402 | (3) |
|
|
405 | (10) |
|
Constructors and Factory Methods |
|
|
406 | (1) |
|
|
406 | (1) |
|
|
407 | (1) |
|
|
408 | (6) |
|
|
414 | (1) |
|
|
415 | (3) |
|
|
418 | (1) |
|
|
419 | (4) |
|
Fibonacci Heap Data Structure |
|
|
423 | (20) |
|
|
424 | (2) |
|
Representation Properties |
|
|
426 | (1) |
|
Fibonacci Heap Node Inner Class |
|
|
426 | (2) |
|
|
428 | (9) |
|
Constructors and Factory Methods |
|
|
428 | (1) |
|
|
429 | (4) |
|
|
433 | (4) |
|
|
437 | (4) |
|
|
441 | (2) |
|
|
443 | (12) |
|
Case Study: Historical Event Collection (Range Queries) |
|
|
443 | (1) |
|
Case Study: Linux Virtual Memory Map |
|
|
444 | (1) |
|
|
445 | (1) |
|
|
446 | (1) |
|
|
447 | (1) |
|
Selecting a Data Structure |
|
|
447 | (2) |
|
Summary of Ordered Collection Data Structures |
|
|
449 | (3) |
|
|
452 | (3) |
|
Sorted Array Data Structure |
|
|
455 | (16) |
|
|
455 | (1) |
|
Representation Properties |
|
|
456 | (1) |
|
|
457 | (10) |
|
|
457 | (1) |
|
|
457 | (1) |
|
|
458 | (2) |
|
|
460 | (4) |
|
|
464 | (1) |
|
Utilities for the B-Tree and B+-Tree Classes |
|
|
465 | (2) |
|
|
467 | (1) |
|
|
467 | (2) |
|
|
469 | (2) |
|
Abstract Search Tree Class |
|
|
471 | (10) |
|
|
471 | (2) |
|
Representation Properties |
|
|
473 | (1) |
|
Abstract Tree Node Inner Class |
|
|
474 | (1) |
|
Abstract Search Tree Class |
|
|
475 | (1) |
|
Abstract Search Tree Methods |
|
|
475 | (5) |
|
|
475 | (1) |
|
|
475 | (4) |
|
|
479 | (1) |
|
|
480 | (1) |
|
Binary Search Tree Data Structure |
|
|
481 | (28) |
|
|
481 | (4) |
|
Representation Properties |
|
|
485 | (1) |
|
|
485 | (4) |
|
Binary Search Tree Methods |
|
|
489 | (12) |
|
Constructors and Factory Methods |
|
|
490 | (1) |
|
|
490 | (6) |
|
|
496 | (4) |
|
|
500 | (1) |
|
|
501 | (3) |
|
|
504 | (2) |
|
|
506 | (3) |
|
Balanced Binary Search Trees |
|
|
509 | (4) |
|
|
510 | (2) |
|
|
512 | (1) |
|
Red-Black Tree Data Structure |
|
|
513 | (18) |
|
|
514 | (1) |
|
Representation Properties |
|
|
515 | (1) |
|
|
515 | (2) |
|
|
517 | (11) |
|
Constructors and Factory Methods |
|
|
517 | (1) |
|
|
517 | (11) |
|
|
528 | (1) |
|
|
528 | (3) |
|
Splay Tree Data Structure |
|
|
531 | (14) |
|
|
531 | (1) |
|
|
532 | (9) |
|
|
532 | (1) |
|
|
533 | (1) |
|
|
533 | (4) |
|
|
537 | (4) |
|
|
541 | (1) |
|
|
541 | (2) |
|
|
543 | (2) |
|
|
545 | (30) |
|
|
546 | (3) |
|
Representation Properties |
|
|
549 | (1) |
|
|
549 | (8) |
|
|
550 | (1) |
|
B-Tree Node Representation Mutators |
|
|
551 | (4) |
|
B-Tree Node Content Mutators |
|
|
555 | (2) |
|
|
557 | (11) |
|
Constructors and Factory Methods |
|
|
557 | (1) |
|
|
558 | (4) |
|
|
562 | (1) |
|
|
563 | (4) |
|
|
567 | (1) |
|
|
568 | (2) |
|
|
570 | (3) |
|
|
573 | (2) |
|
|
575 | (18) |
|
Case Study: A Web Search Engine |
|
|
576 | (1) |
|
|
577 | (1) |
|
Representation Properties |
|
|
578 | (1) |
|
|
579 | (4) |
|
|
583 | (6) |
|
Constructors and Factory Methods |
|
|
584 | (1) |
|
|
584 | (1) |
|
|
585 | (3) |
|
|
588 | (1) |
|
|
589 | (2) |
|
|
591 | (2) |
|
|
593 | (26) |
|
|
593 | (3) |
|
Representation Properties |
|
|
596 | (1) |
|
|
597 | (1) |
|
|
598 | (12) |
|
|
598 | (2) |
|
|
600 | (4) |
|
|
604 | (1) |
|
|
605 | (5) |
|
|
610 | (1) |
|
|
610 | (3) |
|
|
613 | (4) |
|
|
617 | (2) |
|
Digitized Ordered Collection ADT |
|
|
619 | (16) |
|
Case Study: Packet Routing |
|
|
619 | (1) |
|
Case Study: Inverted Index for Text Retrieval |
|
|
620 | (1) |
|
Digitized Ordered Collection Interface |
|
|
621 | (1) |
|
Selecting a Data Structure |
|
|
622 | (1) |
|
|
623 | (1) |
|
|
624 | (1) |
|
Summary of Digitized Ordered Collection Data Structures |
|
|
625 | (5) |
|
|
630 | (1) |
|
|
630 | (1) |
|
|
631 | (2) |
|
|
633 | (2) |
|
|
635 | (4) |
|
|
635 | (1) |
|
|
635 | (1) |
|
|
636 | (1) |
|
Abstract Trie Leaf Node Class |
|
|
637 | (2) |
|
|
639 | (32) |
|
|
639 | (3) |
|
Representation Properties |
|
|
642 | (1) |
|
Internal Node Inner Class |
|
|
642 | (2) |
|
|
644 | (1) |
|
|
644 | (5) |
|
FindResult Enumerated Type |
|
|
649 | (1) |
|
|
650 | (12) |
|
Constructors and Factory Methods |
|
|
650 | (1) |
|
|
651 | (6) |
|
|
657 | (4) |
|
|
661 | (1) |
|
|
662 | (2) |
|
|
664 | (3) |
|
|
667 | (4) |
|
Compact Trie Data Structure |
|
|
671 | (12) |
|
|
671 | (1) |
|
Representation Properties |
|
|
672 | (1) |
|
|
672 | (7) |
|
Constructors and Factory Methods |
|
|
673 | (1) |
|
|
673 | (2) |
|
|
675 | (4) |
|
|
679 | (1) |
|
|
680 | (3) |
|
Compressed Trie Data Structure |
|
|
683 | (14) |
|
|
683 | (2) |
|
Representation Properties |
|
|
685 | (1) |
|
Compressed Trie Node Interface |
|
|
686 | (1) |
|
Internal Node Inner Class |
|
|
686 | (1) |
|
Compressed Trie Leaf Node Inner Class |
|
|
687 | (1) |
|
Compressed Trie Search Data Inner Class |
|
|
687 | (1) |
|
|
688 | (5) |
|
Constructors and Factory Methods |
|
|
688 | (1) |
|
|
689 | (1) |
|
|
690 | (3) |
|
|
693 | (1) |
|
|
694 | (3) |
|
Patricia Trie Data Structure |
|
|
697 | (22) |
|
|
697 | (2) |
|
Representation Properties |
|
|
699 | (1) |
|
Patricia Trie Node Inner Class |
|
|
700 | (2) |
|
Patricia Trie Search Data Inner Class |
|
|
702 | (3) |
|
|
705 | (12) |
|
|
705 | (1) |
|
|
706 | (11) |
|
|
717 | (1) |
|
|
717 | (2) |
|
Ternary Search Trie Data Structure |
|
|
719 | (10) |
|
|
719 | (2) |
|
Representation Properties |
|
|
721 | (1) |
|
Ternary Search Trie Internal Node Inner Class |
|
|
722 | (1) |
|
Ternary Search Trie Search Data Inner Class |
|
|
722 | (1) |
|
Ternary Search Trie Methods |
|
|
723 | (2) |
|
Constructors and Factory Methods |
|
|
723 | (1) |
|
|
724 | (1) |
|
|
725 | (1) |
|
|
725 | (4) |
|
|
729 | (6) |
|
Case Study: Collision Detection in Video Games |
|
|
729 | (1) |
|
|
730 | (1) |
|
|
731 | (1) |
|
Summary of Spatial Collection Data Structures |
|
|
732 | (1) |
|
|
732 | (3) |
|
|
735 | (22) |
|
|
736 | (3) |
|
Representation Properties |
|
|
739 | (1) |
|
|
739 | (3) |
|
|
742 | (5) |
|
|
747 | (3) |
|
|
750 | (2) |
|
|
752 | (2) |
|
|
754 | (3) |
|
|
757 | (28) |
|
|
757 | (3) |
|
Representation Properties |
|
|
760 | (1) |
|
Partitioning a Two-Dimensional Space |
|
|
761 | (1) |
|
|
762 | (3) |
|
|
765 | (2) |
|
|
767 | (15) |
|
Constructors and Factory Methods |
|
|
767 | (1) |
|
|
768 | (1) |
|
|
768 | (4) |
|
|
772 | (9) |
|
|
781 | (1) |
|
|
782 | (1) |
|
|
782 | (3) |
|
|
785 | (40) |
|
|
786 | (3) |
|
|
787 | (1) |
|
Tagged Element Comparator |
|
|
787 | (1) |
|
|
788 | (1) |
|
Tagged Element XY Comparator |
|
|
788 | (1) |
|
Tagged Collection Interface |
|
|
789 | (2) |
|
|
791 | (1) |
|
|
791 | (1) |
|
Selecting a Tagged Collection ADT |
|
|
792 | (1) |
|
Tagged Collection Wrapper |
|
|
793 | (4) |
|
|
797 | (4) |
|
Direct Addressing Mapping |
|
|
799 | (1) |
|
|
799 | (2) |
|
Separate Chaining Mapping |
|
|
801 | (1) |
|
Tagged Priority Queue ADT |
|
|
801 | (6) |
|
Tagged Priority Queue Wrapper |
|
|
803 | (3) |
|
|
806 | (1) |
|
|
806 | (1) |
|
|
807 | (1) |
|
|
807 | (1) |
|
Tagged Ordered Collection ADT |
|
|
807 | (7) |
|
Tagged Ordered Collection Wrapper |
|
|
811 | (1) |
|
|
812 | (1) |
|
Tagged Binary Search Tree |
|
|
813 | (1) |
|
|
813 | (1) |
|
|
813 | (1) |
|
|
813 | (1) |
|
|
814 | (1) |
|
|
814 | (1) |
|
Tagged Digitized Ordered Collection ADT |
|
|
814 | (6) |
|
Tagged Digitized Ordered Collection Wrapper |
|
|
818 | (1) |
|
|
818 | (1) |
|
|
819 | (1) |
|
|
819 | (1) |
|
|
819 | (1) |
|
Tagged Ternary Search Trie |
|
|
819 | (1) |
|
Tagged Spatial Collection ADT |
|
|
820 | (5) |
|
Tagged Spatial Collection Wrapper |
|
|
821 | (1) |
|
|
822 | (1) |
|
|
823 | (2) |
|
Tagged Bucket Collection ADTs |
|
|
825 | (14) |
|
Case Study: Historical Event Collection (Indexing) |
|
|
826 | (2) |
|
Case Study: Biosequence Comparison |
|
|
828 | (1) |
|
|
829 | (1) |
|
Tagged Bucket Collection Interface |
|
|
829 | (2) |
|
Selecting a Tagged Bucket Collection ADT |
|
|
831 | (1) |
|
Selecting a Data Structure |
|
|
832 | (1) |
|
Tagged Bucket Collection Wrapper |
|
|
832 | (7) |
|
III GRAPH DATA STRUCTURES AND ALGORITHMS |
|
|
839 | (2) |
|
|
841 | (116) |
|
|
843 | (14) |
|
Case Study: Task Scheduler |
|
|
844 | (1) |
|
|
845 | (3) |
|
|
848 | (1) |
|
|
848 | (2) |
|
Graph Representation Interface |
|
|
850 | (1) |
|
Selecting a Data Structure |
|
|
851 | (3) |
|
Summary of Graph Data Structures |
|
|
854 | (3) |
|
Abstract Graph and Graph Algorithms |
|
|
857 | (26) |
|
Representation Properties |
|
|
858 | (1) |
|
|
858 | (3) |
|
|
861 | (4) |
|
Finding Shortest Paths with Breadth-First Search |
|
|
865 | (2) |
|
Finding Cycles and Connected Components with Depth-First Search |
|
|
867 | (6) |
|
|
873 | (2) |
|
Strongly Connected Components |
|
|
875 | (3) |
|
|
878 | (1) |
|
Case Study: Garbage Collection |
|
|
878 | (2) |
|
|
880 | (1) |
|
|
881 | (2) |
|
Adjacency Matrix Data Structure |
|
|
883 | (18) |
|
|
883 | (3) |
|
Representation Properties |
|
|
886 | (1) |
|
|
887 | (6) |
|
|
887 | (1) |
|
|
888 | (1) |
|
|
888 | (1) |
|
|
889 | (1) |
|
|
890 | (3) |
|
|
893 | (1) |
|
Incident Edge Iterator Inner Class |
|
|
893 | (3) |
|
|
896 | (1) |
|
|
897 | (1) |
|
|
898 | (3) |
|
Adjacency List Data Structure |
|
|
901 | (16) |
|
|
902 | (3) |
|
Representation Properties |
|
|
905 | (1) |
|
|
906 | (4) |
|
|
906 | (1) |
|
|
906 | (1) |
|
|
906 | (2) |
|
|
908 | (2) |
|
|
910 | (1) |
|
Edge Iterator Inner Class |
|
|
910 | (2) |
|
|
912 | (1) |
|
|
912 | (3) |
|
|
915 | (2) |
|
|
917 | (8) |
|
Case Study: Airline Travel Agent (Revisited) |
|
|
917 | (2) |
|
Case Study: Image Segmentation |
|
|
919 | (2) |
|
|
921 | (1) |
|
|
922 | (1) |
|
Simple Weighted Edge Class |
|
|
922 | (1) |
|
|
923 | (1) |
|
Selecting a Data Structure |
|
|
923 | (1) |
|
Weighted Adjacency Matrix Data Structure |
|
|
924 | (1) |
|
Weighted Adjacency List Data Structure |
|
|
924 | (1) |
|
Abstract Weighted Graph and Weighted Graph Algorithms |
|
|
925 | (32) |
|
|
926 | (5) |
|
Dijkstra's Single-Source Shortest Path Algorithm |
|
|
931 | (4) |
|
Prim's Minimum Spanning Tree Algorithm |
|
|
935 | (3) |
|
Kruskal's Minimum Spanning Tree Algorithm |
|
|
938 | (3) |
|
Bellman-Ford's Single-Source Shortest Path Algorithm |
|
|
941 | (2) |
|
|
943 | (2) |
|
Floyd-Warshall's All-Pairs Shortest Path Algorithm |
|
|
945 | (3) |
|
Edmonds-Karp Maximum Flow Algorithm |
|
|
948 | (6) |
|
|
954 | (1) |
|
|
955 | (2) |
|
|
957 | (40) |
|
|
959 | (20) |
|
|
959 | (2) |
|
|
961 | (1) |
|
|
961 | (1) |
|
|
962 | (1) |
|
|
962 | (3) |
|
|
965 | (1) |
|
|
965 | (2) |
|
|
967 | (2) |
|
|
969 | (1) |
|
|
969 | (1) |
|
|
970 | (1) |
|
|
971 | (2) |
|
|
973 | (1) |
|
|
973 | (1) |
|
Type Checking and Casting |
|
|
973 | (1) |
|
|
974 | (1) |
|
|
974 | (1) |
|
|
974 | (1) |
|
|
975 | (1) |
|
|
976 | (3) |
|
|
979 | (12) |
|
|
980 | (1) |
|
|
981 | (3) |
|
|
984 | (1) |
|
|
985 | (1) |
|
|
985 | (2) |
|
Solving Recurrence Equations with the Master Method |
|
|
987 | (4) |
|
Design Patterns Illustrated in This Book |
|
|
991 | (6) |
|
|
991 | (1) |
|
|
991 | (1) |
|
|
992 | (1) |
|
|
992 | (1) |
|
|
992 | (1) |
|
|
993 | (1) |
|
|
993 | (1) |
|
|
993 | (1) |
|
|
994 | (1) |
|
|
994 | (1) |
|
|
994 | (1) |
|
|
995 | (1) |
|
|
995 | (1) |
|
|
995 | (1) |
|
|
996 | (1) |
|
|
996 | (1) |
|
|
996 | (1) |
References |
|
997 | (8) |
Index |
|
1005 | |