GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1053

The getShortestpath(nodeIndex) method invokes the getPath(nodeIndex)
method to get a vertices in a shortest path from the specified node to the target node
(lines 89-91).
The printNode(node) method displays a node on the console (lines 93-101).
Listing 28.14 gives a program that prompts the user to enter an initial node and displays the
steps to reach the target node.

L ISTING 28.14

NineTail.java
1 import java.util.Scanner;
2
3 public class NineTail {
4 public static void main(String[] args) {
5 // Prompt the user to enter nine coins' Hs and Ts
6 System.out.print( "Enter the initial nine coins Hs and Ts: " );
7 Scanner input = new Scanner(System.in);
8 String s = input.nextLine();
9

char [] initialNode = s.toCharArray();

initial node

10
11 NineTailModel model = new NineTailModel();
12 java.util.List<Integer> path =
13

create model

model.getShortestPath(NineTailModel.getIndex(initialNode));

get shortest path

14
15 System.out.println( "The steps to flip the coins are " );
16 for ( int i = 0 ; i < path.size(); i++)
17 NineTailModel.printNode(
18 NineTailModel.getNode(path.get(i). int Value()));
19 }
20 }

The program prompts the user to enter an initial node with nine letters with a combination
of H s and T s as a string in line 8, obtains an array of characters from the string (line 9), creates
a graph model to get a BFS tree (line 11), obtains a shortest path from the initial node to the
target node (lines 12-13), and displays the nodes in the path (lines 16-18).

28.26

✓ ✓

How are the nodes created for the graph in NineTailModel ?

Check

28.27

How are the edges created for the graph in NineTailModel ?

Point

28.28

What is returned after invoking getIndex("HTHTTTHHH".toCharArray()) in
Listing 28.13? What is returned after invoking getNode(46) in Listing 28.13?

28.29

If lines 26 and 27 are swapped in Listing 28.13, NineTailModel.java, will the pro-
gram work? Why?

K EY T ERMS

adjacency list 1022
adjacency matrix 1021
adjacent vertices 1018
breadth-first search

incident edges 1018
parallel edge 1018
Seven Bridges of Königsberg 1016

1037 simple graph 1018

complete graph 1018 spanning tree 1018

cycle 1018
degree 1018
depth-first search

tree 1018
undirected graph 1017

1037 unweighted graph 1018

directed graph 1017 weighted graph 1018

graph 1016