Homework Answers
Here, data structure Queue is used for BFS to traverse the graph. Initially Queue is empty.
Enqueue(0) to queue. Contents of Queue = [0]
(Dequeue) Visit 0. Enqueue adjacent vertices of 0 into queue. Contents of Queue = [1, 9]
(Dequeue) Visit 1. Enqueue adjacent vertices of 1 into queue. Contents of Queue = [9, 6, 8]
(Dequeue) Visit 9. Enqueue adjacent vertices of 9 into queue. Contents of Queue = [6, 8, 2, 4]
(Dequeue) Visit 6. Enqueue adjacent vertices of 6 into queue. Contents of Queue = [8, 2, 4, 3, 7]
(Dequeue) Visit 8. Enqueue adjacent vertices of 8 into queue. Contents of Queue = [ 2, 4, 3, 7, 5 ]
(Dequeue) Visit 2. Enqueue adjacent vertices of 2 into queue.(Here, 2 doesnt have any adjacent vertices which has to be enqueued) Contents of Queue = [4, 3, 7, 5 ].
(Dequeue) Visit 4. Enqueue adjacent vertices of 4 into queue. Contents of Queue = [ 3, 7, 5 ]
(Dequeue) Visit 3. Enqueue adjacent vertices of 3 into queue. Contents of Queue = [ 7, 5 ]
(Dequeue) Visit 7. Enqueue adjacent vertices of 7 into queue. Contents of Queue = [ 5 ]
(Dequeue) Visit 5. Enqueue adjacent vertices of 5 into queue. Contents of Queue = [ ]
Order in which vertices are visited is: 0, 1, 9, 6, 8, 2, 4, 3, 7, 5
Add Answer to:
In Python 3 please
Apply Breadth First Search (BFS) to traverse the following graph. Start your...
# Problem 4 problem4_breadth_first_traversal = [0,] problem4_depth_first_traversal = [0,] def bfs(g,start): start.set...
# Problem 4
problem4_breadth_first_traversal = [0,]
problem4_depth_first_traversal = [0,]
def bfs(g,start):
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0):
currentVert = vertQueue.dequeue()
for nbr in currentVert.getConnections():
if (nbr.getColor() == 'white'):
nbr.setColor('gray')
nbr.setDistance(currentVert.getDistance() + 1)
nbr.setPred(currentVert)
vertQueue.enqueue(nbr)
currentVert.setColor('black')
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def dfsvisit(self,startVertex):
startVertex.setColor('gray')
self.time += 1
startVertex.setDiscovery(self.time)
for nextVertex in startVertex.getConnections():
if nextVertex.getColor() == 'white':
nextVertex.setPred(startVertex)...
(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void...
(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void breadthFirstSearch (vertex w) for all vertices u num (u) 0 null edges i=1; num (w) i++ enqueue (w) while queue is not empty dequeue ( V= for all vertices u adjacent to v if num(u) is 0 num (u) = i++; enqueue (u) attach edge (vu) to edges; output edges; Now consider the following graph. Give the breadth-first traversal of the graph, starting from...
help with alogrthms Consider the following graph for problems 6, 7, & 8. (b f C...
help with alogrthms
Consider the following graph for problems 6, 7, & 8. (b f C d a (5 points) Starting at vertex a and resolving ties by the vertex alphabetical order, traverse the graph by depth-first search 7. and construct the corresponding depth-first search tree (5 points) Traverse the graph by breadth-first search and construct the corresponding breadth-first search tree. Start the 8. traversal at vertex a and resolve ties by the vertex alphabetical order.
Consider the following graph...
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
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source ver...
Solve (a) and (b) using BFS and DFS diagram
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS
BFS Given an undirected graph...
LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents th...
JAVA
LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents the graph. Your code should contain a function called addEdgelint i, int j). Use this function to add the appropriate edges in your matrix. Write code to implement Depth-First-Search (DFS) and Breadth-First-Search (BFS) of your graph. Let 0 be the source Node . Traverse the graph using DFS, print the Nodes as they are visited. . Traverse the...
from collections import defaultdict # This class represents a directed graph using # adjacency list...
from collections import defaultdict # This class represents a directed graph using # adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue...
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source ver...
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS
BFS Given an undirected graph below (a) Show the shortest distance to each vertex...
Programming Traversal Methods in C++ (depth first & breadth first) Need solution ASAP any help is...
Programming Traversal Methods in C++ (depth first & breadth first) Need solution ASAP any help is much appreciated. read a set of data representing a directed, unweighted graph build an in-memory graph structure using the data display the graph using depth-first traversal display the graph using breadth-first traversal Input data - The data consists of records like this: 16 3 15 4 -1 This represents a vertex 16 with neighbors 3, 15, and 4. The -1 is the indicator that...
In the breadth first traversal procedure BFS, each vertex v has an attribute v.color. Modify BFS...
In the breadth first traversal procedure BFS, each vertex
v has an attribute v.color. Modify BFS
so that instead of x.color, each vertex
x has a Boolean attribute called x.mark,
whose value is either TRUE or FALSE. The attribute
x.mark must be FALSE if x has never been
visited. It must be TRUE if x has been visited, but will
not be visited again.
Thank you!!!
BFS(G, s) 1 for each vertex u e G.V-(s 11, color WHITE 4 5...
# Problem 4
problem4_breadth_first_traversal = [0,]
problem4_depth_first_traversal = [0,]
def bfs(g,start):
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0):
currentVert = vertQueue.dequeue()
for nbr in currentVert.getConnections():
if (nbr.getColor() == 'white'):
nbr.setColor('gray')
nbr.setDistance(currentVert.getDistance() + 1)
nbr.setPred(currentVert)
vertQueue.enqueue(nbr)
currentVert.setColor('black')
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def dfsvisit(self,startVertex):
startVertex.setColor('gray')
self.time += 1
startVertex.setDiscovery(self.time)
for nextVertex in startVertex.getConnections():
if nextVertex.getColor() == 'white':
nextVertex.setPred(startVertex)...
(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void breadthFirstSearch (vertex w) for all vertices u num (u) 0 null edges i=1; num (w) i++ enqueue (w) while queue is not empty dequeue ( V= for all vertices u adjacent to v if num(u) is 0 num (u) = i++; enqueue (u) attach edge (vu) to edges; output edges; Now consider the following graph. Give the breadth-first traversal of the graph, starting from...
help with alogrthms
Consider the following graph for problems 6, 7, & 8. (b f C d a (5 points) Starting at vertex a and resolving ties by the vertex alphabetical order, traverse the graph by depth-first search 7. and construct the corresponding depth-first search tree (5 points) Traverse the graph by breadth-first search and construct the corresponding breadth-first search tree. Start the 8. traversal at vertex a and resolve ties by the vertex alphabetical order.
Consider the following graph...
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
Solve (a) and (b) using BFS and DFS diagram
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS
BFS Given an undirected graph...
JAVA
LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents the graph. Your code should contain a function called addEdgelint i, int j). Use this function to add the appropriate edges in your matrix. Write code to implement Depth-First-Search (DFS) and Breadth-First-Search (BFS) of your graph. Let 0 be the source Node . Traverse the graph using DFS, print the Nodes as they are visited. . Traverse the...
BFS Given an undirected graph below (a) Show the shortest distance to each vertex from source vertex H and predecessor tree on the graph that result from running breadth-finst search (BFS).Choose adjacen vertices in al phabetical order b) Show the start and finsh time for each vertex, starting from source vertex H, that result from running depth-first search (DFS)Choose aljacent vertices in alphabet- ical order DFS
BFS Given an undirected graph below (a) Show the shortest distance to each vertex...
In the breadth first traversal procedure BFS, each vertex
v has an attribute v.color. Modify BFS
so that instead of x.color, each vertex
x has a Boolean attribute called x.mark,
whose value is either TRUE or FALSE. The attribute
x.mark must be FALSE if x has never been
visited. It must be TRUE if x has been visited, but will
not be visited again.
Thank you!!!
BFS(G, s) 1 for each vertex u e G.V-(s 11, color WHITE 4 5...
Most questions answered within 3 hours.
-
20% of all customers subscribe to phone service.
70% of all customers subscribe to internet service....
asked 11 minutes ago -
Write a program to solve the Josephus problem, with the following
modification:
Sample Input:
./a.out n...
asked 2 hours ago -
At the start of a CD it is spinning at a rate of 525 rpm
(revolutions...
asked 3 hours ago -
4. Without doing any calculations, predict whether the observed
∆T would increase, decrease or remain the...
asked 4 hours ago -
Based on the range, which of the following sets of scores has
the greatest variability? 3,...
asked 5 hours ago -
Ripples in a pond travel at a velocity of 3 m/s with one peak
passing a...
asked 5 hours ago -
A man stands on the roof of a building of height 13.0 mm and
throws a...
asked 5 hours ago -
The extent to which assets are financed by borrowed funds and
other liabilities is indicated by:...
asked 6 hours ago -
Explain in detail
Germany is the fifth largest economy
explain what goods and services Germany specializes...
asked 7 hours ago -
The density of platinum is 21.45 g/mL. If a cube of platinum
with a mass of...
asked 7 hours ago -
Accounts Receivable
Sales
A/R Posting
Extended Sales Invoice
Packing Slip
Compare invoice to packing slip 2...
asked 7 hours ago -
Michaella, age 23, is a full-time law student and is claimed by
her parents as a...
asked 7 hours ago