Write better code: Day 8 - Graph Coloring

twitter logo github logo Updated on ・1 min read

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.

twitter logo DISCUSS (1)
markdown guide
 

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
Classic DEV Post from Jan 17

25 years of coding, and I'm just beginning

I've come to a conclusion that I have nothing to show for my 25 years of coding. I am ready to begin and I have a plan.

Arjun Rajkumar profile image
I’m a software developer primarily building web apps using Ruby on Rails.
Join DEV

πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»