Swift之图的遍历

图

图就是由一些小圆点（称为顶点）和连接这些小圆点的直线（称为边）组成的。下图是一个常见的图。

图.png

如何存储一个图呢。我们可以用一个二维数组表示，如下图所示，二维数组中第i行到第j列表示的就是顶点j到j是否有边。1表示有边，∞表示没有边，0表示自己。这种存储图的方法称为图的临接矩阵存储法。这个二维数组是沿主对角线对称的，因为是这个图是无向图，所谓无向图指的就是图的边没有方向。

图的邻接矩阵存储法.png

图的深度优先遍历

深度优先遍历是沿着图的某一条分支遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。图的深度优先遍历结果如下图。顶点右上角的代表该顶点被遍历的顺序。

深度搜索遍历.png

<pre>
/*******************图的深度优先遍历*************************/
//Int.max表示没有边
let map = [[0,1,1,Int.max,1],
[1,0,Int.max,1,Int.max],
[1,Int.max,0,Int.max,1],
[Int.max,1,Int.max,0,Int.max],
[1,Int.max,1,Int.max,0]]
var sum = 0
var book:[Int] = Array.init(repeatElement(0, count: map.count))
book[0] = 1

func mapdfs(step:Int) {

debugPrint(step)
sum+=1
if sum == map.count {
    return
}

for index in map.indices {
    
    if (book[index] == 0) && (map[step][index] == 1) {
        book[index] = 1
        
        mapdfs(step:index)
    }
}

}

mapdfs(step: 0) //0,1,3,2,4
/*******************图的深度优先遍历*************************/
</pre>

图的广度优先优先遍历

广度优先遍历：首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点，再访问他们相邻的未被访问过的顶点，直到所有的顶点都被访问过，遍历结束。图的广度优先遍历结果如下图。

广度搜索遍历.png

<pre>
/*******************图的广度优先遍历*************************/
var book2:[Int] = Array.init(repeatElement(0, count: map.count))

func mapBfs(map:[Array<Int>]) {

//创建一个链表
var queue = Array.init(repeatElement(0, count: 100))
var head = 0
var tail = 0

queue[tail] = 0
tail+=1
book2[head] = 1

while (head < tail) {
    
    for index in map.indices {
        
        if (book2[index] == 0) && (map[head][index] == 1) {
            book2[index] = 1
            
            queue[tail] = index
            tail+=1
        }
    }
    if tail > (map.count - 1) {
        break
    }
    
    head+=1
}
for index in 0..<map.count {
    debugPrint(queue[index])
}

}
mapBfs(map: map) //0,1,2,4,3
/*******************图的广度优先遍历*************************/