> Write the pseudocode of an algorithm that determines if the vertices of > a > given connected undirected graph can be colored with only two colors > (named 0 and 1) > so that no two adjacent vertices have the same color.
>From the algorithm design manual: (http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE178.HTM#SECTION03157000000000000000) "Testing whether a graph is bipartite is easy. Color the first vertex blue, and then do a depth-first search of the graph. Whenever we discover a new, uncolored vertex, color it opposite that of its parent, since the same color would cause a clash. If we ever find an edge where both vertices have been colored identically, then the graph cannot be bipartite. Otherwise, this coloring will be a 2-coloring, and it is constructed in O(n+m) time." --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
