Given the graph G from Question 2, using the Graph Breadth-First Search algorithm with a Queue. please do the following: Assume that the start node is 4 (e.g. node = 4). Demonstrate a step-by-step, manual desk-check execution of the BFS algorithm, showing the values of all variables and arrays (e.g. visited, inqueue, Q) for each step in each cycle of each loop, as demonstrated in class. " Algorithm: Graph breadth-first search BFS (G, node) visited Input: G=(V.E), a graphy node, the starting vertex in G 6 Output: visited, an array of size [V] such that visited[i] is TRUE if we have visited node i, FALSE otherwise 10-CreateQueue () 2 visited 3 inqueue - CreateArray(V) 4 for 0 to VI do CreateArray (VI) visited[i] FALSE inqueue[] FALSE 7 Enqueue (Q, node) ainqueue[node] + TRUE 9 while not IsQueueEmpty(Q) do 10 cDequeue (Q) inqueue[c]FALSE visited[e]-TRUE foreach u in AdjacencyList (G, c) do if not visited[v] and not inqueue[v] then 11 12 13 14 15 16 17 return visited Enqueue (Q.) inqueue[v] - TRUE
Given the graph G from Question 2, using the Graph Breadth-First Search algorithm with a Queue. please do the following: Assume that the start node is 4 (e.g. node = 4). Demonstrate a step-by-step, manual desk-check execution of the BFS algorithm, showing the values of all variables and arrays (e.g. visited, inqueue, Q) for each step in each cycle of each loop, as demonstrated in class. " Algorithm: Graph breadth-first search BFS (G, node) visited Input: G=(V.E), a graphy node, the starting vertex in G 6 Output: visited, an array of size [V] such that visited[i] is TRUE if we have visited node i, FALSE otherwise 10-CreateQueue () 2 visited 3 inqueue - CreateArray(V) 4 for 0 to VI do CreateArray (VI) visited[i] FALSE inqueue[] FALSE 7 Enqueue (Q, node) ainqueue[node] + TRUE 9 while not IsQueueEmpty(Q) do 10 cDequeue (Q) inqueue[c]FALSE visited[e]-TRUE foreach u in AdjacencyList (G, c) do if not visited[v] and not inqueue[v] then 11 12 13 14 15 16 17 return visited Enqueue (Q.) inqueue[v] - TRUE
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
![Given the graph G from Question 2, using the Graph Breadth-First Search algorithm with a Queue.
please do the following:
Assume that the start node is 4 (e.g.node = 4),
Demonstrate a step-by-step, manual desk-check execution of the BFS algorithm, showing the values of
all variables and arrays (e.g. visited, inqueue, Q) for each step in each cycle of each loop, as
demonstrated in class.
Algorithm: Graph breadth-first search
BFS (G, node) → visited
Input: G=(V.E), a graphy
node, the starting vertex in G
Output: visited, an array of size [V] such that visited[i] is TRUE if we
have visited node i, FALSE otherwise.
1 Q-CreateQueue ()
visited
CreateArray (VI)
3 inqueue - CreateArray (IV)
4 for i0 to VI do
5
visited[i]+FALSE
inqueue[i] + FALSE
7 Enqueue (Q, node)
8 inqueue[node] TRUE
9 while not IsQueueEmpty(Q) do
10
c← Dequeue (Q)
11
12
13
14
inqueue[c] FALSE
visited[c] - TRUE
foreach in AdjacencyList (G, c) do
if not visited[v] and not inqueue[v] then
Enqueue (Q, v)
inqueue[v] + TRUE
X
return visited](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fc0851de8-3741-4c3e-9091-0420cbe43fc8%2F4cab5f1a-272b-4c6d-b434-42770ab00e2e%2Fbwlhwxi_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Given the graph G from Question 2, using the Graph Breadth-First Search algorithm with a Queue.
please do the following:
Assume that the start node is 4 (e.g.node = 4),
Demonstrate a step-by-step, manual desk-check execution of the BFS algorithm, showing the values of
all variables and arrays (e.g. visited, inqueue, Q) for each step in each cycle of each loop, as
demonstrated in class.
Algorithm: Graph breadth-first search
BFS (G, node) → visited
Input: G=(V.E), a graphy
node, the starting vertex in G
Output: visited, an array of size [V] such that visited[i] is TRUE if we
have visited node i, FALSE otherwise.
1 Q-CreateQueue ()
visited
CreateArray (VI)
3 inqueue - CreateArray (IV)
4 for i0 to VI do
5
visited[i]+FALSE
inqueue[i] + FALSE
7 Enqueue (Q, node)
8 inqueue[node] TRUE
9 while not IsQueueEmpty(Q) do
10
c← Dequeue (Q)
11
12
13
14
inqueue[c] FALSE
visited[c] - TRUE
foreach in AdjacencyList (G, c) do
if not visited[v] and not inqueue[v] then
Enqueue (Q, v)
inqueue[v] + TRUE
X
return visited
Transcribed Image Text:1
5
X
Graph G
Expert Solution
Breadth First Search
Traversal algorithm involves visiting the vertices of the graph exactly once in some specific order. Breadth first search involves visiting the source node, visiting all the child nodes of the source node, visiting all child nodes of each of each of the node visited earlier and so forth. It involves visiting the nodes of the graph level by level.
Step by step
Solved in 4 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education