图算法 Graph Dijkstra Prim

Dijkstra's Algorithm（迪杰斯特拉算法）是一种图论算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。它用于解决单源最短路径问题，即在带权重的有向图中，找到从给定源节点到其他所有节点的最短路径。该算法适用于无负权重边的图。

Dijkstra's Algorithm的基本思想是贪心算法，它从源节点开始，每次选择与当前已知最短路径集合相邻的具有最小权重边的节点，并更新这些节点的最短路径长度。这个过程重复进行，直到找到从源节点到所有其他节点的最短路径。

Dijkstra's Algorithm的基本步骤如下：

创建一个集合S，用于存储已确定最短路径的节点。
创建一个距离数组dist，存储从源节点到其他各个节点的最短路径长度。初始化源节点的距离为0，其他节点的距离为无穷大（表示尚未找到路径）。
当集合S中未包含所有节点时：
a. 从尚未处理的节点中选取距离最小的节点u（不在S中）。
b. 将节点u加入集合S。
c. 遍历u的所有邻接节点v。如果通过u到v的路径比当前已知的从源节点到v的路径更短，更新dist[v]。
当算法结束时，距离数组dist包含了从源节点到图中所有其他节点的最短路径长度。如果需要找到实际的路径，可以在算法过程中记录每个节点的前驱节点，并在最后通过回溯前驱节点来找到完整的路径。

Dijkstra's Algorithm在时间复杂度方面较高。使用优先队列来优化查找距离最小的节点时，算法的时间复杂度为O(|V|^2)，其中|V|表示图中节点的数量。对于稀疏图，可以通过使用二叉堆、斐波那契堆等高级数据结构将时间复杂度降低到O(|V|log|V| + |E|)，其中|E|表示图中边的数量。

struct Graph {
    let vertices: Int
    var adjacencyList: [[(Int, Int)]]

    init(vertices: Int) {
        self.vertices = vertices
        adjacencyList = Array(repeating: [], count: vertices)
    }

    mutating func addEdge(_ source: Int, _ destination: Int, _ weight: Int) {
        adjacencyList[source].append((destination, weight))
    }
}

func dijkstra(graph: Graph, source: Int) -> [Int] {
    var distances = Array(repeating: Int.max, count: graph.vertices)
    distances[source] = 0

    var visited = Array(repeating: false, count: graph.vertices)
    for _ in 0..<graph.vertices {
        var minDistance = Int.max
        var minIndex = -1

        for index in 0..<graph.vertices {
            if !visited[index] && distances[index] < minDistance {
                minDistance = distances[index]
                minIndex = index
            }
        }

        guard minIndex != -1 else { break }

        visited[minIndex] = true
        for (neighbor, weight) in graph.adjacencyList[minIndex] {
            let newDistance = distances[minIndex] + weight
            if newDistance < distances[neighbor] {
                distances[neighbor] = newDistance
            }
        }
    }

    return distances
}
var graph = Graph(vertices: 5)

graph.addEdge(0, 1, 10)
graph.addEdge(0, 2, 5)
graph.addEdge(1, 3, 1)
graph.addEdge(1, 2, 2)
graph.addEdge(2, 1, 3)
graph.addEdge(2, 3, 9)
graph.addEdge(2, 4, 2)
graph.addEdge(3, 4, 4)
graph.addEdge(4, 3, 6)
graph.addEdge(4, 0, 7)

let shortestDistances = dijkstra(graph: graph, source: 0)

print("Shortest distances from source vertex 0: \(shortestDistances)")
// Shortest distances from source vertex 0: [0, 8, 5, 9, 7]

Prim's Algorithm（普里姆算法）是一种用于解决图的最小生成树问题的算法。最小生成树是一个无向连通图的子图，它包括图中所有的顶点和部分边，使得子图形成一棵树，并且边的权重之和最小。Prim's Algorithm由捷克数学家Vojtěch Jarník于1930年提出，美国计算机科学家Robert C. Prim于1957年独立发现了该算法。

Prim's Algorithm基于贪心策略。它从任意一个顶点开始，逐步将顶点添加到生成树中，每次添加的顶点是与已经在树中的顶点相邻并且具有最小权重边的顶点。该过程一直持续到所有顶点都被添加到生成树中。

Prim's Algorithm的基本步骤如下：

初始化一个集合visited，用于存储已经添加到最小生成树中的顶点。
从任意一个顶点开始，将其添加到visited集合中。
当visited集合中的顶点数量小于图中顶点的数量时：
a. 查找具有最小权重的边，使得该边连接已在visited中的顶点和不在visited中的顶点。
b. 将该边以及与其相连的顶点添加到最小生成树中，并将该顶点添加到visited集合中。
当算法结束时，得到的最小生成树包含了图中所有顶点和一部分边，使得生成树的边的权重之和最小。

Prim's Algorithm在时间复杂度方面较高。使用优先队列来优化查找具有最小权重的边时，算法的时间复杂度为O(|V|^2)，其中|V|表示图中顶点的数量。对于稀疏图，可以通过使用二叉堆、斐波那契堆等高级数据结构将时间复杂度降低到O(|V|log|V| + |E|)，其中|E|表示图中边的数量。

struct Graph {
    let vertices: Int
    var adjacencyList: [[(Int, Int)]]

    init(vertices: Int) {
        self.vertices = vertices
        adjacencyList = Array(repeating: [], count: vertices)
    }

    mutating func addEdge(_ source: Int, _ destination: Int, _ weight: Int) {
        adjacencyList[source].append((destination, weight))
        adjacencyList[destination].append((source, weight))
    }
}

func prim(graph: Graph) -> Int {
    var visited = Array(repeating: false, count: graph.vertices)
    visited[0] = true
    var minCost = 0

    for _ in 1..<graph.vertices {
        var minWeight = Int.max
        var minSource = -1
        var minDestination = -1

        for source in 0..<graph.vertices where visited[source] {
            for (destination, weight) in graph.adjacencyList[source] where !visited[destination] {
                if weight < minWeight {
                    minWeight = weight
                    minSource = source
                    minDestination = destination
                }
            }
        }

        if minSource != -1 && minDestination != -1 {
            visited[minDestination] = true
            minCost += minWeight
        }
    }

    return minCost
}
var graph = Graph(vertices: 5)

graph.addEdge(0, 1, 2)
graph.addEdge(0, 3, 6)
graph.addEdge(1, 2, 3)
graph.addEdge(1, 3, 8)
graph.addEdge(1, 4, 5)
graph.addEdge(2, 4, 7)
graph.addEdge(3, 4, 9)

let minimumCost = prim(graph: graph)

print("Minimum cost of the minimum spanning tree: \(minimumCost)")
// Minimum cost of the minimum spanning tree: 16

github仓库地址 https://github.com/SunZhiC/DataStructuresInSwift

References

Data Structures & Algorithms in Swift by Matthijs Hollemans.
https://github.com/apple/swift-algorithms
https://github.com/raywenderlich/swift-algorithm-club