Take Me Back To Kindergarten
Given a graph with
vertices and two colors, we want to determine if we can color each vertex such that no two neighboring vertices have the same color. Which way of traversing the graph makes sense for solving this problem?
Relevant graph algorithms :
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
"Makes sense" might sounds ambiguous as both approach is valid. But let's say if you are solving this problem on paper, and you want to be systematic , you should apply Breadth-First Search . In other words, you will first select an arbitrary node and color it in 1. Then, you expand to its neighbor and color all of them with 2. If throughout the progress you found that your neighbor has been colored and is the same as the current node, then the colored graph cannot be formed.
If you perform Depth-First Search , you will find yourself confused or missed out some same-colored neighbor as you don't check all your neighbors but keep exploring until the end. Breadth-First Search check for validity while coloring.