Homework Answers
Answer:
a) V is the set of vertices in G. If we sort them alphabetically in reverse then V={z,y,x,w,v,u}.
b) E is the set of edges.
E = { (z,z),(w,z),(w,y),(v,y),(y,x),(x,v),(u,v),(u,x) }
c) Adjacency List:-
| z | {z} |
| y | {x} |
| x | {v} |
| w | {z,y} |
| v | {y} |
| u | {x,v} |
Add Answer to:
Exercise 3 (35 points) Depth-First Search Consider the following graph G=(V,E): a) Complete V= {z, ....)...
Show how depth-first search works on the graph of Figure 22.6. Assume that the for loop of lines 5–7 of the DFS proced...
Show how depth-first search
works on the graph of Figure 22.6. Assume that the for loop of
lines 5–7 of the DFS procedure considers the vertices in reverse
alphabetical order, and assume that each adjacency list is ordered
alphabetically. Show the discovery and finishing times for each
vertex, and show the classification of each edge.
DIJKSTRA(G,w,s)
1INITIALIZE-SINGLE-SOURCE(G,s)
2 S ??
3 Q ? V[G]
4 while Q =?
5 do u ? EXTRACT-MIN(Q)
6 S ? S?{u}
7 for each...
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/ х у
Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the...
Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the reverse graph G of G. 2. Run DFS on G to obtain a post number for each vertex. Assume that in the adjacency list representation of G, vertices are stored alphabetically, and in the list for each vertex, its adjacent vertices are also sorted alphabetically. In other words, the DFS algorithm needs to examine all vertices alphabetically, and when it traverses the adjacent vertices...
Help !! I need help with Depth-First Search using an undirected graph. Write a program, IN JAVA, ...
Help !! I need help with Depth-First Search using an
undirected graph.
Write a program, IN JAVA, to implement the
depth-first search algorithm using the pseudocode given.
Write a driver program, which reads input file mediumG.txt as an
undirected graph and runs
the depth-first search algorithm to find paths to all the other
vertices considering 0 as the
source. This driver program should display the paths in the
following manner:
0 to ‘v’: list of all the vertices traversed to...
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...
Q6: 20 pts) For the directed graph assigned to you, run the Depth First Search algorithm....
Q6: 20 pts) For the directed graph assigned to you, run the Depth First Search algorithm. (a) Clearly show the order in which the vertices are pushed and popped. (b) Clearly write the list of edges and their classification into one of the four categories as determined using DFS. (c) Determine whether the directed graph assigned to you is a DAG or not? If it is a DAG. write the topological sort of the vertices.
Write the pseudocode of the Depth First Search Algorithm DFS(G) using adjacencymatrix representation of the graph...
Write the pseudocode of the Depth First Search Algorithm DFS(G)
using adjacencymatrix
representation of the graph G. What is the running time of your
pseudocode?
Specification: start from the psedocode discussed in class and
do only the modifications
needed for adjacency-matrix graph representation.
Below is the pseudocode discussed in class:
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...
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....
Show how depth-first search
works on the graph of Figure 22.6. Assume that the for loop of
lines 5–7 of the DFS procedure considers the vertices in reverse
alphabetical order, and assume that each adjacency list is ordered
alphabetically. Show the discovery and finishing times for each
vertex, and show the classification of each edge.
DIJKSTRA(G,w,s)
1INITIALIZE-SINGLE-SOURCE(G,s)
2 S ??
3 Q ? V[G]
4 while Q =?
5 do u ? EXTRACT-MIN(Q)
6 S ? S?{u}
7 for each...
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/ х у
Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the reverse graph G of G. 2. Run DFS on G to obtain a post number for each vertex. Assume that in the adjacency list representation of G, vertices are stored alphabetically, and in the list for each vertex, its adjacent vertices are also sorted alphabetically. In other words, the DFS algorithm needs to examine all vertices alphabetically, and when it traverses the adjacent vertices...
Help !! I need help with Depth-First Search using an
undirected graph.
Write a program, IN JAVA, to implement the
depth-first search algorithm using the pseudocode given.
Write a driver program, which reads input file mediumG.txt as an
undirected graph and runs
the depth-first search algorithm to find paths to all the other
vertices considering 0 as the
source. This driver program should display the paths in the
following manner:
0 to ‘v’: list of all the vertices traversed to...
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...
Q6: 20 pts) For the directed graph assigned to you, run the Depth First Search algorithm. (a) Clearly show the order in which the vertices are pushed and popped. (b) Clearly write the list of edges and their classification into one of the four categories as determined using DFS. (c) Determine whether the directed graph assigned to you is a DAG or not? If it is a DAG. write the topological sort of the vertices.
Write the pseudocode of the Depth First Search Algorithm DFS(G)
using adjacencymatrix
representation of the graph G. What is the running time of your
pseudocode?
Specification: start from the psedocode discussed in class and
do only the modifications
needed for adjacency-matrix graph representation.
Below is the pseudocode discussed in class:
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...
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....
Most questions answered within 3 hours.
-
Compile a list (7 or more) of other commands useful for
navigating or manipulating the UNIX/Linux...
asked 2 minutes ago -
How many grams of PbBr2 will precipitate when excess CrBr3
solution is added to 61.0 mL...
asked 4 minutes ago -
If I was given the address of 134.15.0.0/16 from my ISP and I
wanted to use...
asked 9 minutes ago -
What is the pH of the solution that results of dissolving 1.74g
of sodium hydroxide in...
asked 13 minutes ago -
Given a standardized normal distribution (with μ = 0 and a σ =
1), what is...
asked 50 minutes ago -
Given the following information:
acetic acid
CH3COOH
Ka = 1.8×10-5
triethylamine
(C2H5)3N
Kb = 5.2×10-4
(1)...
asked 37 minutes ago -
Potassium permanganate(KMNO4)is has a solubility of 6.4 g/ 100 g
of water at 20ºC, and 250...
asked 33 minutes ago -
51.
As the marginal propensity to expend rises, the multiplier:
decreases.
is impossible to determine.
increases....
asked 40 minutes ago -
The Baldwin Company currently has the following balances on their
balance sheet:
Total
Liabilities
$69,309
Common...
asked 43 minutes ago -
A quiet town in Kansas has 10 people, all of whom have the same
preferences. There...
asked 48 minutes ago -
Summarize what an organization needs from a leader.
a. Analyze what might happen to an organization...
asked 51 minutes ago -
How would one critically evaluate an organizations marketing
strategies from the viewpoint of its consumers, as...
asked 50 minutes ago