Question: Do both of the following methods using an adjacency List and an adjacency matrix. public void breadthFirstTraversal(int start) { } public void depthFirstTraversal(int start) {
Do both of the following methods using an adjacency List and an adjacency matrix.
public void breadthFirstTraversal(int start) {
}
public void depthFirstTraversal(int start) {
}
public class AdjListIntVertices {
private int N;
private HashSet
@SuppressWarnings("unchecked")
public AdjListIntVertices(String fname) {
try {
Scanner input = new Scanner(new File(fname));
N = input.nextInt();
adjList = (HashSet
.newInstance(new HashSet
for (int r = 0; r < N; r++) {
adjList[r] = new HashSet
for (int c = 0; c < N; c++) {
if (input.nextInt() == 1) {
adjList[r].add(c);
}
}
}
input.close();
} catch (Exception e) {
System.err.println("Problem during file input");
System.exit(0);
}
}
public void breadthFirstTraversal(int start) {
}
public void depthFirstTraversal(int start) {
}
public Set
HashSet
HashSet
reachable.add(startVertex);
recentAdditions.add(startVertex);
do {
HashSet
recentAdditions);
recentAdditions.clear();
for (int v : copyRecentAdditions) {
for (int i = 0; i < N; i++) {
if (adjList[v].contains(i) && !reachable.contains(i)) {
recentAdditions.add(i);
}
}
}
reachable.addAll(recentAdditions);
} while (recentAdditions.size() != 0);
return reachable;
}
}
public class AdjMatrixIntVertices {
private int N;
private boolean[][] adjMatrix;
public AdjMatrixIntVertices(String fname) {
try {
Scanner input = new Scanner(new File(fname));
N = input.nextInt();
adjMatrix = new boolean[N][];
for (int r = 0; r < N; r++) {
adjMatrix[r] = new boolean[N];
for (int c = 0; c < N; c++) {
adjMatrix[r][c] = input.nextInt() == 1;
}
}
input.close();
} catch (Exception e) {
System.err.println("Problem during file input");
System.exit(0);
}
}
public void breadthFirstTraversal(int start) {
}
public void depthFirstTraversal(int start) {
}
public Set
HashSet
HashSet
reachable.add(startVertex);
recentAdditions.add(startVertex);
do {
HashSet
recentAdditions);
recentAdditions.clear();
for (int v : copyRecentAdditions) {
for (int i = 0; i < N; i++) {
if (adjMatrix[v][i] && !reachable.contains(i)) {
recentAdditions.add(i);
}
}
}
reachable.addAll(recentAdditions);
} while (recentAdditions.size() != 0);
return reachable;
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help