Free AI web copilot to create summaries, insights and extended knowledge, download it at here

5164

Abstract

Int]], colors: [Int]) -> Bool { guard vertex < graph.count, vertex < colors.count else { return false } // 6. let neighbors = graph[vertex] // 7. for i in 0..<neighbors.count { if neighbors[i] == 1, colors[i] == color { return false } } return true }</pre></div><h2 id="c41a">Explanations:</h2>1. Check if k is not 0 or the graph is not empty.<div id="3862"><pre>guard k > 0 else { return nil } guard !graph.isEmpty else { return [] }</pre></div>2. Let’s create the array which will hold the colors and start the recursion.<div id="9a6f"><pre>var colors = Array(repeating: 0, count: graph.count) let result = coloringGraph(k: k, graph: graph, colors: &colors, vertex: 0)</pre></div>3. If the result is true, there is a way to color the graph with only k colors; let’s return the color array.<div id="55a9"><pre>return result ? colors : nil</pre></div>4. As we are recursing, we need a base case; here, if the vertex index is greater or equal to the number of vertices, it means we have treated all vertices, then it means we can color the graph with k colors.<div id="c3db"><pre>guard vertex < graph.count else { return true }</pre></div>5. It’s here where the magic happens; we are backtracking all colors for all nodes. For all nodes, we will try all colors; if we find a color that “is safe to use” (not used by any neighbors), we save the color for the current node and recurse with the subsequent nodes; if no colors match (neighbors have used all colors) we return false as we cannot use k colors for this graph.<div id="821f"><pre>for color in 1…k { if isSafe(vertex: vertex, color: color, graph: graph, colors: colors) { colors[vertex] = color return coloringGraph(k: k, graph: graph, colors: &colors, vertex: vertex + 1) } }</pre></div>6. Let’s find the neighbors of the given node.<div id="7f83"><pre>let neighbors = graph[vertex]</pre></div>7. if no neighbor is using the current color, this color is safe to use for this number.<div id="c843"><pre>for i in 0..<neighbors.count { if neighbors[i] == 1, colors[i] == color { return false } } return true</pre></div><h2 id="b863">Complexity:</h2>- Time Complexity: As in the worst case will be trying all color combinations; the time complexity is O(k^n), where k is the number of colors and n is the number of nodes within the graph,- Space Complexity: As we keep the color array by the size o

Options

f the number of nodes/vertices O(n), but also the call stack for the backtracking will be up to n calls O(n), the space complexity is O(n) where n is the number of nodes within the graph.<h2 id="041d">Test-cases:</h2><div id="c02c"><pre>public func testColoringGraph() { var graph = [ [1, 1, 1, 0, 1], [1, 1, 1, 0, 1], [1, 1, 1, 0, 1], [1, 1, 1, 0, 1], [1, 1, 1, 0, 1] ]

<span class="hljs-built_in">assert</span>(coloringGraph(k: <span class="hljs-number">3</span>, graph: graph) <span class="hljs-operator">==</span> <span class="hljs-literal">nil</span>, <span class="hljs-string">"coloringGraph 1 not equal"</span>)
<span class="hljs-built_in">assert</span>(coloringGraph(k: <span class="hljs-number">4</span>, graph: graph) <span class="hljs-operator">==</span> [<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">4</span>], <span class="hljs-string">"coloringGraph 2 not equal"</span>)

graph <span class="hljs-operator">=</span> [
    [<span class="hljs-number">0</span>, <span class="hljs-number">1</span>,  <span class="hljs-number">1</span>, <span class="hljs-number">1</span>, <span class="hljs-number">1</span>],
    [<span class="hljs-number">1</span>, <span class="hljs-number">0</span>,  <span class="hljs-number">0</span>, <span class="hljs-number">1</span>, <span class="hljs-number">0</span>],
    [<span class="hljs-number">1</span>, <span class="hljs-number">1</span>,  <span class="hljs-number">1</span>, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>],
    [<span class="hljs-number">1</span>, <span class="hljs-number">0</span>,  <span class="hljs-number">0</span>, <span class="hljs-number">1</span>, <span class="hljs-number">0</span>],
    [<span class="hljs-number">1</span>, <span class="hljs-number">0</span>,  <span class="hljs-number">0</span>, <span class="hljs-number">1</span>, <span class="hljs-number">0</span>]
]

<span class="hljs-built_in">assert</span>(coloringGraph(k: <span class="hljs-number">2</span>, graph: graph) <span class="hljs-operator">==</span> <span class="hljs-literal">nil</span>, <span class="hljs-string">"coloringGraph 3 not equal"</span>)
<span class="hljs-built_in">assert</span>(coloringGraph(k: <span class="hljs-number">3</span>, graph: graph) <span class="hljs-operator">==</span> [<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>], <span class="hljs-string">"coloringGraph 4 not equal"</span>)
<span class="hljs-built_in">assert</span>(coloringGraph(k: <span class="hljs-number">4</span>, graph: graph) <span class="hljs-operator">==</span> [<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>], <span class="hljs-string">"coloringGraph 5 not equal"</span>)

}</pre></div><h2 id="b2ad">Follow-up:</h2>Give the minimum K colors to color a given graph.<a href="https://readmedium.com/algorithms-questions-429c4d84a98f"><< More Interview Questions</a> | <a href="https://readmedium.com/learn-data-structures-and-algorithms-with-swift-5-6-d9f36a4027dd">Data Structures and Algorythms >></a><div id="c879" class="link-block"> <a href="https://medium.com/@jbstevenard/membership"> <div> <div> <h2>Join Medium with my referral link — jb stevenard</h2> <div><h3>Read every story from jb stevenard (and thousands of other writers on Medium). Your membership fee directly supports jb…</h3></div> <div>medium.com</div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*TEb_Qg9xmrjfkxhH)"></div> </div> </div> </a> </div></article></body>

8. Coloring Graph With K Colors

Question: Find if an undirected graph can be colored with a maximum of K colors, two adjacent vertices should not have the same color.

For example, given

[
  [1, 1, 1, 0, 1],
  [1, 1, 1, 0, 1],
  [1, 1, 1, 0, 1],
  [1, 1, 1, 0, 1],
  [1, 1, 1, 0, 1]
]

and k: 3, you should return nil,

and k: 4, you should return [1, 2, 3, 4, 4].

Hints:

- You need a collection to track what colors are set for all nodes,

- Set the color for one node, then do it recursively for the next node,

- This is a backtracking problem.

Solution:

func coloringGraph(k: Int, graph: [[Int]]) -> [Int]? {
    // 1.
    guard k > 0 else { return nil }
    guard !graph.isEmpty else { return [] }

    // 2.
    var colors = Array(repeating: 0, count: graph.count)
    let result = coloringGraph(k: k, graph: graph, colors: &colors, vertex: 0)

    // 3.
    return result ? colors : nil
}

func coloringGraph(k: Int, graph: [[Int]], 
                   colors: inout [Int], vertex: Int) -> Bool {
    // 4.
    guard vertex < graph.count else { return true }
    for color in 1...k {
        // 5.
        if isSafe(vertex: vertex, 
                  color: color, 
                  graph: graph, 
                  colors: colors) {
            colors[vertex] = color
            return coloringGraph(k: k, 
                                 graph: graph, 
                                 colors: &colors, 
                                 vertex: vertex + 1)
        }
    }
    return false
}

func isSafe(vertex: Int, color: Int, graph: [[Int]], colors: [Int]) -> Bool {
    guard vertex < graph.count, vertex < colors.count else { return false }
    // 6.
    let neighbors = graph[vertex]
    // 7.
    for i in 0..<neighbors.count {
        if neighbors[i] == 1, colors[i] == color {
            return false
        }
    }
    return true
}

Explanations:

1. Check if k is not 0 or the graph is not empty.

guard k > 0 else { return nil }
guard !graph.isEmpty else { return [] }

2. Let’s create the array which will hold the colors and start the recursion.

var colors = Array(repeating: 0, count: graph.count)
let result = coloringGraph(k: k, graph: graph, colors: &colors, vertex: 0)

3. If the result is true, there is a way to color the graph with only k colors; let’s return the color array.

return result ? colors : nil

4. As we are recursing, we need a base case; here, if the vertex index is greater or equal to the number of vertices, it means we have treated all vertices, then it means we can color the graph with k colors.

guard vertex < graph.count else { return true }

5. It’s here where the magic happens; we are backtracking all colors for all nodes. For all nodes, we will try all colors; if we find a color that “is safe to use” (not used by any neighbors), we save the color for the current node and recurse with the subsequent nodes; if no colors match (neighbors have used all colors) we return false as we cannot use k colors for this graph.

for color in 1…k {
  if isSafe(vertex: vertex, color: color, graph: graph, colors: colors) {
    colors[vertex] = color
    return coloringGraph(k: k, graph: graph, colors: &colors, vertex: vertex + 1)
  }
}

6. Let’s find the neighbors of the given node.

let neighbors = graph[vertex]

7. if no neighbor is using the current color, this color is safe to use for this number.

for i in 0..<neighbors.count {
  if neighbors[i] == 1, colors[i] == color {
    return false
  }
}
return true

Complexity:

- Time Complexity: As in the worst case will be trying all color combinations; the time complexity is O(k^n), where k is the number of colors and n is the number of nodes within the graph,

- Space Complexity: As we keep the color array by the size of the number of nodes/vertices O(n), but also the call stack for the backtracking will be up to n calls O(n), the space complexity is O(n) where n is the number of nodes within the graph.

Test-cases:

public func testColoringGraph() {
    var graph = [
        [1, 1, 1, 0, 1],
        [1, 1, 1, 0, 1],
        [1, 1, 1, 0, 1],
        [1, 1, 1, 0, 1],
        [1, 1, 1, 0, 1]
    ]

    assert(coloringGraph(k: 3, graph: graph) == nil, "coloringGraph 1 not equal")
    assert(coloringGraph(k: 4, graph: graph) == [1, 2, 3, 4, 4], "coloringGraph 2 not equal")

    graph = [
        [0, 1,  1, 1, 1],
        [1, 0,  0, 1, 0],
        [1, 1,  1, 0, 1],
        [1, 0,  0, 1, 0],
        [1, 0,  0, 1, 0]
    ]

    assert(coloringGraph(k: 2, graph: graph) == nil, "coloringGraph 3 not equal")
    assert(coloringGraph(k: 3, graph: graph) == [1, 2, 3, 2, 3], "coloringGraph 4 not equal")
    assert(coloringGraph(k: 4, graph: graph) == [1, 2, 3, 2, 3], "coloringGraph 5 not equal")
}

Follow-up:

Give the minimum K colors to color a given graph.

<< More Interview Questions | Data Structures and Algorythms >>

Join Medium with my referral link — jb stevenard

Read every story from jb stevenard (and thousands of other writers on Medium). Your membership fee directly supports jb…

medium.com