Swift Coding Test Course, Representation of Graphs

1. Introduction

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.

2. Graph Representation

There are mainly two ways to represent a graph.

• Adjacency Matrix: 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).
• Adjacency List: 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).

3. Problem Description

We will apply the graph representation methods through the following problem.

Problem: Friend Network

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.

Input Format:

N (number of friends)
M (number of friend relationships)
For M lines, two friends A and B (1 ≤ A, B ≤ N) are given.
            

Output Format:

Print "YES" if A and B are in the same friend group, otherwise print "NO".
            

4. Problem Solving Process

4.1. Graph Creation

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.

import Foundation

// Adjacency list for graph representation
var graph: [Int: [Int]] = [:]

// Function to add friend relations
func addFriendRelation(friendA: Int, friendB: Int) {
    graph[friendA, default: []].append(friendB)
    graph[friendB, default: []].append(friendA)
}

// Function to create graph
func createGraph(N: Int, relations: [(Int, Int)]) {
    for (A, B) in relations {
        addFriendRelation(friendA: A, friendB: B)
    }
}
            

The above code creates a dictionary where each friend is a key and the value is the list of connected friends.

4.2. Finding Friend Groups

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.

func dfs(start: Int, visited: inout Set<int>) {
    visited.insert(start)
    for friend in graph[start, default: []] {
        if !visited.contains(friend) {
            dfs(start: friend, visited: &amp;visited)
        }
    }
}

// Function to check if two friends are in the same group
func areInSameGroup(friendA: Int, friendB: Int) -&gt; Bool {
    var visited = Set<int>()
    dfs(start: friendA, visited: &amp;visited)
    return visited.contains(friendB)
}
            </int></int>

4.3. Entire Process

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.

let N = Int(readLine()!)! // Number of friends
let M = Int(readLine()!)! // Number of friend relationships

var relations = [(Int, Int)]()

for _ in 0..<m {="" let="" line="readLine()!.split(separator:" "="" ").map="" int($0)!="" }="" relations.append((line[0],="" line[1]))="" creategraph(n:="" n,="" relations:="" relations)="" checkline="readLine()!.split(separator:" if="" areinsamegroup(frienda:="" checkline[0],="" friendb:="" checkline[1])="" print("yes")="" else="" print("no")="" <="" code=""></m>