Hello! Today, we will take a detailed look at how to represent graphs, which frequently appear in coding tests, using Kotlin. Graphs are an important data structure in various fields and have essential fundamental functions for solving a range of problems. In this article, we will explain how to represent a graph and how to use that representation to solve problems.
What is a Graph?
A graph is a data structure composed of nodes (vertices) and edges. A node represents an object, and an edge represents the relationship between nodes. Graphs can be classified into directed and undirected graphs based on directionality, and into weighted and unweighted graphs based on the presence of weights.
Ways to Represent a Graph
Graphs can be represented in various ways, with the two most common methods being the Adjacency Matrix and the Adjacency List.
1. Adjacency Matrix
An adjacency matrix is a method of representing a graph using a 2D array of size N x N. N is the number of nodes in the graph, and each element of the matrix indicates whether nodes are connected. For example, if node A is connected to node B, then matrix[A][B] will be 1.
fun createAdjacencyMatrix(vertices: Int, edges: List>): Array> {
val matrix = Array(vertices) { Array(vertices) { 0 } }
for (edge in edges) {
val (from, to) = edge
matrix[from][to] = 1
matrix[to][from] = 1 // For undirected graphs
}
return matrix
}
2. Adjacency List
An adjacency list is a method that uses a list to store connected nodes for each node. This method is memory efficient and advantageous for graphs with fewer nodes or edges.
fun createAdjacencyList(vertices: Int, edges: List>): List> {
val list = MutableList(vertices) { mutableListOf() }
for (edge in edges) {
val (from, to) = edge
list[from].add(to)
list[to].add(from) // For undirected graphs
}
return list
}
Problem: Friend Relationship Network
The following is a problem that represents a graph of friendships.
Problem: Given N people and their friendships, write a program to check whether a friendship exists between two people. Friend relationships are represented as undirected graphs. The numbers of the two people are given sequentially from 0 to N-1.
Problem-Solving Process
1. Understand the Input Format
First, we need to understand the given data. The input is as follows:
- The first line contains the number of people N.
- The second line contains the number of friendships M.
- Subsequently, M lines contain two integers a and b representing each friendship.
2. Choose a Data Structure
To store the given friendships, we will use an adjacency list. This allows for easy exploration of friendships.
3. Create the Graph
fun main() {
val reader = BufferedReader(InputStreamReader(System.`in`))
val n = reader.readLine().toInt()
val m = reader.readLine().toInt()
val edges = mutableListOf>()
for (i in 0 until m) {
val (a, b) = reader.readLine().split(" ").map { it.toInt() }
edges.add(Pair(a, b))
}
val adjacencyList = createAdjacencyList(n, edges)
}
4. Check Friendship
The method to check whether two specific people are friends is to use DFS (Depth First Search) or BFS (Breadth First Search) to verify connectivity. Here, we will implement it using DFS.
fun isConnected(adjList: List>, start: Int, target: Int, visited: BooleanArray): Boolean {
if (start == target) return true
visited[start] = true
for (neighbor in adjList[start]) {
if (!visited[neighbor]) {
if (isConnected(adjList, neighbor, target, visited)) {
return true
}
}
}
return false
}
fun main() {
// Continuing from the previous code
val query = reader.readLine().split(" ").map { it.toInt() }
val (x, y) = query
val visited = BooleanArray(n) { false }
val result = isConnected(adjacencyList, x, y, visited)
println(if (result) "YES" else "NO")
}
Conclusion
In this lesson, we learned about the basic concepts and methods of representing graphs, and how to solve the friend relationship network problem using these representations. Graphs are essential for solving various problems, and these graph representation and traversal techniques are very useful in algorithm tests.
Having implemented examples using Kotlin, I encourage you to practice by solving various graph problems yourself. Next time, we will discuss the differences between BFS and DFS, as well as various problem-solving strategies utilizing them. I hope this aids you in your learning journey!