Please help me with the Textbook solutions for Data Structures Abstreaction and
ID: 656366 • Letter: P
Question
Please help me with the Textbook solutions for Data Structures Abstreaction and Design Using Java 2nd Edition Chapter 10 Problem 8PP
We can use Matrix and List to present a graph. A third possible representation of a graph is to use the TreeSet class to contain the edges. By defining a comparator that compares first on the source vertex and then the destination vertex, we can use the subSet method (of the TreeSet class) to create a view that contains only edges originating at a specified vertex and then use the iterator of that view to iterate through edges. Design and implement a class that meets the requirements of the Graph interface and uses a TreeSet to hold the edges. In addition, you must add the depthFirstSearch method to your class.
Hints:When creating your Comparator class, please be aware that since a TreeSet ISA set, all elements of the set must be unique. It decides on the uniqueness of elements by the compareTo and/or compare methods (i.e., if two elements are equal, then they are not unique) . You will most likely use the first version of the subSet method: NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
Explanation / Answer
import java.util.*;
import Trees.State;
public class TreeSet
{
public void dfs(Node root)
{
if(root == null) return;
System.out.print(root.getVertex() + " ");
root.state = State.Visited;
for(Node n: root.getChild())
{
if(n.state == State.Unvisited)
{
dfs(n);
}
}
}
public void bfs(Node root)
{
Queue<Node> queue = new LinkedList<Node>();
if(root == null) return;
root.state = State.Visited;
queue.add(root);
while(!queue.isEmpty())
{
Node r = queue.remove();
System.out.print(r.getVertex() + " ");
for(Node n: r.getChild())
{
if(n.state == State.Unvisited)
{
queue.add(n);
n.state = State.Visited;
}
}
}
}
public static Tree createNewTree()
{
Tree g = new Tree();
Node[] temp = new Node[8];
temp[0] = new Node("A", 3);
temp[1] = new Node("B", 3);
temp[2] = new Node("C", 1);
temp[3] = new Node("D", 1);
temp[4] = new Node("E", 1);
temp[5] = new Node("F", 1);
temp[0].addChildNode(temp[1]);
temp[0].addChildNode(temp[2]);
temp[0].addChildNode(temp[3]);
temp[1].addChildNode(temp[0]);
temp[1].addChildNode(temp[4]);
temp[1].addChildNode(temp[5]);
temp[2].addChildNode(temp[0]);
temp[3].addChildNode(temp[0]);
temp[4].addChildNode(temp[1]);
temp[5].addChildNode(temp[1]);
for (int i = 0; i < 7; i++)
{
g.addNode(temp[i]);
}
return g;
}
public static void main(String[] args)
{
Tree gDfs = createNewTree();
TreeSet s = new TreeSet();
System.out.println("--------------DFS---------------");
s.dfs(gDfs.getNode()[0]);
System.out.println();
System.out.println();
Tree gBfs = createNewTree();
System.out.println("---------------BFS---------------");
s.bfs(gBfs.getNode()[0]);
}
}
Node.java:
package Trees;
import Trees.State;
public class Node
{
public Node[] child;
public int childCount;
private String vertex;
public State state;
public Node(String vertex)
{
this.vertex = vertex;
}
public Node(String vertex, int childlen)
{
this.vertex = vertex;
childCount = 0;
child = new Node[childlen];
}
public void addChildNode(Node adj)
{
adj.state = State.Unvisited;
if(childCount < 30)
{
this.child[childCount] = adj;
childCount++;
}
}
public Node[] getChild()
{
return child;
}
public String getVertex()
{ return vertex;
}
}