(带权有向图)邻接矩阵表示图代码实现

package dn1124;
/**
* @author sj E-mail: [email protected]
* @version 创建时间: 2017-11-26 下午10:16:38
* 类说明: (带权有向图)邻接矩阵表示图代码实现
*/

public class Graph {
    public static final int MAX_WEIGHT=-1;//表示无穷大

    private int[] vertices;//顶点
    private int[][] matrix;//图的节点的边
    private int verticeSize;//定点的数量

    public Graph(int verticeSize) {
        super();
        this.verticeSize = verticeSize;
        this.vertices =new int[verticeSize];
        this.matrix = new int[verticeSize][verticeSize];

        for(int i=0;i<verticeSize;i++){
            vertices[i]=i;
        }
    }

(带权有向图)邻接矩阵表示图代码实现

/**
 * 计算v1到v2的权重(路径长度)
 * @param v1 顶点
 * @param v2 顶点
 * @return
 */
public int getWeight(int v1,int v2){
    int weight=matrix[v1][v2];
    return weight==0 ? 0 :( weight==MAX_WEIGHT ? -1 : weight);
}

/**
 * 获取所有顶点
 * @return
 */
public int[] getVertices(){
    return vertices;
}

/**
 * 计算某个顶点的出度
 * @param v
 * @return
 */
public int getOutDegree(int v){
    int count=0;
    for(int i=0;i<matrix[v].length;i++){
        if(matrix[v][i]!=0 && matrix[v][i]!=MAX_WEIGHT){
            count++;
        }
    }
    return count;
}



/**
 * 计算某个顶点的入度
 * @param v
 * @return
 */
public int getIntDegree(int v){
    int count=0;
    for(int i=0;i<matrix[v].length;i++){
        if(matrix[i][v]!=0 && matrix[i][v]!=MAX_WEIGHT){
            count++;
        }
    }
    return count;
}

/**
 * 返回某个顶点的第一个邻接点
 * @return
 */
public int getFirstNeightBor(int v){
    for(int i=0;i<verticeSize;i++){
        if(matrix[v][i]>0 && matrix[v][i] !=MAX_WEIGHT){
            return i;
        }
    }
    return -1;
}

/**
 * 查找接点v的临界点index的下一个邻接点
 * @param v   节点
 * @param index  节点
 * @return
 */
public int getNextNeightBor(int v,int index){
    for(int i=index+1;i<verticeSize;i++){
        if(matrix[v][i]>0 && matrix[v][i] !=MAX_WEIGHT){
            return i;
        }
    }
    return -1;
}

public static void main() {

(带权有向图)邻接矩阵表示图代码实现

       //构建一个图

       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,MAX_WEIGHT};
        graph.matrix[0]=a0;
        graph.matrix[1]=a1;
        graph.matrix[2]=a2;
        graph.matrix[3]=a3;
        graph.matrix[4]=a4;

        System.out.println("v2的入度： "+graph.getIntDegree(2));
        System.out.println("v2的出度： "+graph.getOutDegree(2));
        System.out.println("第一个邻接点： "+graph.getFirstNeightBor(2));
        System.out.println("v2关于v0的下一个邻接点： "+graph.getNextNeightBor(2,0));
    }

 }

单元测试里面：

public class Test {

    @org.junit.Test
    public void methed(){
        Graph.main();
    }

}

运行结果如下：

(带权有向图)邻接矩阵表示图代码实现

相关推荐