In representing graphs, we assume that the vertices are numbered 0 through v 1. If it is necessary to associate other data such as city names with the vertices, this can be done with a Map or a direct address table.

In an unweighted graph, we need to keep track only of which vertices are the neighbors of each vertex. The first approach to doing this is the neighbor list representation (Figure 15-8), also known as the adjacency list representation. There is an array containing a chain of ListNodes for each vertex. Each list contains the indices of the neighboring vertices. The amount of memory used is in Q(v + e). The time to check for a particular edge is in O(e).

Figure 15-8. A graph (left) and its neighbor list representation (right).

If a graph is dense, it is better to use a neighbor matrix (Figure 15-9), also known as an adjacency matrix. This is essentially a two-dimensional array of booleans. Element <i, j> of this array is true when there is an edge from vertex i to vertex j. The memory used by this representation is in Q(n2), which is more than the neighbor list representation if the graph is sparse. On the other hand, the time to check for a particular edge is constant.

Figure 15-9. A graph (left) and its neighbor matrix representation (right).

(This item is displayed on page 413 in the print version)

An added advantage of the neighbor matrix representation is that it is easily adapted to handle weighted graphs (Figure 15-10). Instead of storing a boolean at each position, we store the weight of the corresponding edge, or 0 if there is no edge.

Figure 15-10. A weighted graph (left) and its neighbor matrix representation (right).

Code for the neighbor matrix representation is given in Figure 15-11. It can be used to represent an unweighted graph (with the methods `addEdge()` and `hasEdge()`) or a weighted graph (with the methods `setEdge()` and `getEdge()`). The methods `addUndirectedEdge()` and `setUndirectedEdge()` allow us to represent undirected edges as well.

Figure 15-11. Beginning the Graph class.

(This item is displayed on pages 414 - 415 in the print version)

1 /** A potentially weighted graph. */ 2 public class Graph { 3 4 /** 5 * edges[i][j] is the weight of the edge from i to j, or 0 if 6 * there is no such edge. 7 */ 8 private double[][] edges; 9 10 /** The argument is the number of vertices in this Graph. */ 11 public Graph(int vertices) { 12 edges = new double[vertices][vertices]; // All zero by default 13 } 14 15 /** Add an edge of weight 1 from i to j. */ 16 public void addEdge(int i, int j) { 17 edges[i][j] = 1; 18 } 1920 /** Add edges of weight 1 from i to j and from j to i. */ 21 public void addUndirectedEdge(int i, int j) { 22 edges[i][j] = 1; 23 edges[j][i] = 1; 24 } 25 26 /** Return the weight of the edge from i to j. */ 27 public double getEdge(int i, int j) { 28 return edges[i][j]; 29 } 30 31 /** Return true if there is an edge from i to j. */ 32 public boolean hasEdge(int i, int j) { 33 return edges[i][j] != 0.0; 34 } 35 36 /** Set the weight of the edge from i to j. */ 37 public void setEdge(int i, int j, double weight) { 38 edges[i][j] = weight; 39 } 40 41 /** Set the weight of the edge from i to j and from j to i. */ 42 public void setUndirectedEdge(int i, int j, double weight) { 43 edges[i][j] = weight; 44 edges[j][i] = weight; 45 } 46 47 /** Return the number of vertices in this Graph. */ 48 public int size() { 49 return edges.length; 50 } 51 52 } |

It will often prove useful to obtain a List of the neighbors of a vertex, so we provide a method for this (Figure 15-12).

We will add quite a few additional methods to this class, but we have enough now to write the Galaxy program. A UML class diagram is given in Figure 15-13.

The fields and `main()` method for the Galaxy class are given in Figure 15-14.

The constructor (Figure 15-15) is rather lengthy because it has to specify all of the edges on the board. Line 3 creates a Graph with 20 vertices but no edges. Lines 424 add the edges. Specifically, a two-dimensional array of ints is created and the rows are traversed using an enhanced `for` loop. Each row contains two numbers, which are passed to `addUndirectedEdge()` on line 23. On line 25, `scores` has length 3 so that we can refer to `scores[1]` and `scores[2]`; `scores[0]` is not used. Line 26 allocates the array `stars`. Line 27 gives a random star to player 1. The loop on lines 2834 gives a random star to player 2; it usually runs only once, but it is set up to try again if player 2 happens to get the same star as player 1.

Figure 15-12. The `neighbors()` method.

1 /** Return a List of the neighbors of vertex i. */ 2 public List neighbors(int i) { 3 List result = new ArrayList(); 4 for (int j = 0; j < size(); j++) { 5 if (hasEdge(i, j)) { 6 result.add(j); 7 } 8 } 9 return result; 10 } |

Figure 15-13. UML class diagram showing the Galaxy and Graph classes. For completeness, all of the Graph methods are shown, even those not used in Galaxy.

Figure 15-14. Fields and `main()` method for the Galaxy class.

1 import java.util.Scanner; 2 3 /** The game of Galaxy. */ 4 public class Galaxy { 5 6 /** For reading from the console. */ 7 public static final Scanner INPUT = new Scanner(System.in); 8 9 /** Edges linking the stars together. */ 10 private Graph edges; 11 12 /** Points earned so far by each player. */ 13 private int[] scores; 14 15 /** Number of player controlling each star, or zero if none. */ 16 private int[] stars; 17 18 /** Create and play the game. */ 19 public static void main(String[] args) { 20 Galaxy game = new Galaxy(); 21 System.out.println("Welcome to Galaxy. "); 22 game.play(); 23 } 24 25 } |

Figure 15-15. Constructor for the Galaxy class.

1 /** Build the galaxy and give one star to each player. */ 2 public Galaxy() { 3 edges = new Graph(20); 4 for (int[] pair : new int[][] 5 {{0, 16}, {0, 17}, {0, 19}, 6 {1, 2}, {1, 8}, 7 {2, 4}, {2, 5}, {2, 8}, 8 {3, 8}, {3, 9}, {3, 16}, 9 {4, 5}, {4, 8}, 10 {5, 6}, {5, 7}, 11 {6, 7}, 12 {7, 8}, {7, 10}, {7, 11}, {7, 12}, {7, 18}, 13 {8, 10}, {8, 14}, 14 {9, 10}, {9, 13}, 15 {10, 12}, {10, 13}, 16 {11, 14}, 17 {11, 19}, 18 {12, 14}, {12, 16}, {12, 19},19 {13, 15}, {13, 16}, 20 {15, 16}, {15, 18}, 21 {16, 17}, 22 {18, 19}}) { 23 edges.addUndirectedEdge(pair[0], pair[1]); 24 } 25 scores = new int[3]; // Initially all zeroes 26 stars = new int[20]; // Initially all zeroes 27 stars[(int)(Math.random() * 20)] = 1; 28 do { 29 int star = (int)(Math.random() * 20); 30 if (stars[star] == 0) { 31 stars[star] = 2; 32 return; 33 } 34 } while (true); 35 } |

In writing the `toString()` method (Figure 15-16), we opt for a simple table.

Figure 15-16. The `toString()` method from the Galaxy class.

1 public String toString() { 2 StringBuilder result = new StringBuilder(); 3 result.append("Star Owner Neighbors "); 4 for (int i = 0; i < 20; i++) { 5 result.append(i + " " + stars[i] + " " 6 + edges.neighbors(i) + " "); 7 } 8 for (int p = 1; p <= 2; p++) { 9 result.append("Player " + p + ": " + scores[p] + " "); 10 } 11 return result.toString(); 12 } |

The `play()` method (Figure 15-17) is one of the simpler ones we've written. In the loop, lines 68 read a star number from the user. Line 9 gives the user control of that star. Lines 1014 add any points scored. Line 15 toggles whose turn it is.

Exercises

15.9 |
How can the neighbor list representation (Figure 15-8) be modified to handle weighted graphs? |

Figure 15-17. The play() method from the Galaxy class.

1 /** Play the game. */ 2 public void play() { 3 int player = 1; 4 for (int turn = 0; turn < 18; turn++) { 5 System.out.println(this); 6 System.out.print("Player " + player + ", pick a star: "); 7 int star = INPUT.nextInt(); 8 INPUT.nextLine(); // To clear out input 9 stars[star] = player; 10 for (int s : edges.neighbors(star)) { 11 if (stars[s] == 3 - player) { 12 scores[player]++; 13 } 14 } 15 player = 3 - player; 16 } 17 System.out.println(this); 18 } |

15.10 |
What is the order of the running time of the |

15.11 |
A graph could be represented as a List of edges, with each edge containing the indices of the two vertices connected by the edge. How much memory is used by this representation? How long does it take to check for the existence of a particular edge? How can this representation be modified to handle weighted graphs? |

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

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