Question: See Code Below Questions 1. Draw the graph in the input file tinyG.txt and determine the order that vertices will be visited using dfs starting
See Code Below Questions
1. Draw the graph in the input file tinyG.txt and determine the order that vertices will be visited using dfs starting at vertex 0. Verify your result by running the code.
2. Complete the method connectedComponent which should print the vertices that are contained in each of the connected components of the graph. You will want to use dfs to do so. Test your code on tinyG.txt
3. Make a small modification to the code so that the graphs now have directed rather than undirected edges. Then complete the code for determining if a graph contains a cycle using a modified dfs. Test your code on graph1.txt, graph2.txt, and graph3.txt.
Graph.java
*/ @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Graph {
private final int V;
private int E;
private Bag
private Mark[] marked;
private enum Mark {WHITE,GRAY,BLACK};
/**
* Initializes an empty graph with V vertices and 0 edges.
* param V the number of vertices
* @throws java.lang.IllegalArgumentException if V < 0
*/
public Graph(int V) {
if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
adj = (Bag
marked = new Mark[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag
marked[v] = Mark.WHITE;
}
}
/**
* Initializes a graph from an input stream.
* The format is the number of vertices V,
* followed by the number of edges E,
* followed by E pairs of vertices, with each entry separated by whitespace.
* @param in the input stream
* @throws java.lang.IndexOutOfBoundsException if the endpoints of any edge are not in prescribed range
* @throws java.lang.IllegalArgumentException if the number of vertices or edges is negative
*/
public Graph(In in) {
this(in.readInt());
int E = in.readInt();
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
addEdge(v, w);
}
}
/**
* Initializes a new graph that is a deep copy of G.
* @param G the graph to copy
*/
public Graph(Graph G) {
this(G.V());
this.E = G.E();
for (int v = 0; v < G.V(); v++) {
// reverse so that adjacency list is in same order as original
Stack
for (int w : G.adj[v]) {
reverse.push(w);
}
for (int w : reverse) {
adj[v].add(w);
}
}
}
/**
* Returns the number of vertices in the graph.
* @return the number of vertices in the graph
*/
public int V() {
return V;
}
/**
* Returns the number of edges in the graph.
* @return the number of edges in the graph
*/
public int E() {
return E;
}
/**
* Adds the undirected edge v-w to the graph.
* @param v one vertex in the edge
* @param w the other vertex in the edge
* @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V
*/
public void addEdge(int v, int w) {
if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
if (w < 0 || w >= V) throw new IndexOutOfBoundsException();
E++;
adj[v].add(w);
adj[w].add(v);
}
private void dfs(int v){
System.out.println("visiting:"+v);
marked[v]=Mark.GRAY;
for (int w: adj[v]){
if (marked[w] == Mark.WHITE)
dfs(w);
}
marked[v]= Mark.BLACK;
}
private void connectedComponents(){
// To be completed
}
private boolean cycle(){
// To be completed
return false;
}
/**
* Returns the vertices adjacent to vertex v.
* @return the vertices adjacent to vertex v as an Iterable
* @param v the vertex
* @throws java.lang.IndexOutOfBoundsException unless 0 <= v < V
*/
public Iterable
if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
return adj[v];
}
/**
* Returns a string representation of the graph.
* This method takes time proportional to E + V.
* @return the number of vertices V, followed by the number of edges E,
* followed by the V adjacency lists
*/
public String toString() {
StringBuilder s = new StringBuilder();
String NEWLINE = System.getProperty("line.separator");
s.append(V + " vertices, " + E + " edges " + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (int w : adj[v]) {
s.append(w + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
/**
* Unit tests the Graph data type.
*/
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
StdOut.println(G);
G.dfs(0);
}
}
tinyG.txt
13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3
graph1.txt
7 8 0 1 1 2 1 3 3 0 3 2 3 4 5 6 6 3
graph2.txt
7 8 0 1 1 2 1 3 3 2 3 4 4 6 5 6 6 3
graph3.txt
7 8 0 1 1 2 1 3 3 2 3 4 5 6 6 3 6 4
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help