III. Given the following graph: M a) Give the depth-first traversal of the graph, starting from...

Transcribed Image Text:

III. Given the following graph: M a) Give the depth-first traversal of the graph, starting from vertex K. (in case you have the choice between multiple vertices to visit, always select the vertex that has smaller lexicographic order first, i.e. alphabetical order) Use the table to list the nodes in the order they were visited. DFS Order: K b) Give the breadth-first traversal of the graph, starting from vertex K. (in case you have the choice between multiple vertices to visit, always select the vertex that has smaller lexicographic order first, i.e. alphabetical order) Use the table below to list the nodes in the order they were visited. BFS Order: K c) Use Topological sorting on the graph to create a linear ordering of vertices. At any point during the algorithm, if you have the choice between multiple nodes to process next, select/use the one that has the smallest lexicographic order (ie when adding multiple nodes at one time to the queue, add them in alphabetical order). Fill the result (from left to right) in the table below: III. Given the following graph: M a) Give the depth-first traversal of the graph, starting from vertex K. (in case you have the choice between multiple vertices to visit, always select the vertex that has smaller lexicographic order first, i.e. alphabetical order) Use the table to list the nodes in the order they were visited. DFS Order: K b) Give the breadth-first traversal of the graph, starting from vertex K. (in case you have the choice between multiple vertices to visit, always select the vertex that has smaller lexicographic order first, i.e. alphabetical order) Use the table below to list the nodes in the order they were visited. BFS Order: K c) Use Topological sorting on the graph to create a linear ordering of vertices. At any point during the algorithm, if you have the choice between multiple nodes to process next, select/use the one that has the smallest lexicographic order (ie when adding multiple nodes at one time to the queue, add them in alphabetical order). Fill the result (from left to right) in the table below:

Answer rating: 100% (QA)

A DFS of the graph Unvisited Vertices ABCDEFGHIJKLMN K ACEFGHILMN KH ACEFGILMN KHC AEFGILMN KHCA EFG... View the full answer