图 Trie 堆栈

图形

在计算机科学中,图形是一种抽象数据类型,旨在实现数学中的无向图和有向图概念。图形数据结构由有限(并且可能是可变的)顶点或节点或点组成,以及用于无向图的一组无序的这些顶点对或用于有向图的一组有序对。这些对被称为用于无向图的边,弧或线,以及用于有向图的箭头,有向边,有向弧或有向线。顶点可以是图结构的一部分,或者可以是由整数索引或引用表示的外部实体。图形数据结构还可以将每个边缘值与某个边缘值相关联,例如符号标签或数字属性(成本,容量,长度等)。 (维基百科,来源

//
//  GraphFactory.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 6/7/14.
//  Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation

public class SwiftGraph {
   
    
    //declare a default directed graph canvas
    private var canvas: Array<Vertex>
    public var isDirected: Bool
    
    
    init() {
        canvas = Array<Vertex>()
        isDirected = true
    }
    
    
    //create a new vertex
    func addVertex(key: String) -> Vertex {
        
        
        //set the key
        let childVertex: Vertex = Vertex()
        childVertex.key = key
        
        
        //add the vertex to the graph canvas
        canvas.append(childVertex)
        
        
        return childVertex
    }
    
    
    
    //add edge to source vertex
    func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {
        
        
        //create a new edge
        let newEdge = Edge()
        
        
        //establish the default properties
        newEdge.neighbor = neighbor
        newEdge.weight = weight
        source.neighbors.append(newEdge)
        
        
        print("The neighbor of vertex: \(source.key as String!) is \(neighbor.key as String!)..")
        
        
        //check condition for an undirected graph
        if isDirected == false {
            
            
           //create a new reversed edge
           let reverseEdge = Edge()
            
            
           //establish the reversed properties
           reverseEdge.neighbor = source
           reverseEdge.weight = weight
           neighbor.neighbors.append(reverseEdge)
            
           print("The neighbor of vertex: \(neighbor.key as String!) is \(source.key as String!)..")
            
        }
        
        
    }

    
    
    
    
    /* reverse the sequence of paths given the shortest path.
       process analagous to reversing a linked list. */

    func reversePath(_ head: Path!, source: Vertex) -> Path! {
        
        
        guard head != nil else {
            return head
        }
        
        //mutated copy
        var output = head
        
        
        var current: Path! = output
        var prev: Path!
        var next: Path!
        
        
        while(current != nil) {
            next = current.previous
            current.previous = prev
            prev = current
            current = next
        }
        
        
        //append the source path to the sequence
        let sourcePath: Path = Path()
        
        sourcePath.destination = source
        sourcePath.previous = prev
        sourcePath.total = nil
        
        output = sourcePath
        
        
        return output
        
    }

    
    
    
    //process Dijkstra's shortest path algorthim
    func processDijkstra(_ source: Vertex, destination: Vertex) -> Path? {
        
        
        var frontier: Array<Path> = Array<Path>()
        var finalPaths: Array<Path> = Array<Path>()
        
        
        //use source edges to create the frontier
        for e in source.neighbors {
            
            let newPath: Path = Path()
            
            
            newPath.destination = e.neighbor
            newPath.previous = nil
            newPath.total = e.weight
            
            
            //add the new path to the frontier
            frontier.append(newPath)
            
        }
        

        //construct the best path
        var bestPath: Path = Path()
        
        
        while frontier.count != 0 {
            
            //support path changes using the greedy approach
            bestPath = Path()
            var pathIndex: Int = 0

            
            for x in 0..<frontier.count {
               
                let itemPath: Path = frontier[x]
                
                if  (bestPath.total == nil) || (itemPath.total < bestPath.total) {
                    bestPath = itemPath
                    pathIndex = x
                }
                
            }
            
            
            
            //enumerate the bestPath edges
            for e in bestPath.destination.neighbors {
                
                let newPath: Path = Path()
                
                newPath.destination = e.neighbor
                newPath.previous = bestPath
                newPath.total = bestPath.total + e.weight
                
                
                //add the new path to the frontier
                frontier.append(newPath)
                
            }
            
            
            //preserve the bestPath
            finalPaths.append(bestPath)
            
            
            //remove the bestPath from the frontier
            //frontier.removeAtIndex(pathIndex) - Swift2
            frontier.remove(at: pathIndex)
            
            
            
        } //end while
        
        
    
        //establish the shortest path as an optional
        var shortestPath: Path! = Path()
        
        
        for itemPath in finalPaths {
            
            if (itemPath.destination.key == destination.key) {
                
                if  (shortestPath.total == nil) || (itemPath.total < shortestPath.total) {
                    shortestPath = itemPath
                }
                
            }
            
        }
        
        
        return shortestPath
        
    }
    
    
    
    ///an optimized version of Dijkstra's shortest path algorthim
    func processDijkstraWithHeap(_ source: Vertex, destination: Vertex) -> Path! {
        
        
        let frontier: PathHeap = PathHeap()
        let finalPaths: PathHeap = PathHeap()
        
        
        //use source edges to create the frontier
        for e in source.neighbors {
            
            let newPath: Path = Path()
            
            
            newPath.destination = e.neighbor
            newPath.previous = nil
            newPath.total = e.weight
            
            
            //add the new path to the frontier
            frontier.enQueue(newPath)
            
        }
        
        
        //construct the best path
        var bestPath: Path = Path()
        
        
        while frontier.count != 0 {
                        
            //use the greedy approach to obtain the best path
            bestPath = Path()
            bestPath = frontier.peek()
            
            
            //enumerate the bestPath edges
            for e in bestPath.destination.neighbors {
                
                let newPath: Path = Path()
                
                newPath.destination = e.neighbor
                newPath.previous = bestPath
                newPath.total = bestPath.total + e.weight
                
                
                //add the new path to the frontier
                frontier.enQueue(newPath)
                
            }
            
            
            //preserve the bestPaths that match destination
            if (bestPath.destination.key == destination.key) {
                finalPaths.enQueue(bestPath)
            }
            
            
            //remove the bestPath from the frontier
            frontier.deQueue()
            
            
        } //end while
        
        
        
        //obtain the shortest path from the heap
        var shortestPath: Path! = Path()
        shortestPath = finalPaths.peek()
        
        
        return shortestPath
        
    }
    
    
    //MARK: traversal algorithms
    
    
    //bfs traversal with inout closure function
    func traverse(_ startingv: Vertex, formula: (_ node: inout Vertex) -> ()) {

        
        //establish a new queue
        let graphQueue: Queue<Vertex> = Queue<Vertex>()
        
        
        //queue a starting vertex
        graphQueue.enQueue(startingv)
        
        
        while !graphQueue.isEmpty() {
            
            //traverse the next queued vertex
            var vitem: Vertex = graphQueue.deQueue() as Vertex!
            
            
            //add unvisited vertices to the queue
            for e in vitem.neighbors {
                if e.neighbor.visited == false {
                    print("adding vertex: \(e.neighbor.key!) to queue..")
                    graphQueue.enQueue(e.neighbor)
                }
            }
            

            /*
            notes: this demonstrates how to invoke a closure with an inout parameter.
            By passing by reference no return value is required.
            */
            
            //invoke formula
            formula(&vitem)
            
            
        } //end while
        
        
        print("graph traversal complete..")
        
        
    }

    
    
    
    //breadth first search
    func traverse(_ startingv: Vertex) {
        
        
        //establish a new queue
        let graphQueue: Queue<Vertex> = Queue<Vertex>()
        
        
        //queue a starting vertex
        graphQueue.enQueue(startingv)
        
        
        while !graphQueue.isEmpty() {
            
            //traverse the next queued vertex
            let vitem = graphQueue.deQueue() as Vertex!
            
            guard vitem != nil else {
                return
            }
            
            //add unvisited vertices to the queue
            for e in vitem!.neighbors {
                if e.neighbor.visited == false {
                    print("adding vertex: \(e.neighbor.key!) to queue..")
                    graphQueue.enQueue(e.neighbor)
                }
            }
            
            
            vitem!.visited = true
            print("traversed vertex: \(vitem!.key!)..")
            
            
        } //end while
        
        
        print("graph traversal complete..")
        
        
    } //end function
    
    
    
    //use bfs with trailing closure to update all values
    func update(startingv: Vertex, formula:((Vertex) -> Bool)) {
        
        
        //establish a new queue
        let graphQueue: Queue<Vertex> = Queue<Vertex>()
        
        
        //queue a starting vertex
        graphQueue.enQueue(startingv)
        
        
        while !graphQueue.isEmpty() {
            
            //traverse the next queued vertex
            let vitem = graphQueue.deQueue() as Vertex!            
            
            guard vitem != nil else {
                return
            }
            
            //add unvisited vertices to the queue
            for e in vitem!.neighbors {
                if e.neighbor.visited == false {
                    print("adding vertex: \(e.neighbor.key!) to queue..")
                    graphQueue.enQueue(e.neighbor)
                }
            }
            
            
            //apply formula..
            if formula(vitem!) == false {
                print("formula unable to update: \(vitem!.key)")
            }
            else {
                print("traversed vertex: \(vitem!.key!)..")
            }
            
            vitem!.visited = true
            
            
        } //end while
        
        
        print("graph traversal complete..")
        
        
    }

    

    
    
}

特里

在计算机科学中,trie,也称为数字树,有时候是基数树或前缀树(因为它们可以通过前缀搜索),是一种搜索树 - 一种有序的树数据结构,用于存储动态集或关联键通常是字符串的数组。 (维基百科,来源

//
//  Trie.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 10/14/14.
//  Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation

public class Trie {
    
    private var root: TrieNode!
    
    
    init(){
        root = TrieNode()
    }
    
    
    
    //builds a tree hierarchy of dictionary content
    func append(word keyword: String) {
        
        
        //trivial case
        guard keyword.length > 0 else {
            return
        }
        
        
        var current: TrieNode = root
        
        
        while keyword.length != current.level {
            
            var childToUse: TrieNode!
            let searchKey = keyword.substring(to: current.level + 1)
            
            
            //print("current has \(current.children.count) children..")
            
            
            //iterate through child nodes
            for child in current.children {
                
                if (child.key == searchKey) {
                    childToUse = child
                    break
                }
                
            }
            
            
            //new node
            if childToUse == nil {
                
                childToUse = TrieNode()
                childToUse.key = searchKey
                childToUse.level = current.level + 1
                current.children.append(childToUse)
            }
            
            
            current = childToUse
            
            
        } //end while
        
        
        //final end of word check
        if (keyword.length == current.level) {
            current.isFinal = true
            print("end of word reached!")
            return
        }
        
        
        
    } //end function
    
    

    
    //find words based on the prefix
    func search(forWord keyword: String) -> Array<String>! {
        
        
        //trivial case
        guard keyword.length > 0 else {
            return nil
        }
        
        
        var current: TrieNode = root
        var wordList = Array<String>()
        
        
        while keyword.length != current.level {
            
            var childToUse: TrieNode!
            let searchKey = keyword.substring(to: current.level + 1)
            

            //print("looking for prefix: \(searchKey)..")
            
            
            //iterate through any child nodes
            for child in current.children {
                
                if (child.key == searchKey) {
                    childToUse = child
                    current = childToUse
                    break
                }
                
            }
            
 
            if childToUse == nil {
               return nil
            }
            
            
        } //end while
        
        
        
        //retrieve the keyword and any descendants
        if ((current.key == keyword) && (current.isFinal)) {
            wordList.append(current.key)
        }

        
        //include only children that are words
        for child in current.children {
            
            if (child.isFinal == true) {
                wordList.append(child.key)
            }
            
        }
        
        
        return wordList

        
    } //end function
    

}

(GitHub,来源

在计算机科学中,堆栈是一种抽象数据类型,用作元素的集合,有两个主要操作:push,它向集合添加元素,pop,删除最近添加的尚未删除的元素。元素从堆栈中出现的顺序产生了其替代名称 LIFO(用于后进,先出)。另外,窥视操作可以在不修改堆栈的情况下访问顶部。 (维基百科,来源

请参阅下面的许可证信息和原始代码源( github

//
//  Stack.swift
//  SwiftStructures
//
//  Created by Wayne Bishop on 8/1/14.
//  Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation

class Stack<T> {
    
    private var top: Node<T>
    
    init() {
        top = Node<T>()
    }
    
    
    //the number of items - O(n)
    var count: Int {
        
        
        //return trivial case
        guard top.key != nil else {
          return 0
        }
                
        
        var current = top
        var x: Int = 1
        
        
        //cycle through list
        while current.next != nil {
            current = current.next!
            x += 1
        }
            
        return x        
        
    }
    
    
    //add item to the stack
    func push(withKey key: T) {
        
        
        //return trivial case
        guard top.key != nil else {
            top.key = key
            return
        }
        
        
        //create new item
        let childToUse = Node<T>()
        childToUse.key = key
            
            
        //set new created item at top
        childToUse.next = top
        top = childToUse        

    }
    

    //remove item from the stack
    func pop() {
        
        if self.count > 1 {
            top = top.next
        }
        else {
            top.key = nil
        }
        
    }
    
    
    //retrieve the top most item
    func peek() -> T! {

        
        //determine instance
        if let topitem = top.key {
            return topitem
        }
            
        else {
            return nil
        }
        
    }
    
    
    
    //check for value
    func isEmpty() -> Bool {
        
        if self.count == 0 {
            return true
        }
        
        else {
            return false
        }
        
    }
    

}

麻省理工学院许可证(MIT)

版权所有(c)2015,Wayne Bishop&Arbutus Software Inc.

特此授予任何获得本软件和相关文档文件(软件)副本的人免费许可,无限制地交易本软件,包括但不限于使用,复制,修改,合并的权利根据以下条件,出版,分发,再许可和/或出售本软件的副本,并允许向其提供本软件的人员这样做:

上述版权声明和本许可声明应包含在本软件的所有副本或实质部分中。

本软件按原样提供,不提供任何明示或暗示的保证,包括但不限于适销性,特定用途的适用性和不侵权的保证。在任何情况下,作者或版权所有者均不对任何索赔,损害或其他责任承担任何责任,无论是在合同,侵权或其他方面的行为,是由于,是否与本软件或其中的使用或其他交易有关。软件。