Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - What's the good of using 3 states for a vertex in DFS?

In the explanation of depth-first search (DFS) in Algorithms in a Nutshell (2nd edition), the author used 3 states for a vertex, say white(not visited), gray(has unvisited neighbors), black(visited).

enter image description here

Two states (white and black) are enough for a traverse. Why add the gray state? What's it used for?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

This is a variation of the DFS algorithm shown in Introduction to Algorithms by Coerman at al.

When you use 3 colors instead of only 2, it gives you more information. Fist, it allows you at each point during the algorithm run, to know which vertices are currently "open" (gray), which are "closed" (black) and which are unexplored yet (white).

In addition, when you use "timestamping" of the colorings (which is a list saying when you color each vertex in the order it occurd) of DFS using 3 colors - you can find out interesting properties about the graph, like backedges. This is used for example to determine if a graph is acyclic or not.

Note that for the sole purpose of discovering a graph - the 3 colors are indeed not mandatory, and indeed exercise 22-3.4 asks you to show that.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...