Jess: Data Structures, Week 8

9.1 Find a topological ordering for the graph in Figure 9.81.
s, G, D, H, A, B, E, I, F, C, t

9.5
a. Find the shortest path from A to all other vertices for the graph in Figure 9.82.
A->B, A->C, A->B->G, A->B->E, A->C->D, A->B->E->F.

b. Find the shortest unweighted path from B to all other vertices for the graph in Figure 9.82.
A->C, A->B, A->B->G, A->B->G->E, A->B->G->E->F, A->B->G->E->D.

9.15 Find a minimum spanning tree for the graph in Figure 9.84 using both Prim’s and Kruskal’s algorithms.

6.2 Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary heap.

After inserting 10:

10

After inserting 12:

  10
 /
12

After inserting 1:

   1
	  / \
12   10

After inserting 14:

     1
	    / \
  12   10 
	  /
14

After inserting 6:

     1
	    / \
   6   10
	  / \
14   12

After inserting 5:

      1
	     / \
	    /   \
   6     5
  / \  /
14  12 10

After inserting 8:

     1
	    / \
	   /   \
  6     5
 / \   / \
14 12 10  8

After inserting 15:

        1
	       / \
	      /   \
     6     5
    / \   / \
   14 12 10  8
  /
15

After inserting 3:

       1
	      / \
     /   \
    3     5
   / \   / \
  6  12 10  8
 / \
15 14

After inserting 9:

         1
	        / \
	       /   \
	      /     \
     3       5
    / \     / \
   /   \   /   \
  6     9 10    8
 / \   /
15 14 12

After inserting 7:

           1
	         /   \
	        /     \
       /       \
      /         \
     3           5
    / \         / \
   /   \       /   \
  6     7     10    8
 / \   / \
15 14 12  9

After inserting 4:

           1
	         /   \
        	/     \
       /       \
      /         \
     3           4
    / \         / \
   /   \       /   \
  6     7     5     8
 / \   / \   /
15 14 12  9 10

After inserting 11:

           1
        	 /   \
        	/     \
       /       \
      /         \
     3           4
    / \         / \
   /   \       /   \
  6     7     5     8
 / \   / \   / \
15 14 12  9 10 11

After inserting 13:

           1
        	 /   \
        	/     \
       /       \
      /         \
     3           4
    / \         / \
   /   \       /   \
  6     7     5     8
 / \   / \   / \   /
15 14 12  9 10 11 13

After inserting 2:

           1
         /   \
        /     \
       /       \
      /         \
     3           2
    / \         / \
   /   \       /   \
  6     7     5     4
 / \   / \   / \   / \
15 14 12  9 10 11 13  8