在swift中,想存储一个图的结构,在segmentfault上看到过一个代码,可以实现BFS,如下:
enum VertexState: Int { case white = 0 case gray = 1 case black = 2 } class Vertex { var parent: Vertex? var color: VertexState! var distance: Int var vIndex: Int init (_ index: Int) { self.vIndex = index self.parent = nil self.color = VertexState.white self.distance = 100000 } } var queue: [Vertex] = [] class Adjacency { var adjacency: [Vertex] = [] } class Graph { var vertexArray: [Vertex]! var adjacencyList: [Adjacency]! init (vertexArray: [Vertex], adjacencyList: [Adjacency]) { self.vertexArray = vertexArray self.adjacencyList = adjacencyList } } func BFS(inout graph: Graph, sourceVertex: Vertex) { // sourceVertex置灰入队列 sourceVertex.color = VertexState.gray sourceVertex.distance = 0 sourceVertex.parent = nil queue.append(sourceVertex) // 遍历 while queue.count > 0 { var u = queue[0] queue.removeAtIndex(0) var adj = graph.adjacencyList[u.vIndex] for var i = 0; i < adj.adjacency.count; i++ { var v = adj.adjacency[i] if v.color == VertexState.white { v.color = VertexState.gray v.distance = u.distance + 1 v.parent = u queue.append(v) } u.color = VertexState.black } } } func printPath(g: Graph, s: Vertex, v: Vertex) { if v.vIndex == s.vIndex { print("\(s.vIndex)\t") } else if v.parent == nil { print("no path from s to v exists") } else { printPath(g, s, v.parent!) print("\(v.vIndex)\t") } } var vArray: [Vertex] = [] var adjList: [Adjacency] = [] for var i = 0; i < 8; i++ { var vertex: Vertex = Vertex(i) vArray.append(vertex) } // TEST CASE var adj0: Adjacency = Adjacency() adj0.adjacency = [vArray[1], vArray[2]] var adj1: Adjacency = Adjacency() adj1.adjacency = [vArray[0], vArray[3], vArray[4]] var adj2: Adjacency = Adjacency() adj2.adjacency = [vArray[0], vArray[5]] var adj3: Adjacency = Adjacency() adj3.adjacency = [vArray[1], vArray[4], vArray[6]] var adj4: Adjacency = Adjacency() adj4.adjacency = [vArray[1], vArray[3], vArray[6], vArray[7]] var adj5: Adjacency = Adjacency() adj5.adjacency = [vArray[2]] var adj6: Adjacency = Adjacency() adj6.adjacency = [vArray[3], vArray[4], vArray[7]] var adj7: Adjacency = Adjacency() adj7.adjacency = [vArray[4], vArray[6]] adjList = [adj0, adj1, adj2, adj3, adj4, adj5, adj6, adj7] var g: Graph = Graph(vertexArray: vArray, adjacencyList: adjList) BFS(&g, vArray[0]) printPath(g, vArray[0], vArray[2])
但是我现在要处理的图是带权值的,求帮忙解决一下这个问题