![](https://csdnimg.cn/release/download_crawler_static/5775285/bg11.jpg)
A Tree-based Heap ...................................................................................600
Heapsort ...................................................................................................601
Trickling Down in Place .................................................................602
Using the Same Array .....................................................................604
The
heapSort.java Program ..........................................................605
The Efficiency of Heapsort .............................................................610
Summary ..................................................................................................610
Questions .................................................................................................611
Experiments .............................................................................................612
Programming Projects .............................................................................612
13 Graphs 615
Introduction to Graphs ...........................................................................615
Definitions ......................................................................................616
Historical Note ...............................................................................618
Representing a Graph in a Program ..............................................619
Adding Vertices and Edges to a Graph ..........................................622
The
Graph Class ..............................................................................622
Searches ....................................................................................................623
Depth-First Search ..........................................................................625
Breadth-First Search ........................................................................636
Minimum Spanning Trees .......................................................................643
GraphN Workshop Applet .............................................................644
Java Code for the Minimum Spanning Tree ..................................644
The
mst.java Program ...................................................................645
Topological Sorting with Directed Graphs ..............................................649
An Example: Course Prerequisites .................................................649
Directed Graphs .............................................................................650
Topological Sorting ........................................................................651
The GraphD Workshop Applet ......................................................652
Cycles and Trees .............................................................................653
Java Code ........................................................................................654
Connectivity in Directed Graphs ............................................................661
The Connectivity Table ..................................................................662
Warshall’s Algorithm ......................................................................662
Implementation of Warshall’s Algorithm ......................................664
Summary ..................................................................................................665
Questions .................................................................................................665
Experiments .............................................................................................667
Programming Projects .............................................................................667
Data Structures & Algorithms in Java, Second Editionxvi
00 0672324539 fm 10/10/02 9:13 AM Page xvi