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;
	}

Problem 3: Dot Output

       public void generateDot() {
		
		System.out.println( "graph G {" );
		for ( int i=0; i<noVertices; i++ ) {
			boolean hasEdges = false; // assume Vertex i has no edges emanating...
			for ( int j=0; j<=i; j++ ) 
				if ( adjMat[i][j] ) {
					hasEdges = true;   // Ah, Vertex i has 1 or more neighbors! 
					System.out.println( i + " -- " + j + ";" );
				}
			// if this vertex is by itself, just print its name
			// the Dot visualizer will display it as a vertex with no edges.
			if ( ! hasEdges )
				System.out.println( i +  ";" );
		}
		System.out.println( "}" );
	}