美文网首页
数据结构图-JAVA实现

数据结构图-JAVA实现

作者: 浩均 | 来源:发表于2017-11-09 10:57 被阅读0次

    package com.sunny.graph.matrix;

    public class Graph {
    private int vertexSize;//顶点数量
    private int [] vertexs;//顶点数组
    private int[][] matrix;//邻接矩阵
    private final static int MAX_WEIGHT = 1000;//权值即图的无穷大。这里只是做了最大的定义

    public Graph(int vertexSize) {
        super();
        this.vertexSize = vertexSize;
        matrix = new int[vertexSize][vertexSize];
        vertexs = new int[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            vertexs[i] = i;
        }
    }
    
    public int[] getVertexs() {
        return vertexs;
    }
    
    public void setVertexs(int[] vertexs) {
        this.vertexs = vertexs;
    }
    
    /**
     * 计算顶点的出度  横排是出度,竖列是入度
     * */
    public int getOutDegree(int index){
        int degree = 0;
        for (int j = 0; j < vertexSize; j++) {
            int weight = matrix[index][j];
            if (weight != 0 && weight !=MAX_WEIGHT){
                degree++;
            }
        }
        return degree;
    }
    
    /**
     * 计算顶点的入度  横排是出度,竖列是入度
     * */
    public int getIntDegree(int index){
        
        int degree = 0;
        for (int j = 0; j < vertexSize; j++) {
            int weight = matrix[j][index];
            if (weight != 0 && weight !=MAX_WEIGHT){
                degree++;
            }
        }
        return degree;
    }
    
    /**
     * 获取两个顶点之间的权值
     * @param args
     * @return 
     */
    public int getWeight(int v1 , int v2) {
        int weight = matrix[v1][v2];
        return weight == 0 ? 0:(weight == MAX_WEIGHT?-1:weight);
    }
    
    //获取V1的邻接点 V1的出度点 V1的入度点
    //V2-V4的最短路径 拓普排序
    
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        int[] a0 = new int[]{0,MAX_WEIGHT ,MAX_WEIGHT, MAX_WEIGHT, 6};
        int[] a1 = new int[]{9,0 ,3, MAX_WEIGHT, MAX_WEIGHT};
        int[] a2 = new int[]{2,MAX_WEIGHT ,0, 5, MAX_WEIGHT};
        int[] a3 = new int[]{MAX_WEIGHT,MAX_WEIGHT ,MAX_WEIGHT, 0, 1};
        int[] a4 = new int[]{MAX_WEIGHT,MAX_WEIGHT ,MAX_WEIGHT, MAX_WEIGHT, 0};
        graph.matrix[0] = a0;
        graph.matrix[1] = a1;
        graph.matrix[2] = a2;
        graph.matrix[3] = a3;
        graph.matrix[4] = a4;
    

    // int degree = graph.getOutDegree(4);
    // System.out.println("V" + 4 + "的出度是" + degree);
    //
    // int degree2 = graph.getIntDegree(0);
    // System.out.println("V" + 0 + "的入度是" + degree2);
    int weight = graph.getWeight(0, 0);
    System.out.println("V0 - V4" + "的权值是" + weight);
    }

    }

    相关文章

      网友评论

          本文标题:数据结构图-JAVA实现

          本文链接:https://www.haomeiwen.com/subject/ocdpmxtx.html