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))
}
上一篇下一篇

猜你喜欢

热点阅读