DEV Community

Arjun Rajkumar
Arjun Rajkumar

Posted on • Edited on

Write better code: Day 8 - Graph Coloring

#challenge

Recent articles from Progress Updates:

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.

Top comments (1)

Collapse
 
arjunrajkumar profile image
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

Read next

leamsigc profile image

How to add comment from BlueSky to static/vue/nuxt project

Ismael Garcia -

pvgomes profile image

staging and QA will not save your systems

Paulo Victor Leite Lima Gomes -

lp profile image

Centralized Root Access in AWS: A Game-Changer for LandingZone security

Lucian Patian -

saranya_velmurugan profile image

fetch all data from multiple table using postgresql in nodejs

Saranya Velmurugan -