Write better code: Day 8 - Graph Coloring

Recent articles from Progress Updates:

• The only daily stand up meeting template you need
• The only two questions you need to ask in your daily standup scrum
• The only daily standup meeting agenda you will ever need
• How to Create a Weekly Report With Templates and Examples
• How to automate your end of week status reports

Day 8: Question 1

Given an undirected graph with maximum degree DD, find a graph coloring using at most D+1 colors.

-

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.
This problem is from InterviewCake.

Comments

[Arjun Rajkumar]

Logic:

• Each node in the graph has maximum D neighbours.
• Given than there are maximum D+1 colours, we can assume that for each node there is atleast one color that is not used.
• So, go thru each node and get the colors of all its neighbours.
• Check to see which color is not included in this neighbouring color group, and assign the color to it.

def colour_graoh(colors, graph)
  graph.nodes.each do |node|

    all_neighbouring_colors = []

    node.neighbours.each do |neighbour|
      all_neighbouring_colors << neighbour.color if !all_neighbouring_colors.include?(neighbour.color)
    end

    colors.each do |color|
      node.color = color if !all_neighbouring_colors.include?(color)
      break
    end
end