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

134 return true ;

135 }
136 else {

137 return false ;

138 }
139 }
140
141 @Override /** Add an edge to the graph */
142 public boolean addEdge( int u, int v) {

addEdge overloaded

143 return addEdge( new Edge(u, v));

144 }
145
146

/** Edge inner class inside the AbstractGraph class */

147 public static class Edge {

Edge inner class

148 public int u; // Starting vertex of the edge

149 public int v; // Ending vertex of the edge

150
151 /** Construct an edge for (u, v) */

152 public Edge( int u, int v) {

153 this .u = u;

154 this .v = v;

155 }
156
157

public boolean equals(Object o) {

158 return u == ((Edge)o).u && v == ((Edge)o).v;

159 }
160 }
161
162 @Override /** Obtain a DFS tree starting from vertex v */
163 /** To be discussed in Section 28.7 */
164 public Tree dfs( int v) {
165 List<Integer> searchOrder = new ArrayList<>();
166 int [] parent = new int [vertices.size()];
167 for ( int i = 0 ; i < parent.length; i++)
168 parent[i] = -1 ; // Initialize parent[i] to -1
169
170

dfs method

// Mark visited vertices

171 boolean [] isVisited = new boolean [vertices.size()];

172
173 // Recursively search
174 dfs(v, parent, searchOrder, isVisited);
175
176 // Return a search tree

177 return new Tree(v, parent, searchOrder);

178 }
179
180 /** Recursive method for DFS search */
181 private void dfs( int u, int [] parent, List<Integer> searchOrder,
182 boolean [] isVisited) {
183 // Store the visited vertex
184 searchOrder.add(u);
185 isVisited[u] = true ; // Vertex v visited
186
187 for (Edge e : neighbors.get(u)) {
188 if (!isVisited[e.v]) {
189 parent[e.v] = u; // The parent of vertex e.v is u
190 dfs(e.v, parent, searchOrder, isVisited); // Recursive search
191 }
192 }
193 }