Pseudo-code:
To implement the 2-coloring problem, we'll use the breadth-first search strategy to visit and process each node. A queue is required for the implementing breadth-first search. For this problem, every node requires three attributes. One attribute is the color attribute, which is assigned to the node. As this is a two coloring problem, we'll make color a boolean variable called red, which would be true if the color of the node is red, otherwise false. The three attributes for each node are:
assigned: Initially it is set to false and set to true once a color is assigned to the node.red: True if the color of the node is red, otherwise false.added: Initially false. Set to true once the node is added to the queue.
The pseudo-code for the solution is:
Routine: twoColoringProblem Input: A graph Output: True if 2 coloring is possible, false otherwise.
- Initialize the attributes assigned,red and added of each node to false.
- Add the first node to the queue
- noClash = true
- while (queue is not empty and noClash) a. Remove a node n from the queue b. get all adjacent nodes of n which have been assigned a color if all have the same color then assign the opposite color to n set the assign attribute of n to true else noClash = false c. get all adjacent nodes of n which have not been assigned a color and have not been added to the queue add all these nodes to queue and set their added attribute to true
- return noClash