Based on the following adjacency list representation of a graph (where there are no weights assigned...
Based on the following adjacency list representation of a graph (where there are no weights assigned to the edges), in which order are the elements of this graph accessed during a BFS traversal starting at node A and DFS traversal starting at node E?
A: B, C, D
B: A, C, D
C: A, B, D
D: A, B, C, F
E: F, G, H
F: D, E, G
G: E, F, H
H: E, G
When doing the traversal, follow the nodes in alphabetical order. That will be the only correct answer
Homework Answers
BFS traversal starting at node A
Starting from node A traverse all the adjacent nodes , add all the adjacent nodes
A
A B C D
All the adjacent nodes of B are already traversed
All the adjacent nodes of C are already traversed
Adjacent node of D which is not traversed is F, so add F
A B C D F
add adjacent nodes of F
A B C D F E G
add adjacent node of E
A B C D F E G H
all nodes are traversed.
So BFS traversal : A, B, C, D, F, E, G, H
DFS traversal starting at node E
Starting from node E, add only first adjacent node in alphabetical order. If all adjacent nodes are already traversed, backtrack.
E
E F (alphabetical order)
E F D
E F D A
E F D A B
E F D A B C
E F D A B C G ( backtrack)
E F D A B C G H
DFS traversal : E F D A B C G H
Graphs
Do ask if any doubt. Please upvote.
Add Answer to:
Based on the following adjacency list representation of a graph
(where there are no weights assigned...
10 20 60 32 Provide the Adjacency Matrix and Adjacency Table representations of the graph G....
10 20 60 32 Provide the Adjacency Matrix and Adjacency Table representations of the graph G. Perform a BFS for the graph G starting with vertex A, with any additional "starts" of BFS (in the main loop) proceeding in alphabetical order. Perform a DFS for the graph G starting with vertex A, with any additional "starts of DFS (in the main loop) proceeding in alphabetical order.
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...
The following is an adjacency matrix of a directed graph. Start from vertex D, write down...
The following is an adjacency matrix of a directed graph. Start from vertex D, write down the order of node visited in Breadth-First- Search (BFS) traversal. (Enter the nodes in order in the following format: [A B C D E F G]) Adjacenc y Matrix ABCDEFG A 1111 000 BO00 0101 C0111010 DO 0 1 0 0 1 1 E 0 1 0 1 000 F 100 1 100 G0000100
Question 3 (4 marks) For the directed graph below, list the order in which the nine...
Question 3 (4 marks) For the directed graph below, list the order in which the nine nodes are visited during a depth-first (DFS) traversal, as well as the order in which they are visited during a breadth first (BFS) traversal. As always, assume that any ties are resolved by taking nodes in alphabetical order. Write the answers in the boxes given g DFS sequence BFS sequence
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...
/* Graph read from file, and represnted as adjacency list. To implement DFS and BFS on...
/* Graph read from file, and represnted as adjacency list.
To implement DFS and BFS on the graph
*/
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
// Each vertex has an integer id.
typedef vector<vector<pair<int,int>>> adjlist; //
Pair: (head vertex, edge weight)
adjlist makeGraph(ifstream& ifs);
void printGraph(const adjlist& alist);
vector<int> BFS(const adjlist& alist, int source); //
Return vertices in BFS order
vector<int> DFS(const adjlist& alist, int source); //...
Exercise 2 Given the following graph: a. Write the formal description of the graph, G=(V,E) b....
Exercise 2 Given the following graph: a. Write the formal description of the graph, G=(V,E) b. Show the Adjacency Matrix representation C. Show the Adjacency List representation d. Calculate step by step the shortest paths from a e. Show the DFS tree/forest from a f. Show the BFS tree/forest from a g MST using Prim h. MST using Kruskal
1. a. Using C++, represent the following graph using adjacency matrix, and implement DFS by using...
1. a. Using C++, represent the following graph using adjacency matrix, and implement DFS by using stack (define it using class) to traverse the graph. b. Similarly, implement BFS (define queue using class) to traverse the graph c.When node 6 is printed, what numbers are in the stack (for DFS) and queue (for BFS) respectively? Draw pictures to show them.
1. a. Using C++, represent the following graph using adjacency matrix, and implement DFS by using stack (define it using...
Which of the following is the size of an adjacency list graph representation? V refers to...
Which of the following is the size of an adjacency list graph representation? V refers to the number of vertices, E the number of edges. a. O(V+E) b. O( VE) Oc O(V * E) d. O(V * 2E)
10 20 60 32 Provide the Adjacency Matrix and Adjacency Table representations of the graph G. Perform a BFS for the graph G starting with vertex A, with any additional "starts" of BFS (in the main loop) proceeding in alphabetical order. Perform a DFS for the graph G starting with vertex A, with any additional "starts of DFS (in the main loop) proceeding in alphabetical order.
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...
The following is an adjacency matrix of a directed graph. Start from vertex D, write down the order of node visited in Breadth-First- Search (BFS) traversal. (Enter the nodes in order in the following format: [A B C D E F G]) Adjacenc y Matrix ABCDEFG A 1111 000 BO00 0101 C0111010 DO 0 1 0 0 1 1 E 0 1 0 1 000 F 100 1 100 G0000100
Question 3 (4 marks) For the directed graph below, list the order in which the nine nodes are visited during a depth-first (DFS) traversal, as well as the order in which they are visited during a breadth first (BFS) traversal. As always, assume that any ties are resolved by taking nodes in alphabetical order. Write the answers in the boxes given g DFS sequence BFS sequence
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...
/* Graph read from file, and represnted as adjacency list.
To implement DFS and BFS on the graph
*/
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
// Each vertex has an integer id.
typedef vector<vector<pair<int,int>>> adjlist; //
Pair: (head vertex, edge weight)
adjlist makeGraph(ifstream& ifs);
void printGraph(const adjlist& alist);
vector<int> BFS(const adjlist& alist, int source); //
Return vertices in BFS order
vector<int> DFS(const adjlist& alist, int source); //...
Exercise 2 Given the following graph: a. Write the formal description of the graph, G=(V,E) b. Show the Adjacency Matrix representation C. Show the Adjacency List representation d. Calculate step by step the shortest paths from a e. Show the DFS tree/forest from a f. Show the BFS tree/forest from a g MST using Prim h. MST using Kruskal
1. a. Using C++, represent the following graph using adjacency matrix, and implement DFS by using stack (define it using class) to traverse the graph. b. Similarly, implement BFS (define queue using class) to traverse the graph c.When node 6 is printed, what numbers are in the stack (for DFS) and queue (for BFS) respectively? Draw pictures to show them.
1. a. Using C++, represent the following graph using adjacency matrix, and implement DFS by using stack (define it using...
Which of the following is the size of an adjacency list graph representation? V refers to the number of vertices, E the number of edges. a. O(V+E) b. O( VE) Oc O(V * E) d. O(V * 2E)
Most questions answered within 3 hours.
-
What is happening to the electron in the tube to make it deflect
more when Vd...
asked 16 minutes ago -
You start with 23.00g of aluminum and 55.00g of NH4ClO4. What is
the limiting reagent? 10Al(s)...
asked 22 minutes ago -
Find the errors in following program.
//This program uses a switch statement to assign a
//...
asked 23 minutes ago -
The mass structure of a spiral galaxy may be determined by
measurement of its___________ ________________
asked 33 minutes ago -
How do you define corrupt power? Lord Acton, a British historian
of the late 19th century,...
asked 30 minutes ago -
1. If demand deceases and supply remains constant, what happens
to the market equilibrium?
A. Quantity...
asked 37 minutes ago -
A ball of mass 81 kg is dropped from a height of 22 m. What is...
asked 37 minutes ago -
There are 3 golden retrievers, 2 dachshunds, and 4 chocolate
labs in a kennel. Two dogs...
asked 53 minutes ago -
When a fixture of real property is physically detached from the
real property, it is known...
asked 51 minutes ago -
Imagine you are driving around a horizontal circular track (such
as a roundabout at an intersection...
asked 1 hour ago -
Draw the structures that correspond to the following names.
Correct any names that are not in...
asked 1 hour ago -
Do elephants and cows present an interesting dichotomy when
viewed from the perspective of property rights?
asked 1 hour ago