Drag and drop the appropriate text to complete the Breadth-First search (BFS) al

Question

Drag and drop the appropriate text to complete the Breadth-First search (BFS) algorithm below. Algorithm BFS(s): initialize collection L0 to contain vertex s 1 leftarrow 0 while Li is not empty do create collection L_i+1 to initially be empty for all vertices v in L_i do for all edges e in v. do if edges e is unexplored then w leftarrow e if vertex w is unexplored then label e as a insert w into L_i+1 else label e as a Drag and drop the appropriate text to complete the Depth-First search (DFS) algorithm below. Algorithm DFS(G, v): Input: A graph G and a vertex v of G Output: A labeling of the edges in the connected component of v as discovery edges and back edges label v as visited for all edges e in v do if edges e is unvisited then w leftarrow e if vertex w is unexplored then label e as a recursively call else label e as a Given the following figure for Depth-First Search (DFS) and Breadth-First Search (BFS): unexplored vertex visited vertex unexplored edge discovery edge back edge cross edge are nodes that have been visited. are nodes that have not been visited. are used to discover new vertices during a DFS or BFS traversal. lead to already visited vertices during a DFS traversal lead o already visited vertices during a BFS traversal.

Explanation / Answer

Answers :

For BFS :

Blank 1: incidentEdges()
Blank 2: opposite(v)
Blank 3: discovered edge
Blank 4: cross edge

For DFS :

Blank 1: incidentEdges()
Blank 2: opposite(v)
Blank 3: discovered edge
Blank 4: DFS(G,W)
Blank 5: back edge

For Graphs:

Blank 1: visited vertices
Blank 2: unexplored vertices
Blank 3: discovered edges
Blank 4: back edge
Blank 5: cross edge

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.