| | |
Draw the graph described by the adjacency list given below for a graph of 7 vertices and 10 edges.
0: 6 5 4 1: 2 6 2: 6 1 4 3: 6 4: 6 0 2 5: 0 6 6: 0 4 2 5 1 3
Given the adjacency list below for a graph of 7 vertices and 10 edges, suppose a recursive method named dfs(v) is written to execute a depth-first traversal of graph starting from vertex $v$. Show the calls to this method (in the order called) that result from an initial call of dfs(0) relative to this graph. Also, draw the graph shading the edges explored as part of the depth-first traversal just done.
0: 5 6 4 2 1: 6 5 4 3 2: 3 0 3: 5 2 1 4: 0 1 5: 0 3 1 6: 1 0
Calls made to dfs(v) in the order they are called: dfs(0) dfs(5) dfs(3) dfs(2) dfs(1) dfs(6) dfs(4) After drawing the graph, shade the following edges: 0-5 5-3 3-2 3-1 1-6 1-4
Given the adjacency list below for a graph of 7 vertices and 10 edges, show the state of a queue used to perform an iterative-based breadth-first traversal of this graph starting at vertex $0$ after each dequeue occurs. Then, draw the graph shading the edges explored as part of the depth-first traversal just done.
0: 1 4 1: 5 0 3 6 2: 6 5 3: 4 1 5 4: 3 6 0 5: 1 2 3 6: 4 2 1
State of the queue (head is on the left side): 0 1 4 4 5 3 6 5 3 6 3 6 2 6 2 2 After drawing the graph, shade the following edges: 0-1 0-4 1-5 1-3 1-6 5-2