{"id":34962,"date":"2024-11-01T09:34:03","date_gmt":"2024-11-01T09:34:03","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34962"},"modified":"2024-11-01T11:45:34","modified_gmt":"2024-11-01T11:45:34","slug":"kotlin-coding-test-course-representation-of-graphs","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34962\/","title":{"rendered":"kotlin coding test course, representation of graphs"},"content":{"rendered":"

<\/p>\n

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.<\/p>\n

What is a Graph?<\/h2>\n

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.<\/p>\n

Ways to Represent a Graph<\/h3>\n

Graphs can be represented in various ways, with the two most common methods being the Adjacency Matrix and the Adjacency List.<\/p>\n

1. Adjacency Matrix<\/h4>\n

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.<\/p>\n

\n    fun createAdjacencyMatrix(vertices: Int, edges: List>): Array> {\n        val matrix = Array(vertices) { Array(vertices) { 0 } }\n        for (edge in edges) {\n            val (from, to) = edge\n            matrix[from][to] = 1\n            matrix[to][from] = 1  \/\/ For undirected graphs\n        }\n        return matrix\n    }\n<\/pre>\n
2. Adjacency List<\/h4>\n
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.<\/p>\n
\n    fun createAdjacencyList(vertices: Int, edges: List>): List> {\n        val list = MutableList(vertices) { mutableListOf() }\n        for (edge in edges) {\n            val (from, to) = edge\n            list[from].add(to)\n            list[to].add(from)  \/\/ For undirected graphs\n        }\n        return list\n    }\n<\/pre>\n
Problem: Friend Relationship Network<\/h2>\n
The following is a problem that represents a graph of friendships.<\/p>\n
\n
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.<\/p>\n<\/blockquote>\n
Problem-Solving Process<\/h2>\n
1. Understand the Input Format<\/h3>\n
First, we need to understand the given data. The input is as follows:<\/p>\n