Programming Assignmer x y project1.pdf Secure h blackboard.olemiss.edu /bbcswebd
ID: 3794013 • Letter: P
Question
Programming Assignmer x y project1.pdf Secure h blackboard.olemiss.edu /bbcswebdav/pid-399467-dt content-rid-1880799 1/cours es/Csci 433 CHEN ALL 2016-2017 SPRG/project1.pdf project1.pdf CSC 433 (Spring 17 Analysis of Algorithms Project 1 Friday, Feb. 15 This project has two parts. In the first part, you need to implement DFS in JAVA. Your program should take as input a graph adjacency matrix, and generate the following: Order in which vertices are first encountered. Assume that the vertices are visited in numerical order when no other order is specified by the search. Order hich verti dead-ends The number of connected components in the graph. Tree edges. Back edges. 1 2 Figure 1: Example graph. Ask me anything A 4) ENG 1:05 AM 2117/2017 R2Explanation / Answer
public class TreeSearch {
void printBFSSequence (int[][] adj, int n){
boolean visit[] = new boolean[n];
int[][] treeEdges = new int[n][n];
int[][] backEdges = new int[n][n];
int count = 0;
int component = 0;
Integer currVisit;
for (int i=0; i< n ; i++)
visit[i] = false;
Queue q = new Queue();
while(count < n) { //checks if all vertices are visited
for (int i = 0; i<n ; i++)
if(!visit[i]){
visit[i]=true;
q.insert(i);
component++; //component is incrementend if any node are left unvisided arter every search
break;
}
while ((currVisit = q.delete())!= null) { //checks if queue is empty.
for(int i = 0; i < n; i++)
if (adj[currVisit][i] != 0)
if(!visit[i]){
q.insert(i);
visit[i] = true;
count++;
treeEdges[currVisit][i] = 1;
}
else
backEdges[currVisit][i] = 1;
System.out.print(currVisit+" ");
}
}
System.out.print(" Number of components: "+ component);
//print tree and back edges;
}
public void printDFSSequence (int[][] adj, int n){
int visit[] = new int[n];
int[][] treeEdges = new int[n][n];
int[][] backEdges = new int[n][n];
int count = 0;
int component = 0;
for (int i=0; i< n ; i++)
visit[i] = 0;
System.out.print(" Dead-end sequence: ");
while(count < n) { //all vertices are not visited
for (int i = 0; i<n ; i++)
if(visit[i] == 0){
count = DFS(adj, n, visit, count, i,treeEdges,backEdges); //DFS works best with recur. algo
component++;
break;
}
}
System.out.print(" Visit sequence: ");
for (int i = 1; i<=n ; i++ )
for (int j =0 ; j<n; j++)
if(visit[j]==i){
System.out.print(" " + j);
break;
}
System.out.print(" Number of components: "+ component);
//do somthing with treeEdges and back edges
}
private int DFS(int[][] adj, int n, int[] visit, int count, int node, int[][] treeEdges, int[][] backEdges) {
visit[node] = ++count;
for (int i=0; i<n; i++)
if (adj[node][i] != 0)
if(visit[i] == 0){
treeEdges[node][i] = 1;
count = DFS(adj,n,visit,count,i,treeEdges, backEdges);
}
else
backEdges[node][i] = 1;
System.out.print(" " + node); //this node is now a dead end
return count;
}
}
class Queue{
private final LinkedList<Integer> ll;
Queue() {
ll = new LinkedList();
}
boolean insert(Integer data) {
return ll.add(data);
}
Integer delete() {
return ll.pollFirst();
}
}
The code is self explanatory. NOTE that the sequence output may vary upon condition..
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.