Bipartite.go description: Implementation of the Bipartite graph coloring algorithm details: A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V. The Bipartite graph coloring algorithm is used to determine i
()
| 7 | // space complexity: O(V) where V is the number of vertices in the graph |
| 8 | |
| 9 | func (g *Graph) TryBipartiteColoring() map[int]Color { |
| 10 | // 0 is uncolored, 1/2 are colors |
| 11 | colors := make(map[int]Color) |
| 12 | visited := make(map[int]bool) |
| 13 | |
| 14 | for i := range g.edges { |
| 15 | colors[i] = 0 |
| 16 | visited[i] = false |
| 17 | } |
| 18 | |
| 19 | var colorNode func(int) |
| 20 | colorNode = func(s int) { |
| 21 | visited[s] = true |
| 22 | coloring := []Color{0, 2, 1} |
| 23 | |
| 24 | for n := range g.edges[s] { |
| 25 | if colors[n] == 0 { |
| 26 | colors[n] = coloring[colors[s]] |
| 27 | } |
| 28 | if !visited[n] { |
| 29 | colorNode(n) |
| 30 | } |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | for i := range g.edges { |
| 35 | if colors[i] == 0 { |
| 36 | colors[i] = 1 |
| 37 | colorNode(i) |
| 38 | } |
| 39 | } |
| 40 | |
| 41 | return colors |
| 42 | } |
| 43 | |
| 44 | // basically tries to color the graph in two colors if each edge |
| 45 | // connects 2 differently colored nodes the graph can be considered bipartite |