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);
}
}
网友评论