深度优先遍历(dfs)

边用二维数组表示

• 0表示顶点到自身的路径
• 1表示顶点到顶点之间存在路径
• ∞表示两个顶点之间不存在路径

代码中图的结构

切片 1.png

Code

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

var count = 0

/// 深度优先遍历
///
/// - Parameters:
///   - v: 节点数组
///   - e: 边数组
///   - start: 开始点
func dfs(v:[Node],e:[[Int]],start:Int) {
    print(v[start].value)
    v[start].visited = true
    count = count + 1
    if count == v.count {
        return
    }
    //遍历对应的数组
    var tmpArray = e[v[start].value]
    
    for i in 0..<tmpArray.count {
        let ttt = tmpArray[i]
        if ttt == 1,v[i].visited == false {
            dfs(v: v, e: e, start: 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;
        dfs(v: array, e: e, start: 0)
    }
}

Console

0
1
4
2
3

时间复杂度分析

因为要遍历完整个二维数组，所以时间复杂度为O(n²)，n为图中的顶点个数