`

Directed Graph Search The directed graph in the diagram will be used to answer the three questions in this section. Note that for the first two questions, on Breadth-First Search and Depth- First Search, you must ignore the edge weights. For the third question, on Lowest- Cost-First search, you must use the edge weights. Also, don't let the geometry of the graph deceive you. You may not always go from a node high in the graph down to one lower in the graph. Question 3 (1 point) The Directed Graph is a DAG (Directed Acyclic Graph). (PS: If it is, then it can be topologically sorted.) 01) True O2) False Question 4 (2 points) What is the order in which the nodes of the directed graph are discovered in a depth-first search starting from node A? When you have the choice of two or more nodes according to the DFS algorithm, break ties by choosing the node whose label comes first in the alphabet. O ABCDEFGHIJKLM O ABCEFGIJLMDKH O ABDHIEJCEKLMG O ABEIDHJCFLKMG O ACBDFEHKJIMLG O ACBFEJMLIGKDH Question 5 (2 points) What is the order in which the nodes of the directed graph are discovered in a Breadth-first search starting from node A? When you have the choice of two or more nodes according to the BFS algorithm, break ties by choosing the node whose label comes first in the alphabet. O ABCDEFGHIJKLM O ABCEFGIJLMDKH OABDHIEJCEKLMG O ABEIDHJCFLKMG OACBDFEHKJIMLG O ACBFEJMLIGKDH Question 6 (2 points) What is the order in which the nodes of the directed graph are discovered in a Lowest-cost-first search starting from node A? When you have the choice of two or more nodes according to the LCFS algorithm, break ties by choosing the node whose label comes first in the alphabet. O ABCDEFGHIJKLM O ABCEFGIJLMDKH O ABDHIEJCEKLMG O ABEIDHJCFLKMG O ACBDFEHKJIMLG O ACBFEJMLIGKDH Topological Sort Question 7 (4 points) Consider the following graph. Below the graph are 8 possible node orderings. Which of these node orderings form a topological sort of the graph? Select all that apply. (Note: There are also other possible topological sort orderings that are not listed here.) 1) BACDEF 2) BACEDF 3) ABCDFE 4) ABCDEF 5) ACBDEF 06) ABCEDF 7) BDACEF 8) FEDCBA