How do I implement topological sort in Swift?

Topological sorting is an algorithm used to order the vertices of a directed acyclic graph (DAG) in such a way that for every directed edge from vertex A to vertex B, vertex A comes before vertex B in the ordering. This can be useful for various applications such as scheduling tasks, organizing dependencies, and more.

Topological Sort Implementation in Swift

Here is a simple implementation of topological sort using Depth-First Search (DFS) in Swift:


    class Graph {
        var adjacencyList: [Int: [Int]] = [:]

        func addEdge(from: Int, to: Int) {
            adjacencyList[from, default: []].append(to)
        }

        func topologicalSort() -> [Int] {
            var visited = Set()
            var stack = [Int]()
            
            for vertex in adjacencyList.keys {
                if !visited.contains(vertex) {
                    dfs(vertex: vertex, visited: &visited, stack: &stack)
                }
            }
            return stack.reversed() // Return in reverse order
        }

        private func dfs(vertex: Int, visited: inout Set, stack: inout [Int]) {
            visited.insert(vertex)
            for neighbor in adjacencyList[vertex, default: []] {
                if !visited.contains(neighbor) {
                    dfs(vertex: neighbor, visited: &visited, stack: &stack)
                }
            }
            stack.append(vertex)
        }
    }

    let graph = Graph()
    graph.addEdge(from: 5, to: 2)
    graph.addEdge(from: 5, to: 0)
    graph.addEdge(from: 4, to: 0)
    graph.addEdge(from: 4, to: 1)
    graph.addEdge(from: 2, to: 3)
    graph.addEdge(from: 3, to: 1)

    let sortedOrder = graph.topologicalSort()
    print("Topological Sort: \(sortedOrder)")

How do I implement topological sort in Swift?

Topological Sort Implementation in Swift

Popular Topics

Recent Languages

How do I implement topological sort in Swift?

Topological Sort Implementation in Swift

Related Questions

Popular Topics

Recent Languages