A directed acyclic graph can be used to represent a set of tasks, some of which are prerequisites of others (Figure 15-23). An edge indicates that one task must be performed before another.

Figure 15-23. Dinner involves a number of different tasks, shown in this directed graph. An edge indicates that one task must be performed before another. For example, the oven must be preheated before the bread can be baked. It should be noted that only a programmer would consider this a complete meal.

A topological sort of such a graph is an ordering in which the tasks can be performed without violating any of the prerequisites. There may be more than one topological sort of a given graph. If the graph is redrawn with all of the vertices in topologically sorted order, all of the arrows lead from earlier to later tasks (Figure 15-24).

Figure 15-24. When the vertices are arranged in topologically sorted order, all of the edges lead from earlier to later tasks.

For a second example, consider the game of Pick Up Sticks (Figure 15-25).

Pick Up Sticks |
---|

Players: 2 or more |

Object: To pick up as many sticks as possible. |

Setup: Drop a number of long, thin sticks in a disorganized pile on the ground. |

Play: In turn, each player picks up a stick. If she successfully extracts a stick without moving any of the others, she wins that stick and gets another turn. |

In practice, this is a game of dexterity. Ignoring this detail, we can phrase it as a topological sorting problem: in what order should the sticks be picked up? Before any stick can be picked up, all of the sticks overlapping it must be picked up. A topological sort is a valid order for picking up the sticks (Figure 15-26).

Figure 15-26. A game of Pick Up Sticks and the corresponding directed acyclic graph. An edge indicates that one stick overlaps another. A topological sort of this graph would give a valid order for picking up the sticks.

We would like to write a program that, given the information on which sticks overlap which other sticks, determines an order in which they may be picked up. A transcript is given in Figure 15-27.

The heart of this program is the topological sorting algorithm. This algorithm is similar to a series of depth-first traversals, one starting from each vertex, but all sharing the same `visited` array.

Figure 15-27. Transcript of the PickUpSticks program.

1 Welcome to Pick Up Sticks. 2 3 How many sticks are there? 4 4 Which sticks overlap stick 0 (separate with spaces)? 5 Which sticks overlap stick 1 (separate with spaces)? 0 6 Which sticks overlap stick 2 (separate with spaces)? 1 3 7 Which sticks overlap stick 3 (separate with spaces)? 0 8 9 The sticks can be picked up in this order: 10 ( 0 3 1 2 ) |

Suppose we do a depth-first traversal starting from some vertex, such as vertex F in Figure 15-26. When we complete this traversal, we have visited everything that can be reached from this vertex. In other words, we have stick F and everything below it. If we add each vertex to the end of the solution list as we visit it, all of the edges will lead backward. If we add these vertices to the beginning instead, all of the edges will lead forward, giving us a topological sort.

The code is given in (Figure 15-28).

Figure 15-28. The topological sort algorithm performs a series of depth-first, postorder traversals. These methods are in the Graph class.

1 /** Return a topological sort of this directed acyclic Graph. */ 2 public List topologicalSort() { 3 LinkedList result = new LinkedList(); 4 boolean[] visited = new boolean[size()]; 5 for (int i = 0; i < size(); i++) { 6 if (!visited[i]) { 7 topologicalTraverse(i, result, visited); 8 } 9 } 10 return result; 11 } 12 13 /** 14 * Visit the vertices reachable from vertex in depth-first 15 * postorder, adding them to result. The array visited 16 * prevents any vertex from being visited more than once. 17 */ 18 protected void topologicalTraverse(int vertex, 19 LinkedList result, 20 boolean[] visited) { 21 visited[vertex] = true; 22 for (Integer i : neighbors(vertex)) { 23 if (!visited[i]) { 24 topologicalTraverse(i, result, visited); 25 } 26 } 27 result.setNext(new ListNode(vertex, result.getNext())); 28 } |

Each vertex is visited exactly once. It takes time in Q(v) to traverse the neighbors of each vertex, so the total running time for `topologicalSort()` is in Q(v2).

The PickUpSticks program is now just a bit of input and output (Figure 15-29).

Figure 15-29. The PickUpSticks program.

1 import java.util.Scanner; 2 3 /** The game of Pick Up Sticks. */ 4 public class PickUpSticks { 5 6 /** For reading from the console. */ 7 public static final Scanner INPUT = new Scanner(System.in); 8 9 /** 10 * Directed acyclic graph indicating which sticks overlap which 11 * others. 12 */ 13 private Graph overlaps; 14 15 /** The number of sticks is set here, but not any overlaps. */ 16 public PickUpSticks(int n) { 17 overlaps = new Graph(n); 18 } 19 20 /** Ask the user which sticks overlap which others. */ 21 protected void determineOverlaps() { 22 for (int i = 0; i < overlaps.size(); i++) { 23 System.out.print("Which sticks overlap stick " + i 24 + " (separate with spaces)? "); 25 Scanner line = new Scanner(INPUT.nextLine()); 26 while (line.hasNextInt()) { 27 overlaps.addEdge(line.nextInt(), i); 28 } 29 } 30 } 3132 /** Print an order in which the sticks can be picked up. */ 33 protected void solve() { 34 System.out.println(" The sticks can be picked up in 35 + "this order:"); 36 System.out.println(overlaps.topologicalSort()); 37 } 38 39 /** Create and solve the game. */ 40 public static void main(String[] args) { 41 System.out.println("Welcome to Pick Up Sticks. "); 42 System.out.print("How many sticks are there? "); 43 PickUpSticks game = new PickUpSticks(INPUT.nextInt()); 44 INPUT.nextLine(); // To clear out input 45 game.determineOverlaps(); 46 game.solve(); 47 } |

We do something unusual on lines 2426 to read several numbers on one line. We read in a line of text, store it in the String `line`, and then create a new Scanner that reads from that line instead of from the keyboard. We can read ints from this Scanner until there are none left. It wouldn't work to read these directly from the keyboard, because the Scanner would have no way of knowing when the user was done entering numbers.

Exercises

15.14 |
Give a topological sort of the graph at the bottom of Figure 15-26. |

15.15 |
Draw the graph described in Figure 15-27. |

15.16 |
In the topological sort algorithm, why is it important that the graph be acyclic? What would our |

15.17 |
Why is it more efficient for |

15.18 |
What is the running time of |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Similar book on Amazon

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net