CSC212 Lab 13 Solutions 2014

--D. Thiebaut (talk) 08:07, 19 November 2014 (EST)

---

Problems 1 & 2

You may want to keep the print statements in the DFS methods for Problem 1, and comment them out for Problem 2.

	private void recurseDFS(int v) {
		visited[v] = true;
		
		for (int w : adj(v))
			if (!visited[w]) {
				System.out.println( String.format( "visiting Edge (%d)---(%d)", v, w ) );
				recurseDFS(w);
			}
	}

	public void DFS(int v) {
		System.out.print( "DFS starting on " + v +":\n");
		visited = new boolean[noVertices];
		recurseDFS(v);
		System.out.println();
	}

	public boolean isConnected() {
		DFS( 0 );
		for ( int i=0; i<noVertices; i++ )
			if ( !visited[i] )
				return false;
		return true;
	}
	
	public int noConnectedComponents() {
		visited = new boolean[noVertices];
		int count = 0;
		for ( int v=0; v < noVertices; v++ ) {
			if ( ! visited[ v ] ) {
				count++;
				System.out.println( "\nComponent # " + count + " starting with Vertex " + v  );
				recurseDFS( v );
			}
		}
		System.out.println( "\n" );
		return count;
	}