Java Reference
In-Depth Information
AbstractGraph<V>.Tree
-root: int
-parent: int[]
-searchOrder: List<Integer>
The root of the tree.
The parents of the vertices.
The orders for traversing the vertices.
+Tree(root: int, parent: int[],
searchOrder: List<Integer>)
Constructs a tree with the specified root, parent, and
searchOrder.
+getRoot(): int
+getSearchOrder(): List<Integer>
+getParent(index: int): int
+getNumberOfVerticesFound(): int
+getPath(index: int): List<V>
Returns the root of the tree.
Returns the order of vertices searched.
Returns the parent for the specified vertex index.
Returns the number of vertices searched.
Returns a list of vertices from the specified vertex index
to the root.
Displays a path from the root to the specified vertex.
Displays tree with the root and all edges.
+printPath(index: int): void
+printTree(): void
F
IGURE
28.11
The
Tree
class describes the nodes with parent-child relationships.
Sections 28.7 and 28.9 will introduce depth-first search and breadth-first search, respec-
tively. Both searches will result in an instance of the
Tree
class.
28.11
✓
✓
Does
AbstractGraph<V>.Tree
implement the
Tree
interface defined in Listing 25.3
Tree.java?
Check
Point
28.12
What method do you use to find the parent of a vertex in the tree?
The depth-first search of a graph starts from a vertex in the graph and visits all
vertices in the graph as far as possible before backtracking.
Key
Point
The depth-first search of a graph is like the depth-first search of a tree discussed in Section 25.2.4,
Tree Traversal. In the case of a tree, the search starts from the root. In a graph, the search can
start from any vertex.
A depth-first search of a tree first visits the root, then recursively visits the subtrees of the
root. Similarly, the depth-first search of a graph first visits a vertex, then it recursively visits
all the vertices adjacent to that vertex. The difference is that the graph may contain cycles,
which could lead to an infinite recursion. To avoid this problem, you need to track the vertices
that have already been visited.
The search is called
depth-first
because it searches “deeper” in the graph as much as possible.
The search starts from some vertex
v
. After visiting
v
, it visits an unvisited neighbor of
v
. If
v
has
no unvisited neighbor, the search backtracks to the vertex from which it reached
v
. We assume
that the graph is connected and the search starting from any vertex can reach all the vertices. If
this is not the case, see Programming Exercise 28.4 for finding connected components in a graph.
28.7.1 Depth-First Search Algorithm
The algorithm for the depth-first search is described in Listing 28.8.
L
ISTING
28.8
Depth-First Search Algorithm
Input: G = (V, E) and a starting vertex v
Output: a DFS tree rooted at v
1 Tree dfs(vertex v) {
2 visit v;
visit
v
Search WWH ::
Custom Search