Chapter 27 Graphs and Applications

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 1
 Objectives
 To model real-world problems using graphs and explain the Seven
Bridges of Königsberg problem (§27.1).
 To describe the graph terminologies: vertices, edges, simple graphs,
weighted/unweighted graphs, and directed/undirected graphs (§27.2).
 To represent vertices and edges using lists, adjacent matrices, and
adjacent lists (§27.3).
 To model graphs using the Graph interface, the AbstractGraph class,
and the UnweightedGraph class (§27.4).
 To represent the traversal of a graph using the AbstractGraph.Tree
class (§27.5).
 To design and implement depth-first search (§27.6).
 To design and implement breadth-first search (§27.7).
 To solve the nine-tail problem using breadth-first search (§27.8).
 To solve the Knight’s Tour problem by reducing it to a Hamiltonian
path problem (§27.9).

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 2
 Modeling Using Graphs
Seattle

Boston

Chicago

New York

Denver

San Francisco Kansas City

Los Angeles Atlanta

Dallas

Houston

Miami

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 3
 Weighted Graph Animation
www.cs.armstrong.edu/liang/animation/GraphLearningTool.html

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 4
Seven Bridges of Königsberg
A

C
D
Island 1
Island 2

C D

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 5
 Basic Graph Terminologies
What is a graph?
Define a graph
Directed vs. undirected graphs
Weighted vs. unweighted graphs
Adjacent vertices
Incident
Degree
Neighbor
loop
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 6
 Basic Graph Terminologies
Parallel edge
Simple graph
Complete graph
Spanning tree

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 7
 Representing Graphs
Representing Vertices
Representing Edges: Edge Array
Representing Edges: Edge Objects
Representing Edges: Adjacency Matrices
Representing Edges: Adjacency Lists

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 8
 Representing Vertices
String[] vertices = {“Seattle“, “San Francisco“, … };

City[] vertices = {city0, city1, … };

public class City {

List<String> vertices;

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 9
 Representing Edges: Edge Array
int[][] edges = {{0, 1}, {0, 3} {0, 5}, {1, 0}, {1, 2}, … };

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 10
 Representing Edges: Edge Object
public class Edge {
int u, v;
public Edge(int u, int v) {
this.u = u;
this.v = v;
}

List<Edge> list = new ArrayList<Edge>();

list.add(new Edge(0, 1)); list.add(new Edge(0, 3)); …

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 11
 Representing Edges: Adjacency
Matrix
int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Seattle
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // San Francisco
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // Los Angeles
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // Denver
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // Kansas City
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // Chicago
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Boston
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // New York
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // Atlanta
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // Miami
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // Dallas
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // Houston
};
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 12
 Representing Edges: Adjacency List
List<Integer>[] neighbors = new LinkedList<Integer>[12];

Seattle neighbors[0] 1 3 5
San Francisco neighbors[1] 0 2 3
Los Angeles neighbors[2] 1 3 4 10
Denver neighbors[3] 0 1 2 4 5
Kansas City neighbors[4] 2 3 5 7 8 10
Chicago neighbors[5] 0 3 4 7 11
Boston neighbors[6] 5 7
New York neighbors[7] 4 5 6 8
Atlanta neighbors[8] 4 7 9 10 11
Miami neighbors[9] 8 11
Dallas neighbors[10]
2 4 8 11
Houston neighbors[11]
10 8 9

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 13
 Modeling Graphs

UnweightedGraph

Graph AbstractGraph
WeightedGraph

Interface Abstract Class Concrete Classes

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 14
 «interface» The generic type V is the type for vertices.
Graph<V>
+getSize(): int Returns the number of vertices in the graph.
+getVertices(): List<V> Returns the vertices in the graph.
+getVertex(index: int): V Returns the vertex object for the specified vertex index.
+getIndex(v: V): int Returns the index for the specified vertex.
+getNeighbors(index: int): List<Integer> Returns the neighbors of vertex with the specified index.
+getDegree(index: int): int Returns the degree for a specified vertex index.
+getAdjacencyMatrix(): int[][]
+printAdjacencyMatrix(): void
Returns the adjacency matrix.
Prints the adjacency matrix.
Graph
+printEdges(): void Prints the edges.
+dfs(index: int): AbstractGraph<V>.Tree Obtains a depth-first search tree.
+bfs(index: int): AbstractGraph<V>.Tree Obtains a breadth-first search tree.

AbstractGraph<V>
AbstractGraph
#vertices: List<V> Vertices in the graph.
#neighbors: List<List<Integer>> Neighbors for each vertex in the graph.

#AbstractGraph(edges: int[][], vertices: V[]) Constructs a graph with the specified edges and vertices

#AbstractGraph(edges: List<Edge>,
in arrays.
Constructs a graph with the specified edges and vertices UnweightedGraph
vertices: List<V>) stored in lists.
#AbstractGraph(edges: int[][], Constructs a graph with the specified edges in an array
numberOfVertices: int) and the integer vertices 1, 2, ....
#AbstractGraph(edges: List<Edge>, Constructs a graph with the specified edges in a list and
numberOfVertices: int) the integer vertices 1, 2, ….
Inner classes Tree is defined here
TestGraph
UnweightedGraph<V>
+UnweightedGraph(edges: int[][], vertices: Constructs a graph with the specified edges and vertices
V[]) in arrays.
+UnweightedGraph(edges: List<Edge>,
vertices: List<V>)
Constructs a graph with the specified edges and vertices
stored in lists. TestGraph
+UnweightedGraph(edges: List<Edge>, Constructs a graph with the specified edges in an array
numberOfVertices: int) and the integer vertices 1, 2, ....
+UnweightedGraph(edges: int[][], Constructs a graph with the specified edges in a list and
numberOfVertices: int) the integer vertices 1, 2, ….

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 15
 Graph Visualization

Displayable Interface DisplayUSMap

GraphView Run
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 16
 Graph Traversals
Depth-first search and breadth-first search

Both traversals result in a spanning tree, which can be

modeled using a class.
AbstractGraph.Tree

-root: int The root of the tree.

-parent: int[] The parents of the vertices.
-searchOrders: java.util.List<Integer> The orders for traversing the vertices.
+Tree(root: int, parent: int[], Constructs a tree with the specified root, parent, and
searchOrders: List<Integer>) searchOrders.
+Tree(root: int, parent: int[]) Constructs a tree with the specified root and parent with
no specified searchOrders.
+getRoot(): int Returns the root of the tree.
+getSearchOrders(): List Returns the order of vertices searched.
+getParent(v: int): int Returns the parent of vertex v.
+getNumberOfVerticesFound(): int Returns the number of vertices searched.
+pathIterator(v: int): java.util.Iterator Returns an iterator for the path from the root to vertex v.
+printPath(v: int): void Displays a path from the root to the specified vertex.
+printTree(): void Displays tree with the root and all edges.

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 17
 Depth-First Search
The depth-first search of a graph is like the depth-first search of a
tree discussed in §25.2.3, “Tree Traversal.” In the case of a tree, the
search starts from the root. In a graph, the search can start from any
vertex.

dfs(vertex v) {
visit v;
for each neighbor w of v
if (w has not been visited) {
dfs(w);
}
}
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 18
 Depth-First Search Example

0 1 0 1 0 1

2 2 2

3 4 3 4 3 4

0 1 0 1

2 2

3 4 3 4

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 19
 Depth-First Search Example
Seattle

2097 Boston
983
Chicago
1331 214
807
1003 New York
787
Denver
533
1267 1260
599
888
San Francisco 1015 Kansas City

381 1663
864

496
Los Angeles 1435 Atlanta
781
810
Dallas
661
239

Houston 1187

Miami

TestDFS TestDFS
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 20
 Applications of the DFS
Detecting whether a graph is connected. Search the graph starting from any
vertex. If the number of vertices searched is the same as the number of
vertices in the graph, the graph is connected. Otherwise, the graph is not
connected (See Exercise 27.2.)

Detecting whether there is a path between two vertices. (See Exercise 27.3)

Finding a path between two vertices. (See Exercise 27.3)

Finding all connected components. A connected component is a maximal

connected subgraph in which every pair of vertices are connected by a path.
(See Exercise 27.2)

Detecting whether there is a cycle in the graph. (See Exercise 27.4)

Finding a cycle in the graph. (See Exercise 27.5)

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 21
 Breadth-First Search
The breadth-first traversal of a graph is like the breadth-
first traversal of a tree discussed in §25.2.3, “Tree
Traversal.” With breadth-first traversal of a tree, the
nodes are visited level by level. First the root is visited,
then all the children of the root, then the grandchildren of
the root from left to right, and so on.

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 22
 Breadth-First Search Algorithm
bfs(vertex v) {
create an empty queue for storing vertices to be visited;
add v into the queue;
mark v visited;
while the queue is not empty {
dequeue a vertex, say u, from the queue
process u;
for each neighbor w of u
if w has not been visited {
add w into the queue;
mark w visited;
}
}
}
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 23
 Breadth-First Search Example

0 1 0 1 0 1

2 2 2

3 4 3 4 3 4

Queue: 0 isVisited[0] = true

Queue: 1 2 3 isVisited[1] = true, isVisited[2] = true,
isVisited[3] = true
Queue: 2 3 4
isVisited[4] = true

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 24
 Breadth-First Search Example
Seattle

2097 Boston
983
Chicago
1331 214
807
1003 New York
787
Denver
533
1267 1260
599
888
San Francisco 1015 Kansas City

381 1663
864

496
Los Angeles 1435 Atlanta
781
810
Dallas
661
239

Houston 1187

Miami

TestBFS TestBFS
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 25
 Applications of the BFS
Detecting whether a graph is connected. A graph is connected if there is a path
between any two vertices in the graph.

Detecting whether there is a path between two vertices.

Finding a shortest path between two vertices. You can prove that the path between
the root and any node in the BFS tree is the shortest path between the root and the
node (see Review Question 27.10).

Finding all connected components. A connected component is a maximal connected

subgraph in which every pair of vertices are connected by a path.

Detecting whether there is a cycle in the graph. (See Exercise 27.4)

Finding a cycle in the graph. (See Exercise 27.5)

Testing whether a graph is bipartite. A graph is bipartite if the vertices of the graph
can be divided into two disjoint sets such that no edges exist between vertices in the
same set. (See Exercise 27.8)
Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 26
 The Nine Tail Problem
The problem is stated as follows. Nine coins are placed in a
three by three matrix with some face up and some face
down. A legal move is to take any coin that is face up and
reverse it, together with the coins adjacent to it (this does
not include coins that are diagonally adjacent). Your task is
to find the minimum number of the moves that lead to all
coins face down.

H H H H H H T T T
T T T T H T T T T
H H H T T T T T T

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 27
 The Nine Tail Problem

NineTailModel NineTailApp NineTailApp

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 28
 The Hamiltonian Path Problem
A Hamiltonian path in a graph is a path that visits
each vertex in the graph exactly once. A
Hamiltonian cycle is a cycle that visits each vertex
in the graph exactly once and returns to the
starting vertex.
A Hamiltonian path and cycle have many
applications.

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 29
 The Knight’s Tour Problem
The Knight’s Tour is a well-known classic problem. The
objective is to move a knight, starting from any square on
a chessboard, to every other square once. Note that the
knight makes only L-shape moves (two spaces in one
direction and one space in a perpendicular direction). As
shown in Figure 27.19(a), the knight can move to eight
squares.
0 1 2 3 4 5 6 7

0
1

3
4

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 30
 Find a Knight’s Tour
To solve the Knight’s Tour problem, create a graph with
64 vertices representing all the squares in the chessboard.
Two vertices are connected if a knight can move between
the two vertices.

KnightTourModel KnightTourApp KnightTourApp

Liang, Introduction to Java Programming, Eighth Edition, (c) 2011 Pearson Education, Inc. All rig
hts reserved. 0132130807 31