In breadth-first and depth-first search, an undiscovered node is marked discover

Question

In breadth-first and depth-first search, an undiscovered node is marked discovered when it is first encountered, and marked processed when it has been completely searched. At any given moment, several nodes might be simultaneously in the discovered state.
(a) Describe a graph on n vertices and a particular starting vertex v such that ?(n) nodes are simultaneously in the discovered state during a breadth-first search starting from v.
(b) Describe a graph on n vertices and a particular starting vertex v such that ?(n) nodes are simultaneously in the discovered state during a depth-first search starting from v.
(c) Describe a graph on n vertices and a particular starting vertex v such that at some point ?(n) nodes remain undiscovered, while ?(n) nodes have been processed during adepth-first search starting from v. (Note, there may also be discovered nodes.)

Explanation / Answer

Depth first search (DFS) is useful for Find a path from one vertex to another Whether or not graph is connected Computing a spanning tree of a connected graph. DFS uses the backtracking technique.

Algorithm Depth First Search

Algorithm starts at a specific vertex S in G, which becomes current vertex. Then algorithm traverse graph by any edge (u, v) incident to the current vertex u. If the edge (u, v) leads to an already visited vertex v, then we backtrack to current vertex u. If, on other hand, edge (u, v) leads to an unvisited vertex v, then we go to v and v becomes our current vertex. We proceed in this manner until we reach to "deadend". At this point we start back tracking. The process terminates when backtracking leads back to the start vertex.

Edges leads to new vertex are called discovery or tree edges and edges lead to already visited are called back edges.

DEPTH FIRST SEARCH (G, v)

Input:    A graph G and a vertex v.
Output: Edges labeled as discovery and back edges in the connected component.

For all edges e incident on v do
    If edge e is unexplored then
        w ? opposite (v, e) // return the end point of e distant to v
        If vertex w is unexplained then
            - mark e as a discovery edge
            - Recursively call DSF (G, w)
        else
            - mark e as a back edge

Solid Edge     = discovery or tree edge
Dashed Edge = back edge.

Each vertex has two time stamps: the first time stamp records when vertex is first discovered and second time stamp records when the search finishes examining adjacency list of vertex.

DFS algorithm used to solve following problems.

Testing whether graph is connected.

Computing a spanning forest of graph

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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