广度优先遍历(bfs)

• 从图中某个顶点V0出发，并访问此顶点；
• 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
• 重复步骤2，直到全部顶点都被访问为止

代码中图的结构

code

/// 节点
class Node {
    var visited:Bool = false
    var value:Int = 0
}

/// 广度优先遍历
///
/// - Parameters:
///   - v: 节点数组
///   - e: 边数组
///   - start: 开始点
func bfs(v:[Node],e:[[Int]],start:Int) {
    var queue:Array = [Node]()
    v[start].visited = true
    queue.append(v[start])
    while queue.count != 0 {
        let headNode = queue[0]
        print(headNode.value)
        queue.remove(at: 0)
        
        //遍历对应的数组
        var tmpArray = e[headNode.value]
        for i in 0..<tmpArray.count {
            let ttt = tmpArray[I]
            if ttt == 1,v[i].visited == false {
                v[i].visited = true
                queue.append(v[I])
            }
        }
    }
}

class ViewController: UIViewController {
    
    override func viewDidLoad() {
        super.viewDidLoad()
        // Do any additional setup after loading the view, typically from a nib.
        let n = 5
        //节点
        var array:Array = [Node]()
        for i in 0..<n {
            let node = Node()
            node.value = I
            array.append(node)
        }
        //边 用二维矩阵表示
        var e = [[Int]]()
        for i in 0..<n {
            var row = [Int]()
            for j in 0..<n {
                if i == j {
                    row.append(0)
                } else {
                    row.append(10000)
                }
            }
            e.append(row)
        }
        e[0][1] = 1;e[0][2] = 1;e[0][3] = 1;
        e[1][0] = 1;e[1][4] = 1;
        e[2][0] = 1;e[2][4] = 1;
        e[3][0] = 1;
        e[4][1] = 1;e[4][2] = 1;
        bfs(v: array, e: e, start: 0)
    }
}

console

0
1
2
3
4

时间复杂度

O(n²)，n代表顶点的个数