大部分內(nèi)容來自于《大話數(shù)據(jù)結構》稽犁，代碼全部使用Swift實現(xiàn)。至于為什么抽風寫這個？??你懂的垂睬。

1.線性表

線性表：零個或者多個數(shù)據(jù)元素的有限序列。

性質：

• 數(shù)據(jù)元素可以為空
• 數(shù)據(jù)元素有限
• 數(shù)據(jù)元素之間的邏輯結構為線性結構抗悍，也就是一對一的關系
• 數(shù)據(jù)元素類型相同

舉個例子：
白羊 -> 金牛 -> 雙子 -> 巨蟹 -> 獅子 -> 處女 -> 天秤 -> 射手 -> 摩羯 -> 水平 -> 雙魚

線性表的抽象數(shù)據(jù)類型：
ADT 線性表（List）
Data
      線性表的數(shù)據(jù)對象集合為{a1, a2, ......, an}驹饺，每一個元素的類型都是DataType。其中缴渊，除第一個元素a1外赏壹，每一個元素有且僅有一個直接前驅元素，除了最后一個元素an外衔沼，每一個元素有且僅有一個直接后續(xù)元素蝌借。數(shù)據(jù)元素之間的關系是一對一的關系。
Operation
       count：線性表元素個數(shù)指蚁。
       first：頭指針菩佑。
       last：尾指針。
       isEmpty()：若線性表為空凝化，返回true稍坯，否則返回false。
       remove()：將線性表清空
       node(i)：將線性表中的第i個位置的元素返回。
       insert(data,i)：在線性表中的第i個位置插入新數(shù)據(jù)data瞧哟。
EndADT

線性表根據(jù)在計算機的儲存方式可以分為兩種：

• 順序線性表
• 鏈式線性表

順序線性表

順序線性表：使用一段連續(xù)的地址存儲單元放置線性表的數(shù)據(jù)元素混巧。

舉個例子：數(shù)組。

順序線性表的優(yōu)缺點：
優(yōu)點：
- 可以快速獲取下標的數(shù)據(jù)元素勤揩，時間復雜度為O(1)
- 邏輯關系是一對一的關系咧党，連續(xù)存儲單元足以儲存，不需要增加額外的存儲空間

缺點：
- 插入和刪除操作需要移動大量的元素陨亡，時間復雜度為O(n)
- 線性表的存儲空間大小難以確定傍衡，并且不好擴展
- 造成存儲空間碎片

鏈式線性表

鏈式線性表：線性表的數(shù)據(jù)元素可以存儲在隨意的存儲單元，每一個節(jié)點不僅僅包括數(shù)據(jù)元素還有一個指向下一個節(jié)點的指針（基本的單鏈表）负蠕。

鏈式（單鏈表）和順序線性表優(yōu)缺點對比：

存儲分配方式：
- 順序 -> 一段地址連續(xù)的存儲空間
- 鏈式 -> 任意地址存儲空間

時間性能：
- 查找
  順序 -> O(1)
  鏈式 -> O(n)
- 插入和刪除
  順序 -> O(n)
  鏈式 -> 尋找相應的節(jié)點聪舒，時間復雜度為O(n)，然后虐急，插入和刪除為O(1)

空間性能：
- 順序 -> 需要提前分配存儲空間，分配大了滔迈，浪費空間止吁，分配小了，容易發(fā)生上溢
- 鏈式 -> 不需要提前分配空間燎悍，只要有存儲空間分配就行敬惦，數(shù)據(jù)元素個數(shù)只受可分配存儲空間大小的限制

總結：
（1）若線性表需要頻繁查找，很少進行插入和刪除操作時谈山，使用順序存儲結構俄删；反之，使用鏈式存儲結構奏路。
（2）如果提前知道線性表需要的存儲空間畴椰，可以使用順序結構；如果不知道線性表中的數(shù)據(jù)元素變化有多大鸽粉，即不確定需要多大的存儲空間斜脂，則使用鏈式存儲結構。

鏈式線性表的基本分類：

• 單向鏈表
• 靜態(tài)鏈表 -> 使用順序結構實現(xiàn)鏈式線性表
• 雙向鏈表 -> 每個節(jié)點除了數(shù)據(jù)元素触机，還包含一個指向上一個節(jié)點的指針和一個指向下一個節(jié)點的指針
• 循環(huán)鏈表 -> 線性表的尾部指向頭節(jié)點帚戳，形成一個閉環(huán)

下面具體講解雙鏈表的Swift實現(xiàn)，其他的鏈表實現(xiàn)可以參考《大話數(shù)據(jù)結構》或者自行Googel/Baidu儡首。

雙向鏈表：在單鏈表的基礎上片任，每個節(jié)點加一個指向上一個節(jié)點的指針。

節(jié)點定義：

public class LinkedListNode<T> {
    var data: T  //Data could not be nil.
    var previous: LinkedListNode?  //The pointer to previous node.
    var next: LinkedListNode?  //The pointer to next node.
    init(_ data: T) {
        self.data = data
    }
}

雙向鏈表：

public enum ErrorStatus {
    case Error(message: String)
    case OK
}

public class DoubleLinkedList<T> {
    public typealias Node = LinkedListNode<T>
    
    private var head: Node?  //Head node of link list.
    
    public var isEmpty: Bool {  //If link list has no data, return true.
        return head == nil
    }
    
    public var first: Node? {  //Get first node is the head of link list.
        return head
    }
    
    public var last: Node? {  //Last node of link list.
        ...
        return node
    }
    
    public var count: Int {  //Retrun link list's nodes count.
        ...
        return count
    }
    
    public func node(atIndex index: Int) -> Node? {  //Get node with index
        ...
        return node
    }
    
    public func appendData(data: T) {  //Append data to link list tail
        ...
    }
    
    public func insert(data: T, atIndex index: Int) -> ErrorStatus {  //Insert data at index
        guard index >= 0, index <= count else {
            return ErrorStatus.Error(message: "Index is out of range!")
        }
        let newNode = Node(data)
        if index == 0 {
            if let node = first {
                head = newNode
                newNode.next = node
                node.previous = newNode
            } else {
                head = newNode
            }
        } else {
            let node = self.node(atIndex: index-1)
            let nextNode = self.node(atIndex: index)
            node?.next = newNode
            newNode.previous = node
            newNode.next = nextNode
            nextNode?.previous = newNode
        }
        return ErrorStatus.OK
    }
    
    public func remove(atIndex index: Int) -> (T?, ErrorStatus) {  //Remove node at index
        guard !isEmpty else {
            return (nil, ErrorStatus.Error(message: "Link list is Empty!"))
        }
        
        guard index >= 0, index < count else {
            return (nil, ErrorStatus.Error(message: "Index is out of range!"))
        }
        
        let node = self.node(atIndex: index)
        let nextNode = self.node(atIndex: index+1)
        if index == 0 {
            head = nextNode
        } else {
            let beforeNode = self.node(atIndex: index-1)
            beforeNode?.next = nextNode
            nextNode?.previous = beforeNode
        }
        return (node?.data, ErrorStatus.OK)
    }    
}

??注意：
這里的head指向第一個有數(shù)據(jù)的節(jié)點蔬胯，有的線性表會生成一個頭節(jié)點对供，該節(jié)點不存儲任何數(shù)據(jù)或者只存儲該鏈表的長度，該節(jié)點指向第一個有數(shù)據(jù)的節(jié)點氛濒。這樣做的好處就是犁钟，第一個節(jié)點的刪除和插入操作和其他節(jié)點保持一致棱诱。

下面主要解釋一下，插入和刪除操作：

• insert

public func insert(data: T, atIndex index: Int) -> ErrorStatus {  //Insert data at index
    guard index >= 0, index <= count else {
        return ErrorStatus.Error(message: "Index is out of range!")
    }
    let newNode = Node(data)
    if index == 0 {
        if let node = first {
            head = newNode
            newNode.next = node
            node.previous = newNode
        } else {
            head = newNode
        }
    } else {
        let node = self.node(atIndex: index-1)
        let nextNode = self.node(atIndex: index)
        node?.next = newNode
        newNode.next = nextNode
        newNode.previous = node
        nextNode?.previous = newNode
    }
    return ErrorStatus.OK
}

1.先判斷需要插入數(shù)據(jù)的index是否在[0, count]的范圍之內(nèi)涝动，注意這里是方括號迈勋，也就是包含邊界，因為線性表最前面和最后面都可以插入新的數(shù)據(jù)醋粟。
2.生成新節(jié)點靡菇。
3.因為這里的雙向鏈表沒有采取頭節(jié)點的方式實現(xiàn)，所以米愿，插入第一個節(jié)點和其他節(jié)點有點不一樣厦凤，需要做一些判斷。
4.如果是插入第一個節(jié)點育苟，則判斷如果該鏈表為空较鼓，則直接設置head=newNode沃但；如果該鏈表不為空线召，則將一個節(jié)點賦值給node候址，然后將newNode賦值給head揣苏，接著將node賦值給newNode.next陨仅，最后設置node.previous=newNode君珠。
5.如果不是插入一個節(jié)點八千，則先獲取下標為index-1的節(jié)點node丈咐，然后獲取下標為index的節(jié)點nextNode馍惹。設置node.next=newNode躺率，然后newNode.next=nextNode，連成一條指向下一個數(shù)據(jù)元素的鏈万矾，最后設置newNode.previous=node和nextNode.previous=newNode連上指向上一個數(shù)據(jù)元素的鏈悼吱，自此，先的數(shù)據(jù)插入成功良狈。

• remove
  無論insert還是remove都是先拆鏈舆绎，然后再組合成新的數(shù)據(jù)鏈。

public func remove(atIndex index: Int) -> (T?, ErrorStatus) {  //Remove node at index
    guard !isEmpty else {
        return (nil, ErrorStatus.Error(message: "Link list is Empty!"))
    }
    
    guard index >= 0, index < count else {
        return (nil, ErrorStatus.Error(message: "Index is out of range!"))
    }
    
    let node = self.node(atIndex: index)
    let nextNode = self.node(atIndex: index+1)
    if index == 0 {
        head = nextNode
    } else {
        let beforeNode = self.node(atIndex: index-1)
        beforeNode?.next = nextNode
        nextNode?.previous = beforeNode
    }
    return (node?.data, ErrorStatus.OK)
}

1.先判斷是否是空鏈们颜，如果是則返回吕朵，否則再判斷需要刪除數(shù)據(jù)的小表是否在合理范圍內(nèi)，如果不是則返回窥突。
2.判斷index是否等于0努溃，如果是，則直接將head=secondNode阻问。
3.獲取beforeNode和nextNode梧税，然后將beforeNode.next=nextNode，nextNode,previous=beforeNode，自此第队，下標為index的節(jié)點哮塞，沒有任何對象指向它，在當前函數(shù)域外就外被系統(tǒng)回收掉凳谦。

2.棧與隊列

棧：限定在表尾進行插入和刪除的線性表忆畅。

棧是一種LIFO(Last In First Out)的線性表，也就是數(shù)據(jù)元素遵循后進先出的原則尸执。

棧的抽象數(shù)據(jù)類型：

ADT 棧(Stack)
Data
      具有線性表一樣的性質家凯。
Operation
      top：獲取棧頂元素
      count：棧的長度
      isEmpty：棧內(nèi)元素是否為空
      push(data)：元素進棧
      pop()：元素出棧
      removeAll()：清空棧內(nèi)元素
EndADT

按棧的存儲結構分類：

• 棧的順序存儲結構
  單棧
  共享棧
• 棧的鏈式存儲結構

共享棧：
兩個順序棧共享存儲空間，棧1的棧頂在下標0處如失，棧2的棧頂在下標n-1處绊诲。

棧的順序結構和鏈式結構區(qū)別：
1.順序結構需要預先估算存儲空間大小，適合數(shù)據(jù)元素變化不大的情況
2.鏈式結構不需要預先估算存儲空間褪贵，適合數(shù)據(jù)元素變化較大的情況

棧的鏈式結構實現(xiàn)：

public struct Stack<T> {
    private var stackData: [T] = []
    
    public var count: Int {
        return stackData.count
    }
    
    public var top: T? {
        if isEmpty {
            return nil
        } else {
            return stackData.last
        }
    }
    
    public var isEmpty: Bool {
        return stackData.isEmpty
    }
    
    public mutating func push(data: T) {
        stackData.append(data)
    }
    
    public mutating func pop() -> T? {
        if isEmpty {
            return nil
        } else {
            return stackData.removeLast()
        }
    }
    
    public mutating func removeAll() {
        stackData.removeAll()
    }
    
    public func printAllData() {
        for item in stackData {
            print(item)
        }
    }
}

上面的代碼寫的非常清楚掂之，一目了然，這里就不費口舌了脆丁。

棧較之線性表有什么特別作用世舰？??

棧和線性表的不同之處在于，棧只有進棧和出棧操作偎快，并且遵循后進先出的規(guī)則，也就是說數(shù)據(jù)元素順序進棧洽胶，逆序出棧晒夹。嘿嘿，楁⒚ィ可以實現(xiàn)回退操作丐怯，遞歸和四則運算等等。

• 遞歸
  聽說過斐波那契數(shù)列嗎翔横？??沒錯就是兔子繁殖??：

以月數(shù)為自變量读跷，兔子的對數(shù)為因變量，則它們之間的關系為：

F(0) = 0, n=0
F(1) = 1, n=1
F(n) = F(n-1) + F(n-2), n>1

下面使用常規(guī)的方法解決這個問題：

func rabbitNumbers() {
    //After 40 months
    var r0 = 0
    print("rabbit: \(r0)")
    var r1 = 1
    print("rabbit: \(r1)")
    var r: Int = 0
    for _ in 2..<40 {
        r = r0 + r1
        print("rabbit: \(r)")
        r0 = r1
        r1 = r
    }
}

再者使用遞歸解決這個問題：

func rabbitNumbers(months n: Int) -> Int {
    if n < 2 {
        return n
    }
    return rabbitNumbers(months: n-1)+rabbitNumbers(months: n-2)
}

for i in 0..<40 {
    let rabbits = rabbitNumbers(months: i)
    print("rabbit: \(rabbits)")
}

比較一下前面兩個的差異：

常規(guī)方法：
    使用一個迭代的方式禾唁，計算出結果效览。不需要反復調用函數(shù)，浪費內(nèi)存荡短。但是丐枉，相對于遞歸來說，沒有那么簡潔掘托。
遞歸：
    遞歸就需要不斷調用函數(shù)瘦锹，建立函數(shù)副本，消耗大量的內(nèi)存。但是弯院，相對于常規(guī)方法辱士，代碼簡潔易懂。

為什么說遞歸是棧的應用呢听绳？
遞歸在執(zhí)行的時候颂碘，需要不斷的調用自身，直到可以返回確定的值辫红，然后凭涂，又從最后面的一層，一層層往回調贴妻，直到最上一層切油，這個兩個操作正好對應著棧的壓棧和出棧的操作。其實名惩，編譯器也是這樣干的澎胡，在前行階段，對于每一層遞歸娩鹉，函數(shù)的局部變量攻谁，參數(shù)值和返回地址都壓進棧；在退回階段弯予，位于棧頂?shù)木植孔兞科莼拢瑓?shù)值以及返回地址都被彈出，用于返回調用層次中執(zhí)行代碼的剩余部分锈嫩，恢復調用狀態(tài)受楼。

• 四則運算
  四則運算就有意思了。自己用筆和紙算數(shù)學題知道怎么做呼寸，但是計算機呢艳汽？怎么算加減乘除的？畢竟計算機只能識別0和1对雪。??

一般手動計算數(shù)學題我們用的是中綴表達法（符號在需要運算的數(shù)字中間）：

9 + (3 - 1) * 3 + 10 / 2

計算機運算需要用到的后綴表達法（去調括號河狐，符號在需要運算的數(shù)字后面）：

9 3 1 - 3 * + 10 2 / +

所以？怎么得到后綴表達式呢瑟捣？利用棧：

規(guī)則：
1.遇到數(shù)字馋艺，直接輸出
2.遇到左括號進棧
3.遇到右括號執(zhí)行出棧操作，直到彈出左括號迈套，左括號和右括號不輸出
4.遇到其他操作符丈钙，則判斷其與棧頂操作符的優(yōu)先級，如果其優(yōu)先級（<=）棧頂操作符交汤，則棧頂元素依次出棧雏赦，該操作符進棧
5.直到最后劫笙，將棧中的元素依次輸出

enum OperationPriority: String {
    case multi = "*"
    case divide = "/"
    case add = "+"
    case sub = "-"
    
    var intValue: Int {
        switch self {
        case .multi,.divide:
            return 1
        case .add, .sub:
            return 0
        }
    }
}

func suffixExpFromMiddleExp(exps: Array<String>) -> Array<String>{
    var suffixExp: [String] = Array()
    var stack = Stack<String>()
    let predicate = NSPredicate.init(format: "SELF MATCHES %@", "^[0-9]*$")
    for value in exps {
        if predicate.evaluate(with: value) {
            suffixExp.append(value)
        } else if value == "(" {
            stack.push(data: value)
        } else if value == ")" {
            while stack.top != "(" {
                suffixExp.append(stack.pop() ?? "")
            }
            if stack.top == "(" {
                stack.pop()
            }
        } else {
            //value <= top, stack.pop;value > top, stack.push
            let advantage = OperationPriority.init(rawValue: value)?.intValue ?? 0
            var topAdvantage: Int = 0
            while let top = stack.top, top != "(" {
                topAdvantage = OperationPriority.init(rawValue: top)?.intValue ?? 0
                if advantage > topAdvantage {
                    break
                } else {
                    suffixExp.append(top)
                    stack.pop()
                }
            }
            stack.push(data: value)
        }
    }
    while let top = stack.top {
        suffixExp.append(top)
        stack.pop()
    }
    return suffixExp
}

let exp = ["9", "+", "(", "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"]  
//中綴表達式：9+(3-1)*3+10/2
//后綴表達式：9 3 1 - 3 * + 10 2 / +

注：后綴表達式更多獲取方法。

得到了后綴表達式星岗，那么開始我們的四則運算了填大。??

規(guī)則：
1.數(shù)字直接進棧
2.遇到符號，將棧頂兩個數(shù)字出棧俏橘，進行運算允华，運算結果進棧

//在上面的枚舉加一個計算加減乘除的函數(shù)
enum OperationPriority: String {
    ...
    func result(operator1: String, operator2: String) -> Int {
        switch self {
        case .multi:
            return Int(operator1)!*Int(operator2)!
        case .divide:
            return Int(operator1)!/Int(operator2)!
        case .add:
            return Int(operator1)!+Int(operator2)!
        case .sub:
            return Int(operator1)!-Int(operator2)!
        }
    }
}

func mathOperation(exps: Array<String>) -> Int {
    var result = 0
    var stack = Stack<String>()
    let predicate = NSPredicate.init(format: "SELF MATCHES %@", "^[0-9]*$")
    for value in exps {
        if predicate.evaluate(with: value) {
            stack.push(data: value)
        } else {
            let operator2 = stack.pop()
            let operator1 = stack.pop()
            let temp = (OperationPriority.init(rawValue: value)?.result(operator1: operator1!, operator2: operator2!))!
            stack.push(data: "\(temp)")
        }
    }
    if let resultStr = stack.pop() {
        result = Int(resultStr)!
    }
    return result
}
let exp = ["9", "+", "(", "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"]  
//result=20

是不是很有意思，一個簡單的四則運算就這樣實現(xiàn)出來了寥掐。棧在計算機里面用的挺多的靴寂，比如，系統(tǒng)管理的對象就是放進一個全局棧里面的召耘，等不需要的時候百炬，一個一個出棧，釋放所占的內(nèi)存污它。

隊列：只允許在一端進行插入操作剖踊，而在另一端進行刪除操作的線性表。

隊列其實和顯示社會排隊買東西的隊列一個道理衫贬，都是一邊進德澈，一邊出，插隊是會被所有人鄙視的??固惯，慎重梆造。

隊列的抽象數(shù)據(jù)類型：

ADT 隊列(Queue)
Data
    具有線性表一樣的性質。
Operation
    front：隊列第一個數(shù)據(jù)
    count：隊列的長度
    isEmpty()：隊列是否為空
    enQueue(data)：數(shù)據(jù)進隊列
    deQueue()：數(shù)據(jù)出隊列
    removeAll()：清空隊列內(nèi)的所有數(shù)據(jù)
EndADT

按線性表的存儲結構分類：

• 線性存儲結構
  順序隊列
  循環(huán)順序隊列
• 鏈式存儲結構
  鏈式隊列

順序隊列：就是使用數(shù)組來模擬隊列葬毫，但是數(shù)組的插入和刪除需要移動數(shù)據(jù)镇辉，比較繁瑣。
循環(huán)順序隊列：在順序隊列的基礎上改造供常，使隊列的隊頭和隊尾可以在數(shù)組中循環(huán)變化摊聋，在數(shù)據(jù)插入和刪除就不需要頻繁移動數(shù)據(jù)了鸡捐。但是順序隊列栈暇，都需要提前申請存儲空間，還有溢出的可能箍镜。
鏈式隊列：為了解決順序隊列的不足源祈，引用鏈式隊列。不需要提前申請空間色迂，只不過會引入頻繁申請和釋放的操作香缺。

隊列的鏈式結構實現(xiàn)：

public struct Queue<T> {
    private var queueData: [T] = []
    
    public var front: T? {
        return queueData.first
    }
    
    public var isEmpty: Bool {
        return queueData.isEmpty
    }
    
    public var count: Int {
        return queueData.count
    }
    
    public mutating func enQueue(_ data: T) {
        queueData.append(data)
    }
    
    public mutating func deQueue() -> T? {
        if isEmpty {
            return nil
        } else {
            return queueData.removeFirst()
        }
    }
    
    public mutating func removeAll() {
        queueData.removeAll()
    }
    
    public func printAllData() {
        for value in queueData {
            print(value)
        }
    }
}

隊列有什么作用？
在開發(fā)過程中歇僧，接觸最多的應該是全局并發(fā)隊列图张。為什么要用隊列實現(xiàn)呢锋拖？在我看來，在線程的優(yōu)先級一樣的情況下祸轮，不應該先申請系統(tǒng)資源的先被滿足嗎兽埃？這和在銀行排隊取錢是一個道理。當然适袜，VIP就可以無視我們這些在前臺排隊取錢的渣渣柄错，他們有專門的通道，多么痛的領悟??苦酱。

3.串

串：是由零個或多個字符組成的有限序列售貌，又叫字符串。

字符串在開發(fā)的時候很常用疫萤，以Objective-C為例颂跨，有可變字符串和不可變字符串，兩者的實現(xiàn)數(shù)據(jù)結構應該有點區(qū)別给僵；一個是鏈式存儲結構毫捣，一個是順序存儲結構。

字符串的抽象數(shù)據(jù)類型：

ADT 串（String）
Data
    串中元素僅由一個字符組成帝际，相鄰元素具有前驅和后續(xù)關系蔓同。
Operation
    StringEmpty(S)：若串S為空，返回true蹲诀，否則返回false斑粱。
    ...
EndADT

按存儲結構分類：

• 順序存儲結構的字符串
• 鏈式存儲結構的字符串

字符串的模式匹配
樸素的模式匹配算法：核心思想，需要匹配的字符串和主串從下標0開始匹配脯爪，一旦子串不匹配则北，則子串又從下標0開始匹配，主串則挪到下標1痕慢，不斷的循環(huán)這個過程尚揣，直到主串或者字串當前的下標超過字符串的長度或者匹配成功返回。

let s = "goodgoogle"
let t = "google"

func matchString(s: String, t: String) -> Int {
    var post: Int = -1
    guard !s.isEmpty || !t.isEmpty else {
        return post
    }
    
    var i = 0  //s current index
    var j = 0  //t current index
    
    while i < s.count, j < t.count {
        let sIndex = s.index(s.startIndex, offsetBy: i)
        let tIndex = t.index(t.startIndex, offsetBy: j)
        let sStr = s[sIndex]
        let tStr = t[tIndex]
        if sStr == tStr {
            i = i+1
            j = j+1
        } else {
            i = i-j+1
            j = 0
        }
    }
    if j > t.count-1 {
        post = i-t.count
    }
    return post
}

樸素的模式匹配掖举，雖然快骗，簡單明了，但是效率低塔次。所以方篮，強大的KMP模式匹配算法就應運而生了。
強大的KMP算法励负，這個可以看我之前寫的KMP字符串匹配算法藕溅，這里就不做詳細的介紹了。

4.樹

樹：n（n>=0）個結點的有限集继榆。

特點：
- n=0時巾表，稱為空樹汁掠。
- 在任意一顆非空樹中：
（1）有且僅有一個根結點
（2）當n>1時，其余結點可分為m（m>0）個互不相交的有限集集币，其中每一個集合本身又是一棵樹调塌，并且稱為根的子樹。

結點分類：

• 結點擁有的子樹數(shù)稱為結點的度（Degree）惠猿。
• 度為0的結點稱為葉結點（Leaf）或終端結點羔砾；度不為0的結點稱為非終端結點或分支結點。
• 除根節(jié)點之外偶妖，分支結點也稱為內(nèi)部結點姜凄。
• 樹的度是樹內(nèi)結點的度的最大值。
  
  樹結點
  
  結點間關系：
• 結點的子樹的根稱為該節(jié)點的孩子（Child）趾访，相應地态秧，該結點稱為孩子的雙親（Parent）。
• 同一個雙親的孩子之間互稱兄弟（Sibling）扼鞋。
• 結點的祖先是從根結點到該節(jié)點所經(jīng)分支上的所有結點（包括根結點）申鱼。
• 以某結點為根的子樹中任一結點都稱為該結點的子孫。
  
  樹結點關系
  
  樹的其他相關概念：
• 結點的層次（Level）從根開始定義起云头，根為第一層捐友，根的孩子為第二層。
• 雙親在同一層的結點互稱為堂兄弟溃槐。
• 樹中結點的最大層次稱為書的深度（Depth）或高度匣砖。
• 如果左右子樹是有次序的，不能互換的昏滴，則稱該樹為有序樹猴鲫，否則稱為無序樹。
• 森林（Forest）是m（m >= 0）課互不相交的樹的集合谣殊。
  
  樹的其他相關概念
  
  線性結構 VS 樹結構：

線性結構：
- 第一個數(shù)據(jù)元素：無前驅
- 最后一個數(shù)據(jù)元素：無后續(xù)
- 中間元素：一個前驅拂共，一個后續(xù)

樹結構：
- 根結點：無雙親，唯一
- 葉結點：無孩子姻几，可以多個
- 中間結點：一個雙親宜狐，多個孩子

樹的抽象數(shù)據(jù)類型：

 ADT  樹（tree）
    樹是由一個根結點和若干課子樹構成。樹中結點具有相同數(shù)據(jù)類型及層次關系鲜棠。
Operation
    root：返回根結點肌厨。
    nodes：樹的結點數(shù)
    depth：樹的深度
    ...
EndADT

樹的存儲結構：

• 雙親表示法
• 孩子表示法
• 孩子兄弟表示法

以下圖為例講解樹三種表示法：

樹的三種表示法

雙親表示法：在每個結點中培慌，擁有指向雙親結點的指針（可以擴展子結點或者兄弟結點）豁陆。

孩子表示法：每個結點有多個指針域，其中每個指針指向一棵子樹的根結點吵护，叫多重鏈表表示法；把每個結點排列起來睬涧，以單鏈表做存儲結構镐确，叫孩子表示法。

孩子表示法

孩子兄弟表示法：一個結點設置兩個指針譬圣，分別指向該結點的第一個子結點和該結點的右兄弟。

孩子兄弟表示法

二叉樹

二叉樹：n（n>=0）個結點的有限集合雄坪，該集合或者為空集（空二叉樹）厘熟，或者為由一個根結點和兩顆互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成维哈。

由定義而得出二叉樹的特點：

• 每個結點最多有兩顆子樹
• 左子樹和右子樹是有順序的
• 一個結點如果只有一顆子樹绳姨，也要區(qū)分左右

二叉樹的基本形態(tài)：

• 空二叉樹（沒有結點，包括根結點）
• 只有一個根結點
• 根結點只有左子樹
• 根結點只有右子樹
• 根結點有左右子樹

特殊二叉樹：

• 斜樹：所有結點都只有左子樹的二叉樹叫左斜樹阔挠，反之飘庄，叫右斜樹。
• 滿二叉樹：所有結點都存在左右子樹购撼，并且所有葉結點都在同一層上跪削。
• 完全二叉樹：對一顆具有n個結點的二叉樹按層編號，編號為i（1<=i<=n）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置相同迂求。

二叉樹的性質：

• 性質1：在二叉樹的第i層最多有2^(i-1)的結點（i>=1）碾盐。
• 性質2：深度為k的二叉樹至多有2^k-1個結點（k>=1）。
• 性質3：對任何一顆二叉樹T揩局，如果其終端結點數(shù)為n0廓旬，度為2的結點數(shù)為n2，則n0=n2+1谐腰。
• 性質4：具有n個結點的完全二叉樹的深度為?log2(n)? + 1（?x?表示不大于x的最大整數(shù)）孕豹。
• 性質5：如果對一顆有n個結點的完全二叉樹（其深度為|log2(n)| + 1）的結點按層編號（從第1層到第|log2(n) + 1|層，每層從左到右）十气，對任一結點i（1<= i <= n）有：
  1.如果i=1励背，則結點i是二叉樹的根結點，無雙親砸西；如果i>1叶眉，則其雙親是結點|i/2|。
  2.如果2i>n芹枷，則結點i無左孩子（結點i為葉子結點）衅疙；否則其左孩子是結點2i。
  3.如果2i+1>n鸳慈，則結點i無右孩子饱溢；否則其右孩子是結點2i+1。

性質證明：
-> 性質1
最多結點的二叉樹是滿二叉樹走芋，除了葉結點绩郎，所有結點的度都為2潘鲫，所以，第i層最多有2^(i-1)個結點肋杖。

-> 性質2
由性質1可以每層的結點數(shù)溉仑，則k（k>=1）層二叉樹總共節(jié)點數(shù)為：n = 2^0 + 2^1 + ... 2^(k-1)=1*(1-2^k)/(1-2) = 2^k - 1。

-> 性質3
二叉樹的總結點數(shù)為：n = n0 + n1 + n2（n0為葉結點状植，n1為度為1的結點數(shù)浊竟，n2為度為2的結點數(shù)）；那么結點數(shù)為n的二叉樹有多少條連接線呢津畸？很明顯每個結點逐沙，除了根結點都有指向連接線，所以洼畅，結點數(shù)為n的二叉樹的總連接線為n-1吩案；從一個結點的度來算，度為1的結點會有1條連接線帝簇，連接子結點徘郭；度為2的結點會有2連接線，連接子結點丧肴；根結點沒有雙親結點残揉，所以沒有連向根結點的連接線，那么有：n-1 = 1*n0 + 2*n2芋浮；和第一條方程式聯(lián)合可得：n0=n2+1抱环。

-> 性質4
設置有n個結點的完全二叉樹的深度為k，則：
2^(k-1)-1< n <= 2^k-1
因為k是整數(shù)纸巷，所以：
2^(k-1)<= n < 2^k
取對數(shù)得：
k-1<=log2(n)<k镇草，即：k<=log2(n)+1并且k>log2(n)
所以：k=|log2(n)| + 1

-> 性質5.1
由性質1，2可得：
深度為k的二叉樹有：結點2^(k-1) - 1的右孩子為：2^k-1瘤旨，其左孩子為：2^k-2
左孩子除以2得：2^k-2 = 2^(k-1) - 1等于其雙親結點
右孩子除以2得：2^k-1 = 2^(k-1) - 1 + 1/2比其雙親結點大1/2梯啤，向下取整為：2^(k-1) - 1
所以，性質5.1成立存哲。
-> 性質5.2
由性質5.1可知因宇，n（n>1）結點的雙親為|n/2|，也就是說祟偷，深度最大察滑，最右邊的雙親結點<=n/2，則如果2i>n修肠，說明i只能是葉結點不是雙親結點贺辰，所以，沒有左孩子。由5.1可得魂爪，2i<=n，則i的左孩子為2i艰管。
-> 性質5.3
由5.2可的2i其實就是i的左孩子滓侍，則2i+1就是i的右孩子，那么2i+1>n牲芋，即超過了最大的結點數(shù)撩笆，所有沒有右孩子。

二叉樹的存儲結構

完全二叉樹

• 二叉樹順序存儲結構
  由于二叉樹每個結點最多只有2個子樹缸浦，并且左右子樹是有順序的夕冲，所以，可以使用數(shù)組直接存儲裂逐。

  
  
  數(shù)組1

• 二叉樹鏈式存儲結構

  
  
  鏈表1

二叉樹遍歷

二叉樹的遍歷是指從根結點出發(fā)歹鱼，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問有且僅有一次卜高。

三種遍歷次序：

• 前序遍歷
  若二叉樹為空弥姻，則返回；否則掺涛，先遍歷根結點庭敦，然后遍歷左子樹，再遍歷右子樹薪缆。
• 中序遍歷
  如果二叉樹為空秧廉，則返回；否則拣帽，從根結點開始疼电，先遍歷左子樹，然后是根結點减拭，左后是右子樹澜沟。
• 后續(xù)遍歷
  如果二叉樹為空，則返回峡谊；否則茫虽，從根結點開始，先遍歷左子樹既们，然后遍歷右子樹濒析。
• 層序遍歷
  如果二叉樹為空，則返回啥纸；否則号杏，從樹的第一層，根結點開始訪問，從上而下逐層遍歷盾致，在同一層中主经，按從左到右的順序逐個結點訪問。

完全二叉樹1

class BinTNode<T>: NSObject{
    var data: T
    var lChild: BinTNode<T>?
    var rChild: BinTNode<T>?
    init(_ data: T) {
        self.data = data
    }
}

//前序遍歷
func preOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    
    print(tNode.data)
    preOrderTraverse(t: tNode.lChild)
    preOrderTraverse(t: tNode.rChild)
}
前序遍歷結果：ABDHIEJCFG => A->(B->(D->H->I)->(E->J))->(C->F->G)

//中序遍歷
func inOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    inOrderTraverse(t: tNode.lChild)
    print(tNode.data)
    inOrderTraverse(t: tNode.rChild)
}
中序遍歷結果：HDIBJEAFCG => ((H<-D->I)<-B->(J<-E))<-A->(F<-C->G)

//后序遍歷
func postOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    postOrderTraverse(t: tNode.lChild)
    postOrderTraverse(t: tNode.rChild)
    print(tNode.data)
}
后序遍歷結果：HIDJEBFGCA => ((H->I->D)->(J->E)->B)->(F->G->C)->A

//層敘遍歷
func layerOrderTraverse(t: BinTNode<String>?) {
    guard let tNode = t else {
        return
    }
    
    var array: [BinTNode<String>] = [tNode]
    while !array.isEmpty {
        let count = array.count
        for i in 0...count-1 {
            let node = array[i]
            print(node.data)
            if let lNode = node.lChild {
                array.append(lNode)
            }
            if let rNode = node.rChild {
                array.append(rNode)
            }
        }
        array.removeSubrange(Range.init(NSRange(location: 0, length: count))!)
    }
}
層序遍歷結果：ABCDEFGHIJ => A->(B->C)->(D->E->F->G)->(H->I->J)

線索二叉樹

線索二叉樹：指向前驅和后續(xù)的指針稱為線索庭惜，加上線索的二叉樹稱為線索二叉樹罩驻。

線索二叉樹的數(shù)據(jù)結構：

class BinTNode<T>: NSObject {
    let data: T
    var lChild: BinTNode<T>?  
    var rChild: BinTNode<T>? 
    var lTag: Bool = false  //lTag = true，lChild指向前驅护赊；否則惠遏，指向左子樹
    var rTag: Bool = false  //rTag = true，rChild指向后續(xù)骏啰；否則节吮，指向右子樹
    init(_ data: T) {
        self.data = data
    }
}

以上面的完全二叉樹1為例：

線索二叉樹

以中序遍歷線索化：

//中序遍歷
func inOrderTraverse_Thread(t: BinTNode<String>?) {
    var p = t?.lChild
    while p != t {
        while p?.lTag == false {  //二叉樹最左邊
            p = p?.lChild
        }
        print(p?.data ?? "")  //打印數(shù)據(jù)
        while p?.rChild != t, p?.rTag == true {
            p = p?.rChild
            print(p?.data ?? "")
        }
        p = p?.rChild
    }
}
核心實現(xiàn)思路：
1.遍歷二叉樹的最左結點，然后輸出
2.通過后續(xù)指針獲取雙親結點判耕，然后輸出
3.遍歷到右子樹透绩，重復1，2兩步驟

如果所用的二叉樹需經(jīng)常遍歷或查找結點時需要某種遍歷序列中的前驅和后續(xù)壁熄，那么采取線索二叉鏈表的存儲結構就是非常不錯的選擇渺贤。

樹、森林與二叉樹的轉換

• 樹轉換為二叉樹

1.加線请毛。在所有兄弟結點之間加一條線志鞍。
2.去線。對樹中每個結點方仿，只保留它與第一個孩子結點的連線固棚，刪除它與其他孩子之間的連線。
3.層次調整仙蚜。以樹的根結點為軸心此洲，將整個樹順時針旋轉一定的角度，使之結構層次分明委粉。

樹 -> 二叉樹

• 森林轉換為二叉樹

1.把每棵樹轉換為二叉樹呜师。
2.第一棵二叉樹不動，從第二棵二叉樹開始贾节，依次把后一棵二叉樹的根結點作為前一棵二叉樹的根結點的右孩子汁汗，用線連接起來。當所有的二叉樹連接起來后就得到了由森林轉換來的二叉樹栗涂。

森林 -> 二叉樹

• 二叉樹轉換為樹

1.加線知牌。若某個結點的左孩子結點存在，則將這個左孩子的n個右孩子結點都作為此結點的孩子斤程。
2.去線角寸。刪除原二叉樹中所有結點與其右孩子結點的連線。
3.層次調整。使之結構層次分明扁藕。

二叉樹 -> 樹

• 二叉樹轉換為森林

1.去線沮峡。從根結點開始，若右孩子存在亿柑，則把與右孩子相連的線去調邢疙，再看分離的二叉樹，繼續(xù)上個步驟橄杨。
2.將每棵分離的二叉樹再轉換成樹秘症。

二叉樹 -> 森林

• 樹與森林的遍歷

樹的遍歷：
1.先根遍歷：
先訪問根結點照卦，然后依次先根遍歷每個子樹式矫。
2.后根遍歷：
先依次后根遍歷每課子樹，再訪問根結點役耕。
比如：圖二叉樹 -> 樹采转，先根遍歷：ABEFCDG  后根遍歷：EFBCGDA

森林的遍歷：
1.前序遍歷：
使用先根依次遍歷每課樹。
2.后序遍歷：
使用后根依次遍歷每棵樹瞬痘。
比如：圖二叉樹 -> 森林故慈，前序遍歷：ABCDEFGHJI 后序遍歷：BCDAFEJHIG

赫夫曼樹

赫夫曼樹：從樹中一個結點到另一個結點之間的分支構成兩個結點之間的路徑，路徑上的分支數(shù)目稱作路徑長度框全。樹的路徑長度就是從樹根到每一結點的路徑長度之和察绷。其中，帶權路徑長度WPL最小的二叉樹稱作赫夫曼樹津辩。

赫夫曼樹

二叉樹a中拆撼，根結點到A的路徑為1，帶權路徑為：15x1=15
所以喘沿，二叉樹a的路徑為：1+2+3+4+4 = 14闸度；二叉樹b的路徑為：3+3+2+2+2 = 12
二叉樹a的帶權路徑為：1x5 + 2x15 + 3x40 + 4x30 + 4x10 = 315
二叉樹b的帶權路徑為：3x5 + 3x15 + 2x40 + 2x30 + 2x10 = 220
如果有10000名學生需要計算成績，則二叉樹a需要判斷：(315÷100)x10000 = 31500次蚜印；二叉樹b需要判斷：(220÷100)x10000 = 22000次莺禁，后者是前者的2/3。所以窄赋，赫夫曼樹可以很有效的把比較的次數(shù)降低哟冬，加快計算的速度。赫夫曼編碼忆绰，也是一種壓縮編發(fā)方式柒傻，可以很有效的減少目標的大小而不丟失信息。

• 構造赫夫曼樹

步驟：
1.先把結點按照權值的大小排成一列：A5较木，E10红符，B15，D30，C40预侯。
2.取權值最小的兩個結點A5和E10作為一個新結點N?的兩個子結點致开，權值較小的作為左子樹，較大的作為右子樹萎馅。然后双戳，N?的權值為兩個子結點的權值之和：5+10=15。
        N?
      /    \
     A      E
3.將N1代替A5和E10插入前面的有序序列：N?15糜芳，B15飒货，D30，C40峭竣。
4.重復步驟2塘辅，直到遍歷所有的結點，得到赫夫曼樹皆撩。
        T
     ????/  \????
     C     N?
       ???? /  \????
        N?    D
     ????/  \????
     N?    B
   ??/  \????
   A    E
WPL：40*1 + 30*2 + 15*3 + 5*4 + 10*4 = 205

• 赫夫曼編碼
  赫夫曼編碼就是主要解決遠距離通信的數(shù)據(jù)傳輸?shù)淖顑?yōu)化的問題扣墩。因為，計算機里數(shù)據(jù)都是通過二進制來傳輸?shù)目竿蹋糜⑽?6個字母來說呻惕，每個字母在一天文章中出現(xiàn)的概率不一樣，那么每個字母和出現(xiàn)的概率可以構造一顆赫夫曼樹滥比，通過減少每個字母的二進制位數(shù)來壓縮文件大小亚脆，這就是赫夫曼編碼的應用。

6.圖

圖：由頂點的有窮非空集合和頂點之間邊的集合組成盲泛，通常表示為：G(V, E)濒持，其中G表示一個圖，V是圖G中頂點的集合查乒，E是圖G中邊的集合弥喉。

特點：

• 頂點集合不能為空
• 邊的集合可以為空

各種圖定義

• 無向圖：若頂點v1到v2之間的邊沒有方向，則稱這條邊為無向邊玛迄，用無序偶對(v1, v2)來表示由境。無向圖就是圖中任意兩個頂點之間的邊都是無向邊。
  

  無向圖

• 有向圖：若從頂點v1到v2的邊有方向蓖议，則稱這條邊為有向邊虏杰，也稱為弧。用有序偶對<v1, v2>來表示勒虾，v1稱為弧尾纺阔，v2稱為弧頭。有向圖就是圖中任意兩條邊都是有向邊修然。
  

  有向圖

• 簡單圖：在圖中笛钝，不存在頂點到其自身的邊质况，并且同一條邊不重復出現(xiàn)，稱為簡單圖玻靡。
  

  非簡單圖

• 完全圖：如果在無向圖中结榄，任意兩個頂點之間都存在邊，則稱為完全圖囤捻。
  

  完全圖

• 有向完全圖：如果任意兩個頂點之間都存在互為相反的兩條弧臼朗，則稱為又想完全圖。
  

  有向完全圖

• 有很少條邊或弧的圖稱為稀疏圖蝎土，反之稱為稠密圖久橙。（數(shù)量不一定）

• 與圖的邊或者弧相關的數(shù)字叫做權辙芍，帶權的圖稱為網(wǎng)谈息。

• 子圖：假設有兩個圖G=(V, {E})和G1=(V1, {E1})漾抬，如果V1?V鹰贵，且E1?E组底，則稱G1為G的子圖笤受。

圖的頂點和邊之間的關系

圖1

• 頂點的度：
  對于無向圖G=(V,{E})颂斜，如果邊(V,V1)∈E淀弹，則稱頂點V和V1互為鄰接點丹壕，頂點V的度是和V相關聯(lián)的邊的數(shù)目，記為TD(V)薇溃。如圖1菌赖，A的度TD(A)=3，TD(B)=2沐序，TD(C)=3琉用，TD(D)=2，則各個頂點的度總和為：3+2+3+2=10策幼，而圖1無向圖的邊數(shù)為5邑时，即各個頂點的度的總和的一半。
  對于有向圖G=(V,{E})特姐，如果弧<V,V1>∈E晶丘，則稱頂點V和V1互為鄰接點；以頂點V為頭的弧的數(shù)目稱為V的入度唐含，記為ID(V)浅浮；以頂點V為尾的弧的數(shù)目稱為V的出度，記為OD(V)捷枯；則頂點TD(V)=ID(V)+OD(V)滚秩。如圖1有向圖，TD(A)=ID(A)+OD(A)=2+1=3淮捆，各頂點的出度和為：1+2+1+0=4郁油，各頂點的入度和為：2+0+1+1=4本股，有向圖的邊的總數(shù)4，所以桐腌，有向圖邊的總數(shù)=各頂點的出度數(shù)=各頂點的入度數(shù)痊末。

• 路徑：
  從一個頂點到另一個頂點所走過的頂點和邊所連成的通道。比如圖1的無向圖哩掺，從B到D有四條路徑凿叠，分別是(BAD)，(BCD)嚼吞，(BACD)盒件，(BCAD)。而圖1從B到D的路徑是有方向的舱禽，即(BAD)炒刁，(BCAD)。路徑的長度是路徑上的邊數(shù)或弧的數(shù)目誊稚。序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑翔始。

• 回路或環(huán)：
  點一個頂點和最后一個頂點相同的路徑稱為回路或者環(huán)。其中里伯，除了第一個頂點和最后一個頂點城瞎，其余頂點不重復出現(xiàn)的回路，稱為簡單回路或簡單環(huán)疾瓮。下面圖1左邊就是簡單回路脖镀，右邊并不是簡單回路，因為頂點C重復出現(xiàn)了狼电。
  

  圖2

• 連通圖：
  在無向圖G中蜒灰，如果從頂點V到頂點V1有路徑，則稱頂點V和頂點V1是連通的肩碟。如果對于圖中任意兩個頂點都是連通的强窖，則稱G是連通圖。如圖3削祈，左邊的圖不是連通圖翅溺，右邊的圖是連通圖。
  

  圖3
  
  
  圖4

• 連通分量：
  無向圖中的極大連通子圖稱為連通分量岩瘦。
  （1）子圖未巫。
  （2）子圖是連通的。
  （3）連通的子圖含有極大的頂點數(shù)启昧。
  （4）具有極大頂點數(shù)的連通子圖包含依附于這些頂點的所有邊叙凡。
  比如圖3中，左邊的圖的連通分量為右邊的圖密末。
  在有向圖G中握爷，如果對于每一對V1跛璧，V2∈V，V1≠V2新啼，從V1到V2和從V2到V1都存在路徑追城，則稱G是強連通圖。有向圖中極大強連通子圖稱做有向圖的強連通分量燥撞。上圖4中左邊的圖不是強連通圖座柱，右邊的圖是強連通圖。
• 無向圖生成樹：
  一個連通圖的生成樹是一個極小的連通子圖物舒，它含有圖中全部的n個頂點色洞，但只有足以構成一棵樹的n-1條邊。比如圖2中左邊的無向圖冠胯，它的連通分量為自身火诸，則它的極小連通子圖為，自身去調AC和AD兩條邊荠察，則構成一個極小連通圖置蜀，因為再去多一條邊就構不成連通圖了，這個就是連通圖的生成樹悉盆。
• 有向樹：
  如果一個有向圖恰有一個頂點的入度為0盯荤，其余頂點的入度都為1，則是一顆有向樹舀瓢。（不需要連通）
• 生成森林：
  一個有向圖的生成森林由若干有向樹組成廷雅，含有圖中全部頂點耗美，但只有足以構成若干課不相交的有向樹的弧京髓。
  
  圖5

圖的抽象數(shù)據(jù)類型

ADT 圖(Graph) 
Data
    頂點是有窮且非空集合+邊的集合
Operation
    ...
    addVertex(v)：添加頂點
    addEdge(v1, v2)：添加邊
    DFSTraverse()：深度優(yōu)先遍歷
    BFSTraverse()：廣度優(yōu)先遍歷
    ...
EndADT

圖的數(shù)據(jù)存儲

鄰接矩陣：用兩個數(shù)組來表示圖。一個一維數(shù)組儲存圖中頂點信息商架，一個二維數(shù)組（稱為鄰接矩陣）存儲圖中的邊或弧的信息堰怨。

• 無向圖
  
  鄰接矩陣圖1

鄰接矩陣圖2

信息：
（1）v1的度即為第1行，所有元素之和：1+0+1+0=2蛇摸。
（2）v1的鄰接點即為第1行备图，所有元素為1的頂點。
（3）判斷v1到v2是否有邊赶袄，只需要判斷arc[1][2]==1?就行揽涮，所以，v1到v2有邊饿肺。

• 有向圖
  

  鄰接矩陣3
  
  信息：
  （1）v1的出度為第1行的元素之和：1+0+1+0=2蒋困；v1的入度為第1列的元素之和：0+0+1+0=1。
  （2）判斷v0到v3是否有弧敬辣，只需要判斷arc[0][3]==1?就行雪标，所以零院，v0到v3是有弧的。（v3到v0沒有弧村刨，弧是有方向的）

• 帶權有向圖
  就是將有向圖的鄰接矩陣中的0和1換成相應的權值告抄，不存在則設置為∞，自身則設置為0嵌牺。
  

  鄰接矩陣4

鄰接表：數(shù)組和鏈表組合的存儲方法稱為鄰接表打洼。

鄰接表處理：
（1）圖中頂點使用一個一維數(shù)組存儲。
（2）圖中每個頂點v的所有鄰接點構成一個線性表逆粹。

• 無向圖鄰接表：

  
  
  鄰接表圖1

• 有向圖鄰接表和逆鄰接表：
  （1）有向圖鄰接表記錄的是頂點的出度的弧拟蜻，即弧尾。
  （2）有向圖逆鄰接表記錄的是頂點的入度的弧枯饿，即弧頭酝锅。

  
  
  鄰接表圖2

• 帶權鄰接表

  
  
  鄰接表圖3

十字鏈表：即把鄰接表與逆鄰接表結合起來。（有向鄰接表的優(yōu)化）

• 重新定義頂點

  
  
  十字鏈表頂點
  
  

  data為數(shù)據(jù)域奢方，firstin為入邊的表頭指針搔扁，firsetout為出邊的表頭指針。頂點的入邊從firstin開始查詢蟋字，同理稿蹲，頂點的出邊從firstout開始查詢。

• 重新定義邊結點結構

  
  
  十字鏈表結點
  
  

  tailvex是指弧尾結點的下標鹊奖，headvex是指弧頭結點的下標苛聘；headlink是指弧頭結點下標和headvex相同的另一個弧頭結點下標，同理忠聚，taillink是指弧尾結點下標和tailvex相同的另一個弧尾結點下標设哗，沒有置為空。

舉個例子：

十字鏈表圖1

v0的入度為：1->0, 2->0两蟀，v0的出度為：0->3网梢。

鄰接多重表：改造邊結點，使刪除某一條邊不需要遍歷兩次赂毯。

鄰接多重表結點

其中ivex和jvex是與某條邊依附的兩個頂點在頂點表中的下標战虏。ilink指向依附頂點ivex的下一條邊，jlink指向依附頂點jvex的下一條邊党涕。

鄰接多重表

上圖總共有5條邊烦感，分別是v0->v1，v1->v2膛堤，v2->v3手趣，v3->v0，v0-v2骑祟，所以回懦，會有5個邊結點气笙。然后從v0開始，有三條鄰接的邊怯晕，分別是v0-v1潜圃，v0-v2，v0-v3舟茶，首先vo指向E(0,1)谭期，然后當前的邊結點的ivex=0，所以吧凉，ilink需要找到下一條頂點為v0的邊隧出，順著邊結點往下找，可以找到E(3,0)阀捅，所以胀瞪，ilink指向E(3,0)，由于饲鄙，v0還有另外一條邊E(0,2)凄诞，所以，jlink順著往下找忍级，找到E(0,2)帆谍，再往下沒有邊結點了，所以置為空轴咱。其他頂點的操作也是相似的過程汛蝙。

邊集數(shù)組：邊集數(shù)組是由兩個一位數(shù)組組成。一個是存儲頂點信息朴肺，另一個是存儲邊的信息窖剑。這個數(shù)組每個數(shù)據(jù)元素由一條邊的起點下標(begin)，終點下標(end)和權(weight)組成宇挫。

邊集數(shù)組

圖的遍歷

圖的遍歷：從圖中某一頂點出發(fā)訪遍圖中其余頂點苛吱，且使每一個頂點被訪問一次。

• 深度優(yōu)先遍歷（DFS）
  連通圖深度優(yōu)先遍歷： 從圖中的某個頂點v出發(fā)器瘪，訪問此頂點，然后從v的未被訪問的鄰接頂點出發(fā)绘雁，深度優(yōu)先遍歷圖橡疼，直到圖中所有和v有路徑相通的頂點被訪問到。
  非連通圖深度優(yōu)先遍歷：先對一個頂點進行連通圖深度優(yōu)先遍歷庐舟，若還有沒有被訪問的頂點欣除，再對該頂點進行連通圖深度優(yōu)先遍歷，直到圖中所有頂點都被訪問到挪略。

深度優(yōu)先遍歷圖1

鄰接矩陣存儲圖历帚，深度優(yōu)先遍歷實現(xiàn)算法

使用深度優(yōu)先遍歷圖1實現(xiàn)深度優(yōu)先遍歷算法
//鄰接矩陣
public struct Graph<T: Equatable> {
    fileprivate var vexs: [T] = []
    fileprivate var arc: [[Int]] = []
    public var vertexes: Int {
        return vexs.count
    }
    public var edges: Int {
        var count = 0
        for items in arc {
            for item in items {
                if item > 0 {
                    count += 1
                }
            }
        }
        return count
    }
    
    public mutating func addVertex(vertext: T) {
        vexs.append(vertext)
        for i in 0..<arc.count {
            var temp = arc[i]
            temp.append(0)
            arc[i] = temp
        }
        
        let newArray = Array(repeating: 0, count: arc.count+1)
        arc.append(newArray)
    }
    
    public mutating func addEdge(from top1: T, to top2: T) {
        let containTop1 = vexs.contains { $0 == top1 }
        let containTop2 = vexs.contains { $0 == top2 }
        
        guard containTop1, containTop2 else {
            return
        }
        
        let row = vexs.index(of: top1)!
        let column = vexs.index(of: top2)!
        arc[row][column] = 1
    }
}

var graphics = Graph<String>()
graphics.addVertex(vertext: "A")
graphics.addVertex(vertext: "B")
graphics.addVertex(vertext: "C")
graphics.addVertex(vertext: "D")
graphics.addVertex(vertext: "E")
graphics.addVertex(vertext: "F")
graphics.addVertex(vertext: "G")
graphics.addVertex(vertext: "H")
graphics.addVertex(vertext: "I")

graphics.addEdge(from: "A", to: "B")
graphics.addEdge(from: "A", to: "F")
graphics.addEdge(from: "B", to: "C")
graphics.addEdge(from: "B", to: "I")
graphics.addEdge(from: "B", to: "G")
graphics.addEdge(from: "C", to: "I")
graphics.addEdge(from: "C", to: "D")
graphics.addEdge(from: "D", to: "I")
graphics.addEdge(from: "D", to: "E")
graphics.addEdge(from: "D", to: "G")
graphics.addEdge(from: "D", to: "H")
graphics.addEdge(from: "E", to: "F")
graphics.addEdge(from: "E", to: "H")
graphics.addEdge(from: "F", to: "G")
graphics.addEdge(from: "G", to: "H")

//深度優(yōu)先遍歷
var visited: [Bool] = []
func DFS(graphics: Graph<String>, i: Int) {
    visited[i] = true
    print(graphics.vexs[i])
    
    for j in 0..<graphics.vertexes {
        if graphics.arc[i][j] == 1, !visited[j] {
            DFS(graphics: graphics, i: j)
        }
    }
}

func DFSTraverse(graphics: Graph<String>) {
    for _ in 0..<graphics.vertexes {
        visited.append(false)
    }
    
    for i in 0..<graphics.vertexes {
        if !visited[i] {
            DFS(graphics: graphics, i: i)
        }
    }
}

DFSTraverse(graphics: graphics)

輸出結果：ABCDEFGHI

鄰接鏈表存儲圖滔岳，深度優(yōu)先遍歷實現(xiàn)算法：

class EdgeNode<T: Equatable> {
    var index: Int
    var nextEdge: EdgeNode<T>?

    init(atIndex index: Int) {
        self.index = index
    }
}

class VertexNode<T: Equatable> {
    var data: T
    var firstEdge: EdgeNode<T>?

    init(_ data: T) {
        self.data = data
    }
}

class Graphics<T: Equatable> {
    var adjList: [VertexNode<T>] = []
    var numVertexes: Int {
        return adjList.count
    }
    var numEdges: Int {
        var count = 0
        for vertex in adjList {
            if let edge = vertex.firstEdge {
                count += 1
                var next = edge.nextEdge
                while next != nil {
                    count += 1
                    next = next?.nextEdge
                }
            }
        }
        return count/2
    }

    func addVertex(vertex: T) {
        let v = VertexNode<T>(vertex)
        adjList.append(v)
    }

    func addEdge(from v1: T, to v2: T) {
        let vertex1 = getVertex(data: v1)
        let vertex2 = getVertex(data: v2)
        guard vertex1 != nil, vertex2 != nil else {
            return;
        }

        let index1 = getVertextIndex(v1)!
        let index2 = getVertextIndex(v2)!
        
        vertextAddEdge(vertex: vertex1!, index: index2)
        vertextAddEdge(vertex: vertex2!, index: index1)
    }

    func vertextAddEdge(vertex: VertexNode<T>, index: Int) {
        var edgeNode = vertex.firstEdge
        guard edgeNode != nil else {
            vertex.firstEdge = EdgeNode<T>(atIndex: index)
            return;
        }

        let value = adjList[index].data
        if adjList[(edgeNode?.index)!].data == value {
            return
        }
        while edgeNode?.nextEdge != nil {
            edgeNode = edgeNode?.nextEdge
            if adjList[(edgeNode?.index)!].data == value {
                return
            }
        }
        edgeNode?.nextEdge = EdgeNode<T>(atIndex: index)
    }

    func getVertex(data: T) -> VertexNode<T>? {
        for v in adjList {
            if v.data == data {
                return v
            }
        }
        return nil
    }

    func getVertextIndex(_ data: T) -> Int? {
        for index in 0..<adjList.endIndex {
            let vertex = adjList[index]
            if vertex.data == data {
                return index
            }
        }
        return nil
    }
}

let graphics = Graphics<String>()
graphics.addVertex(vertex: "A")
graphics.addVertex(vertex: "B")
graphics.addVertex(vertex: "C")
graphics.addVertex(vertex: "D")
graphics.addVertex(vertex: "E")
graphics.addVertex(vertex: "F")
graphics.addVertex(vertex: "G")
graphics.addVertex(vertex: "H")
graphics.addVertex(vertex: "I")

graphics.addEdge(from: "A", to: "B")
graphics.addEdge(from: "A", to: "F")
graphics.addEdge(from: "B", to: "A")
graphics.addEdge(from: "B", to: "C")
graphics.addEdge(from: "B", to: "G")
graphics.addEdge(from: "B", to: "I")
graphics.addEdge(from: "C", to: "B")
graphics.addEdge(from: "C", to: "D")
graphics.addEdge(from: "C", to: "I")
graphics.addEdge(from: "D", to: "C")
graphics.addEdge(from: "D", to: "E")
graphics.addEdge(from: "D", to: "G")
graphics.addEdge(from: "D", to: "H")
graphics.addEdge(from: "D", to: "I")
graphics.addEdge(from: "E", to: "D")
graphics.addEdge(from: "E", to: "F")
graphics.addEdge(from: "E", to: "H")
graphics.addEdge(from: "F", to: "G")
graphics.addEdge(from: "G", to: "B")
graphics.addEdge(from: "G", to: "D")
graphics.addEdge(from: "G", to: "F")
graphics.addEdge(from: "G", to: "H")

var visited: [Bool] = []
func DFS(graphics: Graphics<String>, i: Int) {
    visited[i] = true
    print(graphics.adjList[i].data)

    var edgeNode = graphics.adjList[i].firstEdge
    while edgeNode != nil {
        if !visited[(edgeNode?.index)!] {
            DFS(graphics: graphics, i: (edgeNode?.index)!)
        }
        edgeNode = edgeNode?.nextEdge
    }
}

func DFSTraverse(graphics: Graphics<String>) {
    for _ in 0..<graphics.numVertexes {
        visited.append(false)
    }

    for i in 0..<graphics.numVertexes {
        if !visited[i] {
            DFS(graphics: graphics, i: i)
        }
    }
}

DFSTraverse(graphics: graphics)
輸出結果：ABCDEFGHI

• 廣度優(yōu)先遍歷（BFS）
  如果深度優(yōu)先遍歷類似于樹的前序遍歷，那么廣度優(yōu)先遍歷則類似于樹的層遍歷挽牢。與深度優(yōu)先遍歷圖1為例谱煤，則廣度優(yōu)先遍歷的順序則為：
  （1）A（2）BF（3）CIGE（4）DH。

鄰接矩陣存儲圖禽拔，廣度優(yōu)先遍歷實現(xiàn)算法

var visited: [Bool] = []

func BFSTraverse(graphics: Graph<String>) {
    for _ in 0..<graphics.vertexes {
        visited.append(false)
    }
    
    var result: [String] = []
    for i in 0..<graphics.vertexes {
        if !visited[i] {
            visited[i] = true
            print(graphics.vexs[i])
            result.append(graphics.vexs[i])
            while !result.isEmpty {
                result.removeFirst()
                for j in 0..<graphics.vertexes {
                    if graphics.arc[i][j] == 1, !visited[j] {
                        visited[j] = true
                        print(graphics.vexs[j])
                        result.append(graphics.vexs[j])
                    }
                }
            }
        }
    }
}

BFSTraverse(graphics: graphics)
輸出結果：ABFCDIEHG

鄰接鏈表存儲圖刘离，深度優(yōu)先遍歷實現(xiàn)算法：

var visited: [Bool] = []
func BFSTraverse(graphics: Graphics<String>) {
    for _ in 0..<graphics.numVertexes {
        visited.append(false)
    }
    
    var result: [VertexNode<String>] = []
    for i in 0..<graphics.numVertexes {
        if !visited[i] {
            visited[i] = true
            print(graphics.adjList[i].data)
            result.append(graphics.adjList[i])
            while !result.isEmpty {
                let vertex = result.removeFirst()
                var edgeNode = vertex.firstEdge
                while edgeNode != nil {
                    if !visited[(edgeNode?.index)!] {
                        visited[(edgeNode?.index)!] = true
                        print(graphics.adjList[(edgeNode?.index)!].data)
                        result.append(graphics.adjList[(edgeNode?.index)!])
                    }
                    edgeNode = edgeNode?.nextEdge
                }
            }
        }
    }
}

BFSTraverse(graphics: graphics)
輸出結果：ABFCGIEDH

比較：深度優(yōu)先遍歷適合目標比較明確，而廣度優(yōu)先遍歷更適合在不斷擴大范圍時找到相對最優(yōu)解的情況睹栖。

最小生成樹

最小生成樹：構造連通網(wǎng)的最小代價生成樹稱為最小生成樹硫惕。

尋找最小生成樹的兩種算法：普里姆算法(Prim)和克魯斯卡爾算法(Kruskal)。

• 普里姆算法

假設N是連通網(wǎng)野来，TE是N上最小生成樹中邊的集合恼除。算法從U={u0}(u0∈V)，TE={}開始曼氛。重復執(zhí)行下述操作：在所有u∈V,v∈V-U的邊(u,v)∈E中缚柳，找一條代價最小的邊(u0,v0)并入集合TE，同時v0并入U搪锣，直至U=V為止秋忙。此時TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹构舟，時間復雜度為O(n^2)灰追。通俗來講，先從v0開始狗超，找到和v0連接的權重最小的邊的頂點v1弹澎，然后再找{v0,v1}相連的權重最小的邊，直到所有頂點都找完努咐。

func miniSpanTree_prim(graphics: Graph<String>) {
    var adjvex = Array(repeating: 0, count: graphics.vertexes)  //初始化都為0苦蒿，意味著從v0開始找
    var lowcost = graphics.arc[0] //初始化為v0所關聯(lián)的所有邊的權值
    
    //因為v0已經(jīng)在adjvex里面了，所以從下標1開始尋找
    var min: Int
    for _ in 1..<graphics.vertexes {
        min = Int.max  //lowcost下標為0則說明該頂點已被找過渗稍，下標為Int.max則意味著佩迟，沒有該條邊
        var k = 0 //保存最小值的下標
        for j in 1..<graphics.vertexes {
            if lowcost[j] != 0, lowcost[j] < min {
                min = lowcost[j]
                k = j
            }
        }
        print("\(adjvex[k], k)")  //adjvex[k]為當前的頂點，k為當前頂點關聯(lián)權值最小邊的頂點的下標
        //將找到的最小權值邊的下一個頂點加入adjvex竿屹，并且將該頂點相關聯(lián)的較小邊加入lowcost
        for j in 1..<graphics.vertexes {
            if lowcost[j] != 0, graphics.arc[k][j] < lowcost[j] {
                lowcost[j] = graphics.arc[k][j]
                adjvex[j] = k
            }
        }
    }
}

miniSpanTree_prim(graphics: graphics)
輸出結果：
(0, 1)
(0, 5)
(1, 8)
(8, 2)
(1, 6)
(6, 7)
(7, 4)
(7, 3)

• 注意點：每添加一個頂點报强，lowcost數(shù)組中除了對應已選則的頂點為0之外，保存已選頂點和未選頂點之間的所有較小的邊拱燃。

• 克魯斯卡爾算法

假設 N= (V秉溉，{E})是連通網(wǎng)，則令最小生成樹的初始狀態(tài)為只有 n 個頂點而無邊的 非連通圖 T={V，{}}召嘶，圖中每個頂點自成一個連通分量父晶。在 E 中選擇代價最小的邊，若 該邊依附的頂點落在 T 中不同的連通分量上弄跌，則將此邊加入到 T 中甲喝，否則舍去此邊而 選擇下一條代價最小的邊。依次類推碟绑，直至 T 中所有頂點都在罔一連通分量上為止 俺猿，時間復雜度為O(eloge)。通俗來講就是格仲，先把所有的邊按照權值的大小排序押袍，然后從最小的開始選擇，每選擇一次需要判斷是否和之前已選擇的邊形成回路凯肋，如果形成回路則選擇下一條邊谊惭，直到所有的邊都被遍歷完，所得就是最小生成樹侮东。

struct Edge{
    let begin: Int, end: Int, weight: Int
    init (begin: Int, end: Int, weight: Int) {
        self.begin = begin
        self.end = end
        self.weight = weight
    }
}

func miniSpanTree_Kruskal(graphics: Graph<String>) {
    var edges: [Edge] = []  //邊集數(shù)組
    for i in 1..<graphics.vertexes {
        let arc = graphics.arc[i-1]
        for j in i..<graphics.vertexes {
            if arc[j] < Int.max {
                let edge = Edge(begin: i-1, end: j, weight: arc[j])
                edges.append(edge)
            }
        }
    }
    edges.sort{$0.weight < $1.weight}
    var parent = Array(repeating: 0, count: graphics.vertexes)  //判斷是否成環(huán)的數(shù)組
    for i in 0..<edges.count {
        let n = find(parent: parent, fedge: edges[i].begin)
        let m = find(parent: parent, fedge: edges[i].end)
        if n != m {  //一條邊從兩邊開始計算圈盔，只要最后的點相等，則會構成環(huán)
            parent[n] = m
            print("\(edges[i].begin, edges[i].end) \(edges[i].weight)")
        }
    }
}

//尋找每個點的路徑
func find(parent: [Int], fedge: Int) -> Int {
    var result = fedge
    while parent[result] > 0 {
        result = parent[result]
    }
    return result
}

miniSpanTree_Kruskal(graphics: graphics)

• 注意點：parent數(shù)組悄雅，從下標開始和相應下標數(shù)組中的值驱敲，形成該頂點的一條路徑。

• 兩個算法對比：
  對比兩個算法宽闲，克魯斯卡爾算法主要是針對邊來展開众眨，邊數(shù)少時效率會非常高，所以對于稀疏圖有很大的優(yōu)勢容诬。而普里姆算法對于稠密圖娩梨，即邊數(shù)非常多的情況會更 好一些。

最短路徑

對于網(wǎng)圖來說览徒，最短路徑狈定，是指兩頂點之間經(jīng)過的邊上權值之和最小的路徑，并且习蓬，我們稱路徑上第一個頂點為源點纽什，最后一個頂點為終點。

以下面的網(wǎng)圖友雳，尋找最短路徑：

最短路徑

var graphics = Graph<String>()
graphics.addVertex(vertext: "v0")
graphics.addVertex(vertext: "v1")
graphics.addVertex(vertext: "v2")
graphics.addVertex(vertext: "v3")
graphics.addVertex(vertext: "v4")
graphics.addVertex(vertext: "v5")
graphics.addVertex(vertext: "v6")
graphics.addVertex(vertext: "v7")
graphics.addVertex(vertext: "v8")

//最短路徑
graphics.addEdge(from: "v0", to: "v1", weight: 1)
graphics.addEdge(from: "v0", to: "v2", weight: 5)

graphics.addEdge(from: "v1", to: "v0", weight: 1)
graphics.addEdge(from: "v1", to: "v2", weight: 3)
graphics.addEdge(from: "v1", to: "v3", weight: 7)
graphics.addEdge(from: "v1", to: "v4", weight: 5)

graphics.addEdge(from: "v2", to: "v0", weight: 5)
graphics.addEdge(from: "v2", to: "v1", weight: 3)
graphics.addEdge(from: "v2", to: "v4", weight: 1)
graphics.addEdge(from: "v2", to: "v5", weight: 7)

graphics.addEdge(from: "v3", to: "v1", weight: 7)
graphics.addEdge(from: "v3", to: "v4", weight: 2)
graphics.addEdge(from: "v3", to: "v6", weight: 3)

graphics.addEdge(from: "v4", to: "v1", weight: 5)
graphics.addEdge(from: "v4", to: "v2", weight: 1)
graphics.addEdge(from: "v4", to: "v3", weight: 2)
graphics.addEdge(from: "v4", to: "v5", weight: 3)
graphics.addEdge(from: "v4", to: "v6", weight: 6)
graphics.addEdge(from: "v4", to: "v7", weight: 9)

graphics.addEdge(from: "v5", to: "v2", weight: 7)
graphics.addEdge(from: "v5", to: "v4", weight: 3)
graphics.addEdge(from: "v5", to: "v7", weight: 5)

graphics.addEdge(from: "v6", to: "v3", weight: 3)
graphics.addEdge(from: "v6", to: "v4", weight: 6)
graphics.addEdge(from: "v6", to: "v7", weight: 2)
graphics.addEdge(from: "v6", to: "v8", weight: 7)

graphics.addEdge(from: "v7", to: "v4", weight: 9)
graphics.addEdge(from: "v7", to: "v5", weight: 5)
graphics.addEdge(from: "v7", to: "v6", weight: 2)
graphics.addEdge(from: "v7", to: "v8", weight: 4)

graphics.addEdge(from: "v8", to: "v6", weight: 7)
graphics.addEdge(from: "v8", to: "v7", weight: 4)

• 迪杰斯特拉（Dijkstra）算法

從源點開始稿湿，找到源點到下一個最短路徑的頂點。然后押赊，在之前的基礎上，再找下一個最短路徑的頂點，直到終點流礁。該算法的時間復雜度為O(n^2)涕俗。

func shortestPath_Dijkstra(graphics: Graph<String>) {
    var final = Array(repeating: 0, count: graphics.vertexes)  //final[N]=1劝枣，表示求的頂點v0至vN的最短路徑
    var pathArc = Array(repeating: 0, count: graphics.vertexes)  //儲存最短路徑下標前驅的數(shù)組
    var shortPathTable: [Int] = []  //表示v0到各個頂點的最短路徑長度
    for i in 0..<graphics.vertexes {
        shortPathTable.append(graphics.arc[0][i])
    }
    final[0] = 1  //v0-v0不需要求路徑
    //開始求v0到各個頂點的最短路徑
    for _ in 1..<graphics.vertexes {
        var min = Int.max  //當前所知離v0頂點最近的距離
        var k = 0
        for w in 0..<graphics.vertexes {
            if final[w] == 0, shortPathTable[w] < min {
                k = w
                min = shortPathTable[w]
            }
        }
        final[k] = 1
        //修正最短路徑
        for w in 0..<graphics.vertexes {
            if final[w] == 0, min < shortPathTable[w]-graphics.arc[k][w]{
                shortPathTable[w] = min + graphics.arc[k][w]
                pathArc[w] = k
            }
        }
    }
    
    print(final)
    print(pathArc)
    print(shortPathTable)
}

shortestPath_Dijkstra(graphics: graphics)
//輸出結果
[1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 4, 2, 4, 3, 6, 7]
[0, 1, 4, 7, 5, 8, 10, 12, 16]

• 說明：
  剛開始final數(shù)組為：[1, 0, 0, 0, 0, 0, 0, 0, 0]碟狞，因為從v0開始，v0算是找到了最短路徑编整；pathArc數(shù)組為：[0, 0, 0, 0, 0, 0, 0, 0, 0]找御；shortestPathTable數(shù)組為：[0, 1, 5, ∞, ∞, ∞, ∞, ∞, ∞]元镀。因為v0-v1=1 < v0-v2=5，所以霎桅，v0下一個最短路徑的頂點是v1栖疑，這時候final為[1, 1, 0, 0, 0, 0, 0, 0, 0]，那么滔驶，既然找到了下一個最短路徑的頂點v1遇革，那么，和v1相連的頂點路徑的權值和shortestPathTable中的權值比較揭糕，取較小者的權值萝快。到此，v0-v1以及和v1相連的頂點的較小權值都得到了著角，繼續(xù)重復上面的步驟直到終點揪漩，就可以得到從v0-v8各個頂點到v0的最小路徑了。

• 佛洛伊德（Floyd）算法

關鍵公式：D[ v ][ w ] = min { D[ v ][ w ] , D[ V ][0] + D[0][W] }吏口，主要思想就是：求v1到v2經(jīng)過最短路徑奄容，有v1->v2，v1->v0->v2锨侯，則v1->v2的最短路徑為兩者最短的路徑嫩海。以此類推，在其基礎上求v1-v3的路徑也是一樣的囚痴。算法時間復雜度為O(n^3)叁怪。

//佛洛伊德算法
func ShortestPath_Floyd(graphics: Graph<String>) {
    //初始化矩陣
    var pathmatirx: [[Int]]
    var shortPathTable: [[Int]] = graphics.arc
    
    var rowValue: [Int] = []
    for i in 0..<graphics.vertexes {
        rowValue.append(i)
    }
    pathmatirx = Array(repeating: rowValue, count: graphics.vertexes)
    
    //開始算法
    for k in 0..<graphics.vertexes {
        for v in 0..<graphics.vertexes {
            for w in 0..<graphics.vertexes {
                if shortPathTable[v][k] < Int.max, shortPathTable[k][w] < Int.max, shortPathTable[v][w] > shortPathTable[v][k] + shortPathTable[k][w] {
                    shortPathTable[v][w] = shortPathTable[v][k] + shortPathTable[k][w]
                    pathmatirx[v][w] = pathmatirx[v][k]
                }
            }
        }
    }
    
    //打印最短路徑
    var k = 0
    for v in 0..<graphics.vertexes {
        for w in v+1..<graphics.vertexes {
            print("v\(v)-v\(w) weight: \(shortPathTable[v][w])")
            k = pathmatirx[v][w]
            print("path: \(v)")
            while k != w {
                print(" -> \(k)")
                k = pathmatirx[k][w]
            }
            print(" -> \(w)")
        }
        print("\n")
    }
}

ShortestPath_Floyd(graphics: graphics)

//輸出結果
[0, 1, 4, 7, 5, 8, 10, 12, 16]   //v0達到各頂點的最短路徑
[1, 0, 3, 6, 4, 7, 9, 11, 15]
[4, 3, 0, 3, 1, 4, 6, 8, 12]
[7, 6, 3, 0, 2, 5, 3, 5, 9]
[5, 4, 1, 2, 0, 3, 5, 7, 11]
[8, 7, 4, 5, 3, 0, 7, 5, 9]
[10, 9, 6, 3, 5, 7, 0, 2, 6]
[12, 11, 8, 5, 7, 5, 2, 0, 4]
[16, 15, 12, 9, 11, 9, 6, 4, 0]
//前驅矩陣
[0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2, 2, 2, 2]
[1, 1, 2, 4, 4, 4, 4, 4, 4]
[4, 4, 4, 3, 4, 4, 6, 6, 6]
[2, 2, 2, 3, 4, 5, 3, 3, 3]
[4, 4, 4, 4, 4, 5, 7, 7, 7]
[3, 3, 3, 3, 3, 7, 6, 7, 7]
[6, 6, 6, 6, 6, 5, 6, 7, 8]
[7, 7, 7, 7, 7, 7, 7, 7, 8]

• 說明：獲取v0->v8的最短路徑，則P[0][8] = 1深滚，P[1][8] = 2奕谭，P[2][8] = 4，P[4][8] = 3痴荐，P[3][8] = 6血柳，P[6][8] = 7，P[7][8] = 8生兆，所以难捌，v0->v8的最短路徑為：v0->v1->v2->v4->v3->v6->v7-V8。

• 兩個算法總結：
  如果只需求其中兩個頂點之間的最短路徑，采用迪杰斯特拉算法根吁；如果需要求所有頂點到所有頂點的最短路徑员淫，可以采用佛洛依德算法，雖然击敌，兩個算法計算所有頂點到所有頂點的最短路徑的時間復雜度都是O(n^3)介返，但是佛洛依德算法比較簡潔，不易出錯沃斤。

拓撲結構

在一個表示工程的有向圖中圣蝎，用頂點表示活動，用弧表示活動之間的優(yōu)先關系衡瓶，這樣的有向圖表示的網(wǎng)徘公，稱為AOV網(wǎng)（Activity On vertex Network）。假設G=(V,E)是一個具有n個頂點的有向圖鞍陨，V中的頂點序列v1, v2, v3, ...... , Vn步淹，滿足若從頂點vi到vj有一條路徑，則中頂點序列中頂點vi必須在vj之前诚撵，我們稱這樣的頂點序列為一個拓撲序列缭裆。拓撲排序，就是對一個有向圖構造拓撲序列的過程寿烟。拓撲序列的主要作用是確定一個有向圖確定的有序序列澈驼，比如：iOS開發(fā)使用拓撲序列來整理整個工程的文件依賴，比如檢查循環(huán)依賴筛武，比如確認從那個依賴文件開始編譯等等缝其。兩個特點：1.無環(huán)有向圖 2.兩個頂點之間的方向只有一個。

AVO圖.png

AVO圖鏈表表示.png

extension Int {
    static func += (left: inout Int, right: Int) {
        left = left + right
    }
    
    static func -= (left: inout Int, right: Int) {
        left = left - right
    }
}

//邊表結點
class EdgeNode {
    var adjex = 0
    var weight = 1
    var next: EdgeNode?
}

//頂點表結點
class VertexNode {
    var inEdge = 0
    var data = 0
    var firstEdge: EdgeNode?
}

class GraphAdjList {
    var adjList: [VertexNode] = []
    var numEdges = 0
    var numVertexes : Int {
        return adjList.count
    }
}

let graphiAdjList = GraphAdjList()

//V0
let v0 = VertexNode()
v0.inEdge = 0
v0.data = 0

let v0E11 = EdgeNode()
v0E11.adjex = 11
let v0E5 = EdgeNode()
v0E5.adjex = 5
let v0E4 = EdgeNode()
v0E4.adjex = 4

v0.firstEdge = v0E11
v0E11.next = v0E5
v0E5.next = v0E4

//V1
let v1 = VertexNode()
v1.inEdge = 0
v1.data = 1

let v1E8 = EdgeNode()
v1E8.adjex = 8
let v1E4 = EdgeNode()
v1E4.adjex = 4
let v1E2 = EdgeNode()
v1E2.adjex = 2

v1.firstEdge = v1E8
v1E8.next = v1E4
v1E4.next = v1E2

//V2
let v2 = VertexNode()
v2.inEdge = 2
v2.data = 2

let v2E9 = EdgeNode()
v2E9.adjex = 9
let v2E6 = EdgeNode()
v2E6.adjex = 6
let v2E5 = EdgeNode()
v2E5.adjex = 5

v2.firstEdge = v2E9
v2E9.next = v2E6
v2E6.next = v2E5

//V3
let v3 = VertexNode()
v3.inEdge = 0
v3.data = 3

let v3E13 = EdgeNode()
v3E13.adjex = 13
let v3E2 = EdgeNode()
v3E2.adjex = 2

v3.firstEdge = v3E13
v3E13.next = v3E2

//V4
let v4 = VertexNode()
v4.inEdge = 2
v4.data = 4

let v4E7 = EdgeNode()
v4E7.adjex = 7

v4.firstEdge = v4E7

//V5
let v5 = VertexNode()
v5.inEdge = 3
v5.data = 5

let v5E12 = EdgeNode()
v5E12.adjex = 12
let v5E8 = EdgeNode()
v5E8.adjex = 8

v5.firstEdge = v5E12
v5E12.next = v5E8

//V6
let v6 = VertexNode()
v6.inEdge = 1
v6.data = 6

let v6E5 = EdgeNode()
v6E5.adjex = 5

v6.firstEdge = v6E5

//V7
let v7 = VertexNode()
v7.inEdge = 2
v7.data = 7

//V8
let v8 = VertexNode()
v8.inEdge = 2
v8.data = 8

let v8E7 = EdgeNode()
v8E7.adjex = 7

v8.firstEdge = v8E7

//V9
let v9 = VertexNode()
v9.inEdge = 2
v9.data = 9

let v9E11 = EdgeNode()
v9E11.adjex = 11
let v9E10 = EdgeNode()
v9E10.adjex = 10

v9.firstEdge = v9E11
v9E11.next = v9E10

//V10
let v10 = VertexNode()
v10.inEdge = 1
v10.data = 10

let v10E13 = EdgeNode()
v10E13.adjex = 13

v10.firstEdge = v10E13

//V11
let v11 = VertexNode()
v11.inEdge = 2
v11.data = 11

//V12
let v12 = VertexNode()
v12.inEdge = 1
v12.data = 12

let v12E9 = EdgeNode()
v12E9.adjex = 9

v12.firstEdge = v12E9

//V13
let v13 = VertexNode()
v13.inEdge = 2
v13.data = 13

graphiAdjList.adjList.append(v0)
graphiAdjList.adjList.append(v1)
graphiAdjList.adjList.append(v2)
graphiAdjList.adjList.append(v3)
graphiAdjList.adjList.append(v4)
graphiAdjList.adjList.append(v5)
graphiAdjList.adjList.append(v6)
graphiAdjList.adjList.append(v7)
graphiAdjList.adjList.append(v8)
graphiAdjList.adjList.append(v9)
graphiAdjList.adjList.append(v10)
graphiAdjList.adjList.append(v11)
graphiAdjList.adjList.append(v12)
graphiAdjList.adjList.append(v13)

func toPologicalSort(gl: GraphAdjList) {
    var count = 0, top = 0, k = 0, getTop = 0
    var stack: [Int] = []
    //將有向圖所有入度為0的頂點入棧
    for i in 0..<gl.numVertexes {
        if gl.adjList[i].inEdge == 0 {
            stack.append(i)
            top += 1
        }
    }
    //開始算拓撲序列
    while top != 0 {
        getTop = stack.removeLast()
        top -= 1
        print("vertex: \(gl.adjList[getTop].data)")
        count += 1
        var edgeNode = gl.adjList[getTop].firstEdge
        while edgeNode != nil {
            k = (edgeNode?.adjex)!
            gl.adjList[k].inEdge -= 1
            if gl.adjList[k].inEdge == 0 {
                stack.append(k)
                top += 1
            }
            edgeNode = edgeNode?.next
        }
    }
    
    if count < gl.numVertexes {
        print("Error")
    } else {
        print("OK")
    }
}

toPologicalSort(gl: graphiAdjList)
//輸出結果
vertex: 3
vertex: 1
vertex: 2
vertex: 6
vertex: 0
vertex: 4
vertex: 5
vertex: 8
vertex: 7
vertex: 12
vertex: 9
vertex: 10
vertex: 13
vertex: 11

• 拓撲排序并不是唯一的
• 拓撲排序簡要說明：

1.先找到所有入度為0的頂點徘六，并依次進棧内边。
2.從棧頂開始，出棧待锈；然后漠其，遍歷該棧頂元素的鏈表，每個頂點的入度減1竿音，判斷每個頂點的入度是否為0和屎，如果為0則入棧，否則跳過春瞬。
3.判斷棧是否還有元素柴信，如果棧不為空，則回到第2步宽气，否則随常，結束潜沦。

關鍵路徑

拓撲排序解決一個工程能否順利進行的問題，那么线罕，關鍵路徑就是解決工程完成需要的最短時間問題止潮。在一個表示工程的帶權有向圖中窃判，用頂點表示事件钞楼，用有向邊表示活動，用邊上的權值表示活動的持續(xù)時間袄琳，這種有向圖的邊表示活動的網(wǎng)询件，我們稱之為 AOE網(wǎng) (Activity On Edge Network) 。 我們把AOE網(wǎng)中沒有人邊的頂點稱為始點或源點唆樊，沒有出邊的頂點稱為終點或匯點宛琅。我們把路徑上各個活動所持續(xù)的時間之和稱為路徑長度，從源點到匯點具有最大長度的路徑叫關鍵路徑逗旁，在關鍵路徑上的活動叫關鍵活動嘿辟。

AOE圖.png

AOE鏈表顯示.png

//V0
let v0 = VertexNode()
v0.inEdge = 0
v0.data = 0

let v0E2 = EdgeNode()
v0E2.adjex = 2
v0E2.weight = 4
let v0E1 = EdgeNode()
v0E1.adjex = 1
v0E1.weight = 3

v0.firstEdge = v0E2
v0E2.next = v0E1

//V1
let v1 = VertexNode()
v1.inEdge = 1
v1.data = 1

let v1E4 = EdgeNode()
v1E4.adjex = 4
v1E4.weight = 6
let v1E3 = EdgeNode()
v1E3.adjex = 3
v1E3.weight = 5

v1.firstEdge = v1E4
v1E4.next = v1E3

//V2
let v2 = VertexNode()
v2.inEdge = 1
v2.data = 2

let v2E5 = EdgeNode()
v2E5.adjex = 5
v2E5.weight = 7
let v2E3 = EdgeNode()
v2E3.adjex = 3
v2E3.weight = 8

v2.firstEdge = v2E5
v2E5.next = v2E3

//V3
let v3 = VertexNode()
v3.inEdge = 2
v3.data = 3

let v3E4 = EdgeNode()
v3E4.adjex = 4
v3E4.weight = 3

v3.firstEdge = v3E4

//V4
let v4 = VertexNode()
v4.inEdge = 2
v4.data = 4

let v4E7 = EdgeNode()
v4E7.adjex = 7
v4E7.weight = 4
let v4E6 = EdgeNode()
v4E6.adjex = 6
v4E6.weight = 9

v4.firstEdge = v4E7
v4E7.next = v4E6

//V5
let v5 = VertexNode()
v5.inEdge = 1
v5.data = 5

let v5E7 = EdgeNode()
v5E7.adjex = 7
v5E7.weight = 6

v5.firstEdge = v5E7

//V6
let v6 = VertexNode()
v6.inEdge = 1
v6.data = 6

let v6E9 = EdgeNode()
v6E9.adjex = 9
v6E9.weight = 2

v6.firstEdge = v6E9

//V7
let v7 = VertexNode()
v7.inEdge = 2
v7.data = 7

let v7E8 = EdgeNode()
v7E8.adjex = 8
v7E8.weight = 5

v7.firstEdge = v7E8

//V8
let v8 = VertexNode()
v8.inEdge = 1
v8.data = 8

let v8E9 = EdgeNode()
v8E9.adjex = 9
v8E9.weight = 3

v8.firstEdge = v8E9

//V9
let v9 = VertexNode()
v9.inEdge = 2
v9.data = 9

let graphiAdjList = GraphAdjList()

graphiAdjList.adjList.append(v0)
graphiAdjList.adjList.append(v1)
graphiAdjList.adjList.append(v2)
graphiAdjList.adjList.append(v3)
graphiAdjList.adjList.append(v4)
graphiAdjList.adjList.append(v5)
graphiAdjList.adjList.append(v6)
graphiAdjList.adjList.append(v7)
graphiAdjList.adjList.append(v8)
graphiAdjList.adjList.append(v9)

//etv(earliest time of vertex) => 頂點V的最早發(fā)生時間
//ltv(latest time of vertex) => 頂點V的最遲發(fā)生時間
//ete(earliest time of edge) => 弧a的最早發(fā)生時間
//lte(latest time of edge) => 弧a的最遲發(fā)生時間

var etv: [Int] = Array(repeating: 0, count: graphiAdjList.numVertexes)
var ltv: [Int] = []
var stack2: [Int] = []
var top2 = 0

func TopologicalSort(gl: GraphAdjList) {
    var count = 0, top = 0, k = 0, getTop = 0
    var stack: [Int] = []
    //將有向圖所有入度為0的頂點入棧
    for i in 0..<gl.numVertexes {
        if gl.adjList[i].inEdge == 0 {
            stack.append(i)
            top += 1
        }
    }
    //開始算拓撲序列
    while top != 0 {
        getTop = stack.removeLast()
        top -= 1
        count += 1
        /////////////////////
        stack2.append(getTop)  //添加入度為0的頂點
        top2 += 1
        ////////////////////
        var edgeNode = gl.adjList[getTop].firstEdge
        while edgeNode != nil {
            k = (edgeNode?.adjex)!
            gl.adjList[k].inEdge -= 1
            if gl.adjList[k].inEdge == 0 {
                stack.append(k)
                top += 1
            }
            /////////////////////////////////////////////
            if etv[getTop]+(edgeNode?.weight)! > etv[k] {   //頂點的最早發(fā)生時間，即到達這個頂點之前最大的花費時間
                etv[k] = etv[getTop]+(edgeNode?.weight)!
            }
            /////////////////////////////////////////////
            edgeNode = edgeNode?.next
        }
    }
    
    if count < gl.numVertexes {
        print("Error")
    } else {
        print("OK")
    }
}

func CriticalPath(gl: GraphAdjList) {
    var getTop = 0, k = 0
    var ete = 0, lte = 0
    TopologicalSort(gl: gl)  //求拓撲序列片效，計算數(shù)組etv和stack2
    //   etv: [0, 3, 4, 12, 15, 11, 24, 19, 24, 27]
    //stack2: [v0, v1, v2, v3, v4, v5, v6, v7, v8, v9]
    for _ in 0..<gl.numVertexes {
        ltv.append(etv[gl.numVertexes-1])  //初始化ltv為27
    }
    while top2 != 0 {
        getTop = stack2.removeLast()
        top2 -= 1
        var edgeNode = gl.adjList[getTop].firstEdge
        while edgeNode != nil {
            k = (edgeNode?.adjex)!
            if ltv[k]-(edgeNode?.weight)! < ltv[getTop] {
                ltv[getTop] = ltv[k]-(edgeNode?.weight)!  //取最小值红伦，才不會影響該頂點到達其他頂點的時間，也就是最遲發(fā)生的時間
            }
            edgeNode = edgeNode?.next
        }
    }
    for j in 0..<gl.numVertexes {
        var edgeNode = gl.adjList[j].firstEdge
        while edgeNode != nil {
            k = (edgeNode?.adjex)!
            ete = etv[j]
            lte = ltv[k]-(edgeNode?.weight)!
            if ete == lte {
                print("<\(gl.adjList[j].data), \(gl.adjList[k].data) length: \((edgeNode?.weight)!)>")
            }
            edgeNode = edgeNode?.next
        }
    }
}

輸出結果：
<0, 2 length: 4>
<2, 3 length: 8>
<3, 4 length: 3>
<4, 7 length: 4>
<7, 8 length: 5>
<8, 9 length: 3>

• 關鍵點：
  1.etv的計算：比如計算v9點最早開始的時間淀衣，那么需要計算終點是v9的所有點的權值昙读，取最大的權值，是因為膨桥，在這個點開始蛮浑，v9之前的所有活動都剛剛結束，也就是說保證v9之前所有活動完成之后才是v9最早開始的時間只嚣。

  
  
  etv計算公式.png

2.ltv的計算：由etv可以知道終點的最早開始時間沮稚，那么所有點以這個為初始值，因為最遲開始的時間不可能大于終點最早的開始時間册舞。那么蕴掏，ltv的計算從終點開始，往回推环础。比如說要計算v8最遲開始的時間囚似，因為v8需要3天時間工作，那么在保證v8工作完成時不影響v9的工作线得，那么v8最遲開始的工作時間就是v9最早工作時間減去v8需要的時間饶唤。比如說v4，經(jīng)過v4會到達多個頂點贯钩，需要保證不影響所達到的多個的工作時間募狂，那么v4開始的時間就是v4所經(jīng)過的過個頂點最早的開始時間分別減去v4所需要的時間办素，取最小的開始時間，才會不影響之后所有的頂點的最早開始時間祸穷。

ltv計算公式.png

3.ete本來是表示活動 <vk性穿，vj>的最早開工時間，是針對弧來說
的雷滚。但只有此弧的弧尾頂點vk的事件發(fā)生了需曾，它才可以開始，因此 ete=etv[k]祈远；lte 表示的是活動<vk呆万，vj>的最晚開工時間，但此活動再晚也不能等 vj事件發(fā)生才開始车份，而必須要在vj事件之前發(fā)生谋减，所以 lte=ltv[j]-len<vk，vj>扫沼。

總結：

寫這個數(shù)據(jù)結果出爹，斷斷續(xù)續(xù)奮戰(zhàn)了幾個星期，總算一點一點的把它啃完缎除。敲代碼的基礎很重要严就，就像蓋房子一樣，基礎不牢固伴找，建不起高樓大廈盈蛮。后面會繼續(xù)推出，算法技矮，設計模式抖誉，編譯原理，操作系統(tǒng)等等一些列的學習筆記衰倦。這世界很大袒炉，需要保持一點好奇心??。最后樊零，獻上Demo我磁。