图
2017-03-04 本文已影响7人
czins
import graph.Graph.Companion.MAX_WEIGHT
class Graph(val size: Int) {
var matrix = arrayOfNulls<IntArray>(size)
companion object {
val MAX_WEIGHT = Int.MAX_VALUE
}
/**
* 获取图的某个顶点的出度
*/
fun getOutDegree(index: Int): Int {
var degree = 0
matrix.getOrNull(index)?.forEach {
if (it != MAX_WEIGHT && it != 0) {
degree++
}
}
return degree
}
/**
* 获取图的某个顶点的入度
*/
fun getInDegree(index: Int): Int {
var degree = 0
matrix?.forEach {
it?.getOrNull(index)?.let {
if (it != MAX_WEIGHT && it != 0) {
degree++
}
}
}
return degree
}
fun main(args: Array<String>) {
/**
* 图的矩阵
* 横向代表出度,纵向代表入度
* v0 v1 v2 v3 v4
* v0 0 ∞ ∞ ∞ 6
* v1 9 0 3 ∞ ∞
* v2 2 ∞ 0 5 ∞
* v3 ∞ ∞ ∞ 0 1
* v4 ∞ ∞ ∞ ∞ 0
*/
var graph = Graph(5)
graph.matrix[0] = intArrayOf(0, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 6)
graph.matrix[1] = intArrayOf(9, 0, 3, MAX_WEIGHT, MAX_WEIGHT)
graph.matrix[2] = intArrayOf(2, MAX_WEIGHT, 0, 5, MAX_WEIGHT)
graph.matrix[3] = intArrayOf(MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0, 1)
graph.matrix[4] = intArrayOf(MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0)
println("图顶点1的出度:" + graph.getOutDegree(1))
println("图顶点1的入度:" + graph.getInDegree(1))
}