图的深度优先遍历(DFS)

2017-03-05  本文已影响137人  czins

从图中的某个顶点v出发,访问此顶点,然后从v的未被访问的领接点出发深度优先遍历图,直至图中所有和v有路径相同的顶点都被访问到。

图片.png
/**
     * 查找某个顶点的第一个邻接点
     */
    fun getFirstNeighbor(index: Int): Int {
        matrix.getOrNull(index)?.forEachIndexed { index, i ->
            if (i in 1..(MAX_WEIGHT - 1)) {
                return index
            }
        }
        return -1
    }

    /**
     * 查找某个顶点v相对于index的下一个邻接点
     */
    fun getNextNeighbor(v: Int, index: Int): Int {
        matrix.getOrNull(v)?.slice(index + 1..size - 1)?.forEachIndexed { i, d ->
            if (d in 1..(MAX_WEIGHT - 1)) {
                return index + i + 1
            }
        }
        return -1
    }

    /**
     * 深度优先遍历
     */
    fun depthFirstSearch() {
        isVisited = BooleanArray(size)
        (0..size - 1).forEach {
            depthFirstSearch(it)
        }
    }

private fun depthFirstSearch(index: Int) {
        if (!isVisited[index]) {
            isVisited[index] = true
            System.out.println("访问到了" + index + "顶点")
        }
        var i = getFirstNeighbor(index)
        while (i != -1) {
            if (!isVisited[i]) {
                depthFirstSearch(i)
            }
            i = getNextNeighbor(index, i)
        }
    }
上一篇 下一篇

猜你喜欢

热点阅读