Compsci 100, Fall 2009, Dec 4 Recitation
In this recitation you'll do one new
APT GalaxyTrip to review the graph concepts of DFS/BFS and connected components.
The steps below are suggested in solving the problem, you'll go over
each one in order.
- Create a representation of the graph represented by the
dependencies data, e.g., either an adjacency list or
an adjacency matrix. Is this graph directed or undirected? Why is it
easier to iterative over a given vertex's adjacent vertices
using an adjaceny list rather than a matrix?
- If you use a map of vertices to a list of adjacent vertices to
represent the graph, complete the code below and answer
questions about it.
<![CDATA[
Map<String, List<String>> myGraph = new TreeMap<String, List<String>>();
int vertex = 0;
for(String s : dependencies){
String sv = ""+vertex;
vertex++;
myGraph.put(sv,new ArrayList<String>());
List<String> list = myGraph.get(sv);
if (s.equals("")) continue; // no vertices, don't parse
String[] a = s.split(" ");
// add code here
}
]]>
- Why is a map of strings to list of strings used instead of integers
to list of integers to represent the graph?
- Complete the add code here section to add adjacent
vertices
to
sv which is the current vertex whose adjacent verticies
are being processed. Why is ""+vertex used?
- If
LinkedList was used in place
of ArrayList in the code above, would the code still
compile and run? Why?
- To find the size of a connected component which in this
problem is the number of machines that depend on each other
starting
from a specific machine, you can do a depth-first search (or a breadth
first) and count the number of nodes visited.
<![CDATA[
Set<String> myVisited = new TreeSet<String>();
private int dfs(String vertex){
if (myVisited.contains(vertex)) return 0;
myVisited.add(vertex);
int total = 1; // count myself
for(String adj : myGraph.get(vertex)){
total += dfs(adj);
}
return total;
}
]]>
- Would it be possible to move the
myVisited.add statement
to just before the return statement? Why?
- How could you write this using a Stack instead of recursion?
- In a few words, why does this version of DFS return the size of a
connected component starting with
vertex?
- Write code to call the version of
dfs above for every
vertex represented in dependencies, i.e., from 0 to
the number of entries and to add the values returned to a list
of integers representing the sizes of all connected components (don't
store zero sizes).
<![CDATA[
List<Integer> sizes = new ArrayList<Integer>();
for(int k=0; k < dependencies.length; k++){
}
]]>
- The code below uses the list
sizes from above
and finds all possible values that can be created by adding together
elements of sizes. You should try to understand
how this code sets possible[v] to true if and only if
the value of v can be created by summing elements of
sizes together. Why does the inner-loop start at the end
of possible?
<![CDATA[
boolean[] possible = new boolean[1000];
Arrays.fill(possible,false);
possible[0] = true;
for(int value : sizes){
for(int k=possible.length-1; k >= 0; k--){
if (possible[k]){
possible[k+value] = true;
}
}
}
]]>
- Now that
possible[v] is true iff v is a
valid value for the galactic trip, complete the APT. What code
must be added?