Swift Coding Test Course, DFS and BFS Programs

DFS (Depth-First Search) and BFS (Breadth-First Search), which frequently appear in coding tests, are fundamental methodologies for graph and tree traversal. In this course, we will implement these two algorithms in Swift and solve the problems using them.

1. Overview of DFS and BFS

DFS (Depth-First Search) explores one path to the end before exploring the next one. It uses a stack and can also be called recursively.

BFS (Breadth-First Search) explores adjacent nodes starting from the initial node and then explores the nodes at the next depth. It is mainly implemented using a queue.

2. Problem: Counting Connected Components

We will tackle the problem of counting the number of connected components in a given undirected graph. The graph consists of vertices and edges, and the goal is to find the number of connected vertices.

Problem Definition

Integer n (1 ≤ n ≤ 1000): Number of vertices
List edges: A tuple (a, b) representing the two vertices connected by each edge.

Return the number of connected components.

Input Example

n = 5
edges = [(1, 2), (2, 3), (4, 5)]

Output Example

2

3. Algorithm Explanation

Both DFS and BFS methods can be used to solve this problem. Here, we will solve it using DFS. The following steps will be taken:

  • Convert the graph into an adjacency list format.
  • Create an array to check whether a vertex has been visited.
  • For each vertex, if there are unvisited vertices, execute DFS and mark all connected vertices as visited within the called DFS.
  • Each time DFS is called, increment the number of connected components by one.

4. Swift Implementation

Let’s implement the problem in Swift.

import Foundation

var graph = [[Int]]()
var visited: [Bool] = []
var connectedComponents = 0

// Define the DFS function
func dfs(node: Int) {
    visited[node] = true
    
    for neighbor in graph[node] {
        if !visited[neighbor] {
            dfs(node: neighbor)
        }
    }
}

// Main function
func connectedComponentsCount(n: Int, edges: [(Int, Int)]) -> Int {
    graph = Array(repeating: [Int](), count: n + 1)
    visited = Array(repeating: false, count: n + 1)
    
    // Create the graph
    for edge in edges {
        let (a, b) = edge
        graph[a].append(b)
        graph[b].append(a)
    }
    
    for i in 1...n {
        if !visited[i] {
            dfs(node: i)
            connectedComponents += 1 // New connected component discovered
        }
    }
    
    return connectedComponents
}

// Example usage
let n = 5
let edges = [(1, 2), (2, 3), (4, 5)]
let result = connectedComponentsCount(n: n, edges: edges)
print("Number of connected components: \(result)") // Output: Number of connected components: 2

5. Algorithm Analysis

The algorithm above explores the graph using DFS, resulting in a time complexity of O(V + E). Here, V is the number of vertices and E is the number of edges. This is because the algorithm visits each vertex once and checks each edge once as well.

6. Conclusion

In this course, we introduced an algorithm to count the number of connected components using DFS. Both DFS and BFS are important techniques for graph traversal, so it is crucial to understand the characteristics and implementation methods of each algorithm thoroughly and practice them. In the next course, we will tackle a similar problem using BFS.

7. References