从图中的某个顶点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)
}
}
