To answer this question, you also need to write the algorithm and the code to solve this problem. You can find the Java code for depth first search and breadth first search as below. You can use C++, or Java, or Python.

6. a. Explain how one can check a graphs acyclicity by using breadth-first

search.

b. Does either of the two traversalsDFS or BFSalways find a cycle faster

than the other? If you answer yes, indicate which of them is better and

explain why it is the case; if you answer no, give two examples supporting

your answer.

package depthfirstsearch; public class DepthFirstSearch { // recursive dfs private static void dfs_rec(ArrayList> adjLists, boolean[] visited, int v){ visited[v] = true; System.out.print(v + " "); //for(int w : adjLists.get(v)){ for(int w : adjLists.get(v)){ if(!visited[w]){ dfs_rec(adjLists, visited, w); } } } //http://mathworld.wolfram.com/AdjacencyMatrix.html //http://xlinux.nist.gov/dads/HTML/adjacencyListRep.html // Usually dfs_rec() would be sufficient. However, if we don't want to pass // a boolean array to our function, we can use another function dfs(). // We only have to pass the adjacency list and the source node to dfs(), // as opposed to dfs_rec(), where we have to pass the boolean array additionally. public static void dfs(ArrayList> adjLists, int s){ int n = adjLists.size(); boolean[] visited = new boolean[n]; dfs_rec(adjLists, visited, s); } // ---------------------------------------------------------------------- // Testing our implementation public static void main(String[] args) { // Create adjacency list representation ArrayList> adjLists = new ArrayList>(); final int n = 7; // Add an empty adjacency list for each vertex for(int v=0; v()); } // insert neighbors of vertex 0 into adjacency list for vertex 0 adjLists.get(0).add(1); adjLists.get(0).add(2); adjLists.get(0).add(3); // insert neighbors of vertex 1 into adjacency list for vertex 1 adjLists.get(1).add(5); adjLists.get(1).add(6); // insert neighbors of vertex 2 into adjacency list for vertex 2 adjLists.get(2).add(4); // insert neighbors of vertex 3 into adjacency list for vertex 3 adjLists.get(3).add(2); adjLists.get(3).add(4); // insert neighbors of vertex 4 into adjacency list for vertex 4 adjLists.get(4).add(1); // insert neighbors of vertex 5 into adjacency list for vertex 5 // -> nothing to do since vertex 5 has no neighbors // insert neighbors of vertex 6 into adjacency list for vertex 5 adjLists.get(6).add(4); // Print vertices in the order in which they are visited by dfs() dfs(adjLists, 0); } }

package bfs; public class BFS { private Queue queue; public BFS() { queue = new LinkedList(); //http://learningviacode.blogspot.com/2013/06/queues-in-java.html } public void bfs(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix[source].length - 1; int[] visited = new int[number_of_nodes + 1]; int i, element; visited[source] = 1; queue.add(source); while (!queue.isEmpty()) { element = queue.remove(); i = element; System.out.print(i + "\t"); while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { queue.add(i); visited[i] = 1; } i++; } } } public static void main(String... arg) { int number_no_nodes, source; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_no_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_no_nodes; i++) for (int j = 1; j <= number_no_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); System.out.println("The BFS traversal of the graph is "); BFS bfs = new BFS(); bfs.bfs(adjacency_matrix, source); } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } scanner.close(); } }