a graph is 2-colourable if and only if it is bipartite a graph is bipartite if and only if it has an odd cycle you can check if a graph has an odd cycle using dfs (the ADT methods that you mentioned let you implement dfs) if you know the pseudocode you're done.. (the pseudocode is pretty straightforward) you just need to check if a cycle that you found is odd, which is pretty easy (standard dfs keeps track of parent pointers, so you can reconstruct a cycle)
--~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
