Please, answer the three questions. Thanks 1 Question Given the following figure

Question

Please, answer the three questions. Thanks

1 Question Given the following figure for Depth-First Search (DFS) and Breadth-First Search (BFS: Not yet answered Points out of 5.00 A) unexplored vertex F Flag question A 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 Unexplored vertices Visited vertices Back edges Cross edges Discovery edges

Explanation / Answer

Q1) a) Visited vertex, as the name suggests are the nodes that are already visited.

b) Unexplored vertex, as the name suggests are the nodes that have not yet been visited.

c) Discovery edges are edges from node of a traversal tree to its descendent. Hence, they aid in discovering new vertices.

d) Back edge is from a node to its ancestor. You have to use the backedge in DFS when adjacency list of a node is exhausted.

e)Although the classification of edges in BFS is not used widely but cross-edge would lead to same vertex in this case. (Cross edges actually are not present in real, they are implemented with the help of a queue).

Q2. DFS(G,v){
label starting vertex v as visited.

for all edges e in vertex v incidentEdges (edges emanating from vertex v) list:

if the edge e which is under consideration in current iteration of loop is unvisited:

then assign opposite vertex of v on edge e to w

if w is unexplored,

then label e as a discovery edge (as it discovers a new vertex in search)

and then recursively call DFS(G,w) to let DFS go as deep as possible in the graph.

else if w is already explored

label the edge e as back edge (DFS already went as deep as it coult and went back to the ancestor)

}

Q3. Let's look at the main loops of BFS.

for all vertices v on Level i

for all edges e emanating from vertex v's incident edges

if e is unexplored then,

assign opposite vertex of v on edge e as w

if vertex w (vertex on next level) is unexplored then,

label w as a discovery edge leading to next element in search

So, insert w into the Level i+1 queue

else if w is already explored (vertex on next level)

label e as a cross edge [see your graph figure, the edge from c to e]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---