# Block 7: Trees and graphs

 Draw a complete binary search tree containing 1,2,3,4,5 and 6. Here is an adjacency matrix for a weighted directed graph. Cells contain weights of edges, empty cells mean there is no edge. Complete the drawing of the graph to the right by adding directed edges and weights.  In the same graph as B), one path from A to E is A→C→E, with a combined weight of 9. Write three other paths from A to E, and the combined weight of each. A → D → E (11) A → B → C → E (9) A → C → D → E (15) If a multigraph has E edges, what is the maximal/minimal number of nodes it may have? Answer in O notation. Assume the graph is undirected and connected (no unreachable nodes). Maximal N = E+1 , O(E) Minimal N = 1, O(E) Given this weighted directed graph, we use Dijkstras Algorithm (3 points) to find the shortest path from A to all other (reachable) nodes. Write the nodes it reaches and the length of the shortest path it finds for each. Write them in the order that the algorithm would find them. B 2 D 3 C 4 F 5 List the Nodes of the same graph in breadth first order starting from E. (2 points) E,D,C,F,B ) In an adjacency matrix for the same graph, where each cell has either a weight or -1 if there is no edge, how many cells would have -1 in them? Also write a formula for calculating this number for any graph, in terms of number of nodes N and number of edges E. 6 * 6 - 9 = 27 N^2 - E If a binary tree has N nodes, what is the maximal/minimal height the tree may have (you may answer in O notation) Maximal H = N-1 , O(N)  Minimal H = O( log(N) ) If a graph has E edges, what is the maximal/minimal number of nodes it may have? Answer in O notation. Assume the graph is undirected, connected (no unreachable nodes) and not a multigraph. Maximal N = O(E)  Minimal N = O( sqrt(E) ) [E=n^2] A directed weighted graph is represented as an adjacency matrix g, such that g[i][j] is a boolean that is true if and only if there is an edge from node i to node j. A) Write the body of the method: public static int highestDegree(boolean[][] g) That computes the highest number of outgoing edges of any node. int size = g.length; int top = 0; for (int i = 0;itop) top=deg; } return top; If the graph g has N nodes and E edges, how many cells in g contains false? N^2 - E Define a binary search tree (compared to trees in general). Binary tree, each non-leaf node has two children. The element in each node must be greater than or equal to all elements in the left child, and lesser than all elements in the right child If a binary tree has N nodes, what is the maximal/minimal height the tree may have (you may answer in O notation) Maximal H = N-1 , O(N) Minimal H = O( log(N) ) Authorccc ID329518 Card SetBlock 7: Trees and graphs DescriptionBlock 7: Trees and graphs Updated2017-03-14T16:23:56Z Show Answers