The Gateway to Computer Science Excellence

+1 vote

Assume WHITE vertices that are yet to be discovered, BLACK vertices are finished vertices and GRAY vertices are frontier betweeen WHITE and BLACK in Depth First Search.

Now, What are the various edge types like TREE-EDGE and BACK-EDGE possible between any pair of vertices during a Depth First Search in an Undirected graph.

Confused about the edge type between WHITE and GRAY type vertices.

[ CLRS (3rd Edition) : 22-3:1; Page # 610 ]

Now, What are the various edge types like TREE-EDGE and BACK-EDGE possible between any pair of vertices during a Depth First Search in an Undirected graph.

Confused about the edge type between WHITE and GRAY type vertices.

[ CLRS (3rd Edition) : 22-3:1; Page # 610 ]

0 votes

An edge (u,v) is said to be TREE-EDGE if either u is ancestor of v or v is ancestor of u.

An edge (u,v) is said to be BACK-EGE if the edge between u and v discovered during the traversal from v to u.

If we can have a TREE-EDGE between any pair of types of vertices in an undirected graph, we can also have BACK-EDGE in that same pair of types of vertices.

WHITE | GRAY | BLACK | |
---|---|---|---|

WHITE | Tree, Back | Tree, Back | None |

GRAY | Tree, Back | Tree, Back | Tree, Back |

BLACK | None | Tree, Back | Tree, Back |

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,479 answers

195,421 comments

100,549 users