Kotlin coding test course, determining if a graph is bipartite

Problem Description

This is a problem to determine whether the given graph is a bipartite graph. A bipartite graph is a graph that can be divided into two sets of vertices such that there are no edges between vertices of the same set.
In other words, if two vertices u and v are connected, u and v must belong to different sets.

Input

• Integer n (1 ≤ n ≤ 1000): number of vertices
• Integer m (1 ≤ m ≤ 5000): number of edges
• m pairs (u, v): edge information between vertex u and vertex v

Output

Print YES if the graph is a bipartite graph, otherwise print NO.

Problem Solving Process

To determine if a graph is bipartite, we can use DFS (Depth First Search) or BFS (Breadth First Search) algorithms. We proceed by coloring the vertices of the graph with two colors, and if adjacent vertices are colored the same, it is not a bipartite graph.

Step 1: Graph Representation

The graph is represented using an adjacency list. We use ArrayList to store the connectivity between vertices.

Step 2: Graph Traversal

While traversing the graph using DFS or BFS, we determine the color of each vertex and check its adjacent vertices to determine if it is a bipartite graph.

Step 3: Implementation

Below is the implementation in Kotlin.

fun isBipartiteGraph(n: Int, edges: List>): String {
    val graph = Array(n + 1) { mutableListOf() }
    for (edge in edges) {
        graph[edge.first].add(edge.second)
        graph[edge.second].add(edge.first)
    }

    val color = IntArray(n + 1) { -1 } // -1: unvisited, 0: set0, 1: set1

    fun bfs(start: Int): Boolean {
        val queue: Queue = LinkedList()
        queue.add(start)
        color[start] = 0 // Coloring the starting vertex with set0

        while (queue.isNotEmpty()) {
            val node = queue.poll()
            for (neighbor in graph[node]) {
                if (color[neighbor] == -1) { // Unvisited vertex
                    color[neighbor] = 1 - color[node] // Color with the opposite color of the current vertex
                    queue.add(neighbor)
                } else if (color[neighbor] == color[node]) {
                    return false // If adjacent vertices have the same color
                }
            }
        }
        return true
    }

    for (i in 1..n) {
        if (color[i] == -1) { // If unvisited vertex, start BFS
            if (!bfs(i)) {
                return "NO"
            }
        }
    }
    return "YES"
}

// Example usage
fun main() {
    val n = 5 // Number of vertices
    val edges = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5)) // Edge information
    println(isBipartiteGraph(n, edges)) // Output: YES
}

Step 4: Results and Validation

By running the above code, you can determine whether the graph is a bipartite graph. Test various graphs to validate that it produces the correct results.

Conclusion

Through this course, we understood the concept of bipartite graphs and how to determine them, and learned how to effectively solve this problem using Kotlin programming.