{"id":34690,"date":"2024-11-01T09:30:55","date_gmt":"2024-11-01T09:30:55","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34690"},"modified":"2024-11-01T11:26:57","modified_gmt":"2024-11-01T11:26:57","slug":"swift-coding-test-course-representation-of-graphs","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34690\/","title":{"rendered":"Swift Coding Test Course, Representation of Graphs"},"content":{"rendered":"<\/p>\n
\n\n<\/header>\n\n
1. Introduction<\/h2>\n
Understanding algorithms and data structures is crucial in the field of software development. One of the problems that frequently appears in coding tests is related to graphs. A graph is a data structure composed of nodes (vertices) and edges, allowing data to be represented in various forms. In this course, we will deepen our understanding through algorithm problems related to graph representation.<\/p>\n<\/section>\n\n
2. Graph Representation<\/h2>\n
There are mainly two ways to represent a graph.<\/p>\n
\n
Adjacency Matrix:<\/strong> A two-dimensional array is used to represent the presence or absence of edges for all vertices in the graph. This method is useful when the number of vertices is small. The size of the array is O(V^2).<\/li>\n
Adjacency List:<\/strong> This method stores the connected vertices as a list for each vertex. It is memory efficient and suitable for graphs with fewer edges. The time complexity of this method is O(V + E).<\/li>\n<\/ul>\n<\/section>\n\n
3. Problem Description<\/h2>\n
We will apply the graph representation methods through the following problem.<\/p>\n
Problem: Friend Network<\/h3>\n
You are managing a network of N friends. Friend relationships are bidirectional, meaning if two friends are directly connected, they are friends with each other. Represent the friend relationship as a graph and write a program to check if two specific friends belong to the same friend group. A friend group includes all friends that are indirectly connected.<\/p>\n
Input Format:<\/p>\n
\nN (number of friends)\nM (number of friend relationships)\nFor M lines, two friends A and B (1 \u2264 A, B \u2264 N) are given.\n <\/pre>\n
Output Format:<\/p>\n
\nPrint \"YES\" if A and B are in the same friend group, otherwise print \"NO\".\n <\/pre>\n<\/section>\n\n
4. Problem Solving Process<\/h2>\n
4.1. Graph Creation<\/h3>\n
First, we need to create a graph based on the given friend relationships. We will implement this using an adjacency list. Here is a simple Swift code for graph creation.<\/p>\n
\nimport Foundation\n\n\/\/ Adjacency list for graph representation\nvar graph: [Int: [Int]] = [:]\n\n\/\/ Function to add friend relations\nfunc addFriendRelation(friendA: Int, friendB: Int) {\n graph[friendA, default: []].append(friendB)\n graph[friendB, default: []].append(friendA)\n}\n\n\/\/ Function to create graph\nfunc createGraph(N: Int, relations: [(Int, Int)]) {\n for (A, B) in relations {\n addFriendRelation(friendA: A, friendB: B)\n }\n}\n <\/code><\/pre>\n
The above code creates a dictionary where each friend is a key and the value is the list of connected friends.<\/p>\n
4.2. Finding Friend Groups<\/h3>\n
Now we can use one of the graph traversal algorithms to check if two friends belong to the same group. We can use Depth-First Search (DFS) or Breadth-First Search (BFS), and we will choose DFS here. DFS allows us to explore all related friends.<\/p>\n
\nfunc dfs(start: Int, visited: inout Set) {\n visited.insert(start)\n for friend in graph[start, default: []] {\n if !visited.contains(friend) {\n dfs(start: friend, visited: &visited)\n }\n }\n}\n\n\/\/ Function to check if two friends are in the same group\nfunc areInSameGroup(friendA: Int, friendB: Int) -> Bool {\n var visited = Set()\n dfs(start: friendA, visited: &visited)\n return visited.contains(friendB)\n}\n <\/code><\/pre>\n
4.3. Entire Process<\/h3>\n
Now let’s integrate the entire process to solve the problem. Here is the code to read input, create the graph, and check the relationship of two friends.<\/p>\n
\nlet N = Int(readLine()!)! \/\/ Number of friends\nlet M = Int(readLine()!)! \/\/ Number of friend relationships\n\nvar relations = [(Int, Int)]()\n\nfor _ in 0..<\/pre>\n
The above code implements the logic to represent and verify friend relationships through the overall flow.<\/p>\n<\/section>\n\n
5. Conclusion<\/h2>\n
In this course, we explored how to represent graphs and how to use basic DFS algorithms to solve problems. Graphs are useful data structures that can be applied to various problems, and it is essential to become familiar with them through sufficient practice. Since such problems often appear in coding tests, I encourage you to improve your skills by solving problems multiple times.<\/p>\n<\/section>\n