《swift-algorithm-club》——数据结构/图

图(Graphs)

图(Graph)

在计算机科学中，图形被定义为一组点和与之配对的一组边。边可以具有权重，也可以有向的。

在代码中描述图，有两种主要策略；邻接表和邻接矩阵

邻接表(Adjacency List)。在邻接表实现中，每个点存储一个从这个点出发的所有边的列表。

邻接矩阵(Adjacency Matrix)。在邻接矩阵实现中，具有表示顶点的行和列的矩阵存储权重以指示顶点是否链接以及权重。

设V是图中点的数量，E是边数。我们有

public struct Edge<T>: Equatable where T: Equatable, T: Hashable {
  
  public let from: Vertex<T>
  public let to: Vertex<T>
  
  public let weight: Double?
  
}
复制代码

public struct Vertex<T>: Equatable where T: Equatable, T: Hashable {
  public var data: T
  public let index: Int
}
复制代码

代码：邻接表

private class EdgeList<T> where T: Equatable, T: Hashable {
	var vertex: Vertex<T>
  var edges: [Edge<T>]? = nil
  
  init(vertex: Vertex<T>) {
    self.vertex = vertex
  }
  
  func addEdge(_ edge: Edge<T>) {
    edges.append(edge)
  }
}
复制代码

open override func createVertex(_ data: T) -> Vertex<T> {
  // check if the vertex already exists
  let matchingVertices = vertices.filter() { vertex in
  	return vertex.data = data
  }
  
  if matchingVertices.count > 0 {
    return matchingVertices.last!
  }
  
  // if the vertex doesn't exist, creat a new one
  let vertex = Vertex(data: data, index: adjacencyList.count)
  adjcencyList.append(EdgeList(vertex: vertex))
  return vertex
}
复制代码

代码：邻接矩阵

open override func createVertex(_ data: T) -> Vertex<T> {
  // check if the vertex already exist
  let matchingVertices = vertices.filter() { vertex in
    return vertex.data = data
  }
  
  if matchingVertices.count > 0 {
    return matchingVertices.last!
  }
  
  // if the vertex doesn't exist, create a new one
  let vertex = Vertex(data: data, index: adjacencyMatrix.count)
  
  // Expand each existing row to the right one column.
  for i in 0 ..< adjacencyMatrix.count {
    adjacencyMatrix[i].append(nil)
  }
  
  // Add one new row at the bottom.
  let newRow = [Double?](repeating: nil, count: adjacencyMatrix.count + 1)
  adjacencyMatrix.append(newRow)
  
  _vertices.append(vertex)
  
  return vertex
}
复制代码

广度优先搜索

队列的实现

func breadthFirstSearch(_ graph: Graph, source: Node) -> [String] {
  var queue = Queue<Node>()
  queue.enqueue(source)
  
  var nodesExplored = [source.label]
  source.visited = true
  
  while let node = queue.dequeue() {
    for edge in node.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        queue.enqueue(neighborNode)
        beighborNode.visited = true
        nodesExplored.append(neighborNode.label)
      }
    }
  }
  
  return nodesExplored
}
复制代码

BFS可以用于解决

• 计算源节点和其他每个节点之间的最短路径 (仅适用于未加权的图形)。
• 在未加权的图表上计算最小生成树

深度优先搜索

简单递归实现

func depthFirstSearch(_ graph: Graph, source: Node) -> [String] {
  var nodesExpored = [Source.label]
  source.visited = true
  
  for edge in source.neighbors {
    if !edge.neighbor.visited {
      nodesExplored += depthFirstSearch(graph, source: edge.neighbor)
    }
  }
  return nodesExplored
}
复制代码

也可以用栈实现

DFS可以用于解决

• 查找稀疏图的连通分量
• 图中节点的拓扑排序
• 查找图的桥梁
• more

未加权图的最短路径

目标：找到图中从一个节点到另一个节点的最短路径

未加权图：广度优先搜索

func breadthFirstSearchShortestPath(graph: Graph, source: Node) -> Graph {
  let shortestPathGraph = graph.duplicate()

  var queue = Queue<Node>()
  let sourceInShortestPathsGraph = shortestPathGraph.findNodeWithLabel(label: source.label)
  queue.enqueue(element: sourceInShortestPathsGraph)
  sourceInShortestPathsGraph.distance = 0

  while let current = queue.dequeue() {
    for edge in current.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.hasDistance {
        queue.enqueue(element: neighborNode)
        neighborNode.distance = current.distance! + 1
      }
    }
  }

  return shortestPathGraph
}
复制代码

单源最短路径

单源最短路径问题是从一个给定的源顶点到有向加权图中其他所有顶点的最短路径。

Bellman-Ford

u是源顶点，v是有向边的目标顶点，边e = (u, v)

u保持0，其他顶点的初始值为♾

if weights[v] > weights[u] + e.weight {
  weights[v] = weights[u] + e.weight
}
复制代码

未加权图的最小生成树树

深度优先搜索

func breadthFirstSearchMinimumSpanningTree(graph: Graph, source: Node) -> Graph {
  let minimumSpanningTree = graph.duplicate()
  
  var queue = Queue<Node>()
  let sourceInMinimumSpanningTree = minimumSpanningTree.findNodeWithLabel(source.label)
  queue.enqueue(sourceInMinimumSpanningTree)
  sourceInMinimumSpanningTree.visited = true
  
  while let current = queue.dequeue() {
    for edge in current.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        neighborNode.visited = true
        queue.enqueue(neighborNode)
      } else {
        current.remove(edge)
      }
    }
  }
  
  return minimumSpanningTree
}
复制代码

最小生成树

Kruskal算法

根据权重对边进行排序。每次贪婪地选择最小的一个并且只要它不形成环就加入MST。

准备

// Initialize the values to be returned and Union Find data structure.
var cost: Int = 0
var tree = Graph<T>()
var unionFind = UnionFind<T>()
for vertex in graph.vertices {

// Initially all vertices are disconnected.
// Each of them belongs to it's individual set.
  unionFind.addSetWith(vertex)
}
复制代码

排序边：

let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight < $1.weight })
复制代码

一次取一个边并尝试将其插入MST。

for edge in sortedEdgeListByWeight {
  let v1 = edge.vertex1
  let v2 = edge.vertex2 
  
  // Same set means the two vertices of this edge were already connected in the MST.
  // Adding this one will cause a cycle.
  if !unionFind.inSameSet(v1, and: v2) {
    // Add the edge into the MST and update the final cost.
    cost += edge.weight
    tree.addEdge(edge)
    
    // Put the two vertices into the same set.
    unionFind.unionSetsContaining(v1, and: v2)
  }
}
复制代码

Prim算法

准备

// Initialize the values to be returned and Priority Queue data structure.
var cost: Int = 0
var tree = Graph<T>()
var visited = Set<T>()

// In addition to the (neighbour vertex, weight) pair, parent is added for the purpose of printing out the MST later.
// parent is basically current vertex. aka. the previous vertex before neigbour vertex gets visited.
var priorityQueue = PriorityQueue<(vertex: T, weight: Int, parent: T?)>(sort: { $0.weight < $1.weight })
复制代码

排序顶点：

priorityQueue.enqueue((vertex: graph.vertices.first!, weight: 0, parent: nil))
复制代码

// Take from the top of the priority queue ensures getting the least weight edge.
while let head = priorityQueue.dequeue() {
  let vertex = head.vertex
  if visited.contains(vertex) {
    continue
  }

  // If the vertex hasn't been visited before, its edge (parent-vertex) is selected for MST.
  visited.insert(vertex)
  cost += head.weight
  if let prev = head.parent { // The first vertex doesn't have a parent.
    tree.addEdge(vertex1: prev, vertex2: vertex, weight: head.weight)
  }

  // Add all unvisted neighbours into the priority queue.
  if let neighbours = graph.adjList[vertex] {
    for neighbour in neighbours {
      let nextVertex = neighbour.vertex
      if !visited.contains(nextVertex) {
        priorityQueue.enqueue((vertex: nextVertex, weight: neighbour.weight, parent: vertex))
      }
    }
  }
}
复制代码

任意两点间的最短路径

任意两点间的最短路径同时计算图中每个节点到其他节点的最短路径。

Floyd-Warshall算法