depth first search in swift

Here is a simple implementation of Depth First Search (DFS) for a graph in Swift using recursion:


main.swift
class Graph {
    var adjList: [Int: [Int]]
    var visited: [Bool]
    
    init() {
        adjList = [Int: [Int]]()
        visited = [Bool]()
    }
    
    func addEdge(_ v: Int, _ w: Int) {
        if adjList[v] == nil {
            adjList[v] = [Int]()
        }
        adjList[v]?.append(w)
    }
    
    func dfs(_ v: Int) {
        visited[v] = true
        print(v)
        
        if let neighbors = adjList[v] {
            for neighbor in neighbors {
                if !visited[neighbor] {
                    dfs(neighbor)
                }
            }
        }
    }
    
    // DFS traversal starting from a given vertex
    func dfsTraversal(_ startNode: Int) {
        visited = Array(repeating: false, count: adjList.count)
        dfs(startNode)
    }
}

// Example usage:
let g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

g.dfsTraversal(2)
932 chars
47 lines

In this implementation, we start with a graph defined as an adjacency list (adjList) and a visited array that keeps track of whether a given vertex has been visited during the DFS traversal.

The addEdge function adds edges to the graph by adding an adjacent vertex to the list of neighbors for a given vertex.

The dfs function performs the actual DFS traversal. We start by marking the current node as visited and printing it. Then, for each neighbor of the current node, we recursively call the dfs function if it hasn't already been visited.

The dfsTraversal function initializes the visited array and starts the DFS traversal from a given starting node.

Finally, we create a Graph instance, add edges to it, and perform a DFS traversal starting from node 2. When we run this code, the output should be: