ColorUsingBFS will return the Color of each vertex and the total number of different colors used, using BFS
()
| 10 | // ColorUsingBFS will return the Color of each vertex and the |
| 11 | // total number of different colors used, using BFS |
| 12 | func (g *Graph) ColorUsingBFS() (map[int]Color, int) { |
| 13 | // Initially all vertices will have same color |
| 14 | vertexColors := make(map[int]Color, g.vertices) |
| 15 | for i := 0; i < g.vertices; i++ { |
| 16 | vertexColors[i] = 1 |
| 17 | } |
| 18 | |
| 19 | visited := make(map[int]struct{}) |
| 20 | // Run BFS from each non-visited vertex |
| 21 | for i := 0; i < g.vertices; i++ { |
| 22 | if _, ok := visited[i]; ok { |
| 23 | continue |
| 24 | } |
| 25 | visited[i] = struct{}{} |
| 26 | |
| 27 | queue := list.New() |
| 28 | queue.PushBack(i) |
| 29 | |
| 30 | for queue.Len() != 0 { |
| 31 | // front vertex in the queue |
| 32 | frontNode := queue.Front() |
| 33 | front := frontNode.Value.(int) |
| 34 | queue.Remove(frontNode) |
| 35 | |
| 36 | // Now, check all neighbours of front vertex, if they have same |
| 37 | // color as that of front, change their color |
| 38 | for nb := range g.edges[front] { |
| 39 | if vertexColors[nb] == vertexColors[front] { |
| 40 | vertexColors[nb]++ |
| 41 | } |
| 42 | // if the neighbour is not already visited, add it to the queue |
| 43 | if _, ok := visited[nb]; !ok { |
| 44 | visited[nb] = struct{}{} |
| 45 | queue.PushBack(nb) |
| 46 | } |
| 47 | } |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | colorsUsed := 0 |
| 52 | for _, cr := range vertexColors { |
| 53 | if colorsUsed < int(cr) { |
| 54 | colorsUsed = int(cr) |
| 55 | } |
| 56 | } |
| 57 | return vertexColors, colorsUsed |
| 58 | } |