Homework Answers
The adjacency list for the given tree is :
![OL Nחרר 00 |------- Nחרר -1] - Nחדר [os - -- --- אחרר os - ES]- אחדו 3-E- אחדר ].-- אחרר 9]--- N - - - [ on חרר [s]- אחדד 9-פ](http://img.homeworklib.com/questions/cdc72260-67f9-11ea-a130-2f7211f7b6ff.png?x-oss-process=image/resize,w_560)
The discovery/ finish time is represented as _ / _ and the discovery time of the source node 0 is taken as 0.
Source is given as node 0.
Initially, stack contains 0.
Neighbour of node 0 is node 2.
Push 2.
Stack : 0 2
Neighbour of node 2 is node 3.
Push 3.
Stack : 0 2 3
Neighbour of node 3 is node 7.
Push 7.
Stack : 0 2 3 7
Node 7 has no neighbours.
Pop 7.
Stack : 0 2 3.
Backtrack from node 7 to node 3.
Node 3 has no unvisited neighbours.
Pop 3.
Stack : 0 2 3.
Backtrack from node 3 to node 2.
Neighbour of node 2 is node 5.
Push 5
Stack : 0 2 5
Node 5 has no unvisited neighbours.
Pop 5.
Stack : 0 2
Neighbour of node 2 is node 6.
Push 6
Stack : 0 2 6
Neighbour of node 6 is node 10.
Push 10.
Stack : 0 2 6 10
Neighbour of node 10 is node 11.
Push 11.
Stack : 0 2 6 10 11
Node 11 has no unvisited neighbour.
Pop 11.
Stack : 0 2 6 10
Backtrack from node 11 to node 10.
Node 10 has no unvisited neighbour.
Pop 10.
Stack : 0 2 6
Backtrack from node 10 to node 6.
Node 6 has no unvisited neighbour.
Pop 6.
Stack : 0 2
Backtrack from node 6 to node 2.
Node 2 has no unvisited neighbour.
Pop 2.
Stack : 0
Neighbour of node 0 is node 1.
Push 1.
Stack : 0 1.
Neigbour of node 1 is node 4.
Push 4.
Stack : 0 1 4
Neighbour of node 4 is node 8.
Push 8.
Stack : 0 1 4 8
Neighbour of node 8 is node 9.
Push 9.
Stack : 0 1 4 8 9.
Node 9 has no unvisited neighbour.
Pop 9.
Stack : 0 1 4 8
Backtrack from node 9 to node 8.
Node 8 has no unvisited neighbour.
Pop 8.
Stack : 0 1 4
Node 4 has no unvisited neighbour.
Pop 4.
Stack : 0 1.
Node 1 has no unvisited neighbour.
Pop 1.
Stack : 0
Node 0 has no unvisited neighbour.
Pop 0.
Stack is empty.
Therefore, the DFS tree from the given directed graph is :
The discovery time and finish time of the nodes in the DFS tree is :
Add Answer to:
1 Graph Search Consider the following graph G. 1.1 Draw the DFS tree for G when...
3. (8 points-7+1) Figure 4 shows an undirected graph G. Assume that the adjacency list lists the ...
3. (8 points-7+1) Figure 4 shows an undirected graph G. Assume that the adjacency list lists the edges in alphabetical order. Figure 3: Graph for P3 (a) Apply depth first search (DFS) to graph G, and show the discovery and finish times of each vertex. In the main-loop of DFS, check the vertices in alphabetical the form dsc/fin, where dsc is the discovery time and fin is the finish time. (b) Draw the DFS tree obtained.
3. (8 points-7+1) Figure...
3. Given a directed graph G < V E >, we define its transpose Gr < V.E1 > to be the graph such tha...
3. Given a directed graph G < V E >, we define its transpose Gr < V.E1 > to be the graph such that ET-{ < v, u >:< u, v >EE). In other words, GT has the same number of edges as in G, but the directions of the edges are reversed. Draw the transpose of the following graph: ta Perform DFS on the original graph G, and write down the start and finish times for each vertex in...
Consider the following directed graph for each of the problems: 1. Perform a breadth-first search on...
Consider the following directed graph for each of the
problems:
1. Perform a breadth-first search on the graph assuming that the
vertices and adjacency lists
are listed in alphabetical order. Show the breadth-first search
tree that is generated.
2. Perform a depth-first search on the graph assuming that the
vertices and adjacency lists
are listed in alphabetical order. Classify each edge as tree, back
or cross edge. Label each
vertex with its start and finish time.
3. Remove all the...
Q2. Show the execution trace of DFS on the following directed graph. You must show discovery...
Q2. Show the execution trace of DFS on the following directed graph. You must show discovery time v.d, finish time v.f, and the v.color for each node as the algorithm progresses. Indicate all tree edges, back edges, forward edges, and cross edges when the final DFS forest is constructed. Assume that the edges going out from a vertex are processed in alphabetical order and that each adjacency list is ordered alphabetically.
Problem 2 [10 points] Depth-First Search Write inside each vertex in the following graph the discovery...
Problem 2 [10 points] Depth-First Search Write inside each vertex in the following graph the discovery and finishing times in the format discovery/finish. Assume DFS considers the vertices in alphabetical order (A,B,C,....X,Y,Z), and assume that each adjacency list is ordered alphabetically W 1/ х у
Show the operation of depth-first search (DFS) on the graph of Figure 1 starting from vertex...
Show the operation of depth-first search (DFS) on the graph of Figure 1 starting from vertex q. Always process vertices in alphabetical order. Show the discovery and finish times for each vertex, and the classification of each edge. (b) A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first search (BFS) tree can also be used to classify the edges reachable from the source of the search into the same four categories....
Give the adjacency matrix representation and the adjacency lists representation for the graph G_1. Assume that...
Give the adjacency matrix representation and the adjacency lists representation for the graph G_1. Assume that vertices (e.g., in adjacency lists) are ordered alphabetically. For the following problems, assume that vertices are ordered alphabetically in the adjacency lists (thus you will visit adjacent vertices in alphabetical order). Execute a Breadth-First Search on the graph G_1, starting on vertex a. Specifiy the visit times for each node of the graph. Execute a Depth-First Search on the graph G_1 starting on vertex...
Please help me with 2 (c), thank you!!! Figure 2: 4 10 Figure 3:1 4 Problems 1. Trace BFS on the following graphs. For...
Please help me with 2 (c), thank you!!!
Figure 2: 4 10 Figure 3:1 4 Problems 1. Trace BFS on the following graphs. For each vertex, record its color, parent, and distance fields, draw the resulting BFS tree, and determine the order in which vertices are added to the Queue. Process adjacency lists in ascending numerical order. a. The graph in figure 1, with 1 as the source. b. The directed graph in figure 2 with 1 as source. 2....
Execute DFS on the graph below, starting in node a. Whenever you have a choice which...
Execute DFS on the graph below, starting in node a. Whenever you have a choice which vertex to visit next, choose the next vertex in the adjacency list of the vertex (e.g., when you have reached node e, you must first try to visit node f, then g, and then . Indicate the outcome of the algorithm by labeling the edges of the graph either as T (tree edge) F (forward edge), B (back edge), or C (cross edge). Label...
Draw the DFS search tree with starting vertex E and break ties alphabetically. Assuming unit edge...
Draw the DFS search tree with starting vertex E and break ties alphabetically. Assuming unit edge length (i.e., ignore edge weight), draw the BFS search tree with starting vertex E and break ties alphabetically. Suppose the Dijkstras algorithm is run on the graph with starting vertex E: (i) draw a table showing the intermediate distance values of all vertices at each iteration of the algorithm; (ii) show the final shortest-path tree.
3. (8 points-7+1) Figure 4 shows an undirected graph G. Assume that the adjacency list lists the edges in alphabetical order. Figure 3: Graph for P3 (a) Apply depth first search (DFS) to graph G, and show the discovery and finish times of each vertex. In the main-loop of DFS, check the vertices in alphabetical the form dsc/fin, where dsc is the discovery time and fin is the finish time. (b) Draw the DFS tree obtained.
3. (8 points-7+1) Figure...
3. Given a directed graph G < V E >, we define its transpose Gr < V.E1 > to be the graph such that ET-{ < v, u >:< u, v >EE). In other words, GT has the same number of edges as in G, but the directions of the edges are reversed. Draw the transpose of the following graph: ta Perform DFS on the original graph G, and write down the start and finish times for each vertex in...
Consider the following directed graph for each of the
problems:
1. Perform a breadth-first search on the graph assuming that the
vertices and adjacency lists
are listed in alphabetical order. Show the breadth-first search
tree that is generated.
2. Perform a depth-first search on the graph assuming that the
vertices and adjacency lists
are listed in alphabetical order. Classify each edge as tree, back
or cross edge. Label each
vertex with its start and finish time.
3. Remove all the...
Q2. Show the execution trace of DFS on the following directed graph. You must show discovery time v.d, finish time v.f, and the v.color for each node as the algorithm progresses. Indicate all tree edges, back edges, forward edges, and cross edges when the final DFS forest is constructed. Assume that the edges going out from a vertex are processed in alphabetical order and that each adjacency list is ordered alphabetically.
Problem 2 [10 points] Depth-First Search Write inside each vertex in the following graph the discovery and finishing times in the format discovery/finish. Assume DFS considers the vertices in alphabetical order (A,B,C,....X,Y,Z), and assume that each adjacency list is ordered alphabetically W 1/ х у
Show the operation of depth-first search (DFS) on the graph of Figure 1 starting from vertex q. Always process vertices in alphabetical order. Show the discovery and finish times for each vertex, and the classification of each edge. (b) A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first search (BFS) tree can also be used to classify the edges reachable from the source of the search into the same four categories....
Give the adjacency matrix representation and the adjacency lists representation for the graph G_1. Assume that vertices (e.g., in adjacency lists) are ordered alphabetically. For the following problems, assume that vertices are ordered alphabetically in the adjacency lists (thus you will visit adjacent vertices in alphabetical order). Execute a Breadth-First Search on the graph G_1, starting on vertex a. Specifiy the visit times for each node of the graph. Execute a Depth-First Search on the graph G_1 starting on vertex...
Please help me with 2 (c), thank you!!!
Figure 2: 4 10 Figure 3:1 4 Problems 1. Trace BFS on the following graphs. For each vertex, record its color, parent, and distance fields, draw the resulting BFS tree, and determine the order in which vertices are added to the Queue. Process adjacency lists in ascending numerical order. a. The graph in figure 1, with 1 as the source. b. The directed graph in figure 2 with 1 as source. 2....
Execute DFS on the graph below, starting in node a. Whenever you have a choice which vertex to visit next, choose the next vertex in the adjacency list of the vertex (e.g., when you have reached node e, you must first try to visit node f, then g, and then . Indicate the outcome of the algorithm by labeling the edges of the graph either as T (tree edge) F (forward edge), B (back edge), or C (cross edge). Label...
Draw the DFS search tree with starting vertex E and break ties alphabetically. Assuming unit edge length (i.e., ignore edge weight), draw the BFS search tree with starting vertex E and break ties alphabetically. Suppose the Dijkstras algorithm is run on the graph with starting vertex E: (i) draw a table showing the intermediate distance values of all vertices at each iteration of the algorithm; (ii) show the final shortest-path tree.
Most questions answered within 3 hours.
-
Assume Kw = 1.01 ✕ 10−14
For pure water, we can calculate [H3O+ ] = [OH...
asked 17 minutes ago -
Suppose that on a temperature scale X, water boils at 203.0°X
and freezes at -105.7°X. What...
asked 1 hour ago -
BaS crystallizes in a cubic unit cell with S2- ions on each
corner and each face....
asked 1 hour ago -
A. 0≤P(Oi)≤10≤P(Oi)≤1 for each i
B. P(Oi)≤0P(Oi)≤0
C. P(Oi)=1+P(OCi)P(Oi)=1+P(OiC)
D. P(Oi)≥1P(Oi)≥1
If an experiment consists of...
asked 3 hours ago -
A battery has an emf of 9.20V and an internal resistance of 1.20
ohm. a)What resistance...
asked 3 hours ago -
The area of an elastic circular loop decreases at a constant
rate, dA/dt = −6.60×10−3 m2/s...
asked 4 hours ago -
The denaturation of proteins can be described by the
equilibrium
F⇌U
where F and U represent...
asked 5 hours ago -
Please answer what the maximum and minimum force is, and the
angle on the ion is...
asked 5 hours ago -
implement a program that reads a number of rows and a symbol.
The program will draw...
asked 5 hours ago -
Assume that when adults with smartphones are randomly selected,
45% use them in meetings or classes....
asked 5 hours ago -
Determine the number of formula units of
Na2SO4 and moles of oxygen contained in 8.11
moles...
asked 6 hours ago -
Explain in steps on the following code
What would be the output when executed
using System;...
asked 6 hours ago