CODEWITHSUNDEEP
algorithmdepth-first-search
user3666471
user3666471

Reputation: 945

Vertex Coloring with DFS

I'm trying to color vertices of a graph using minimum number of colors using DFS. I'm stuck on a particular place where the graph cannot be completely accessed from a single start point. Once I assign a color to a vertex, will I ever change it? Is there backtracking involved?

If there is backtracking, how do I use DFS to color a graph that looks like this:

A  B
 \ |
  \|
C--D

Upvotes: 3

Views: 3491

Answers (1)

sray
sray

Reputation: 584

For a graph, you can check whether a node is colored (already visited) to track which nodes you have already visited by DFS.

When the DFS from a node cannot move ahead, you have to start DFS from other unvisited nodes till each and every node has been visited/colored.

Also, you terminate each DFS path once you encounter a visited/colored node.

This is a greedy coloring algorithm. However, it may not be optimal in choosing the minimum number of colors. See more at http://en.wikipedia.org/wiki/Graph_coloring#Algorithms

Upvotes: 2

Related Questions