该类包括
- 基础方法
- 邻接矩阵
- 邻接表
- 深度优先遍历
- 广度优先遍历
- 最小生成树
- 最短路径
- 拓扑排序
package com.naah.s4_Graph;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
/**
*
* ClassNameCh 图
* ClassNameEn Graph
* Description 数据结构图
* Company
* @author Naah
* @date 2017年8月13日 下午11:18:46
* @param
*/
public class Graph> {
// 顶点数组
private T[] vertexs;
// 邻接表元素数组
private VertexNeighborNode[] neighborArray;
// 邻接矩阵
private int[][] matrix;
// 度数组
private Edge[] edges;
// 泛型对象的类文件
private Class Class;
// 顶点数量
private int size;
// 常亮：未连接
public static final int NO_LINK = -1;
/**
* 构造方法
* @param Class 类对象
* @param vertexs 顶点可选数组
*/
public Graph(Class Class, T... vertexs) {
super();
this.vertexs = vertexs;
this.size = vertexs.length;
this.Class = Class;
}
/**
* 构造方法
* @param vertexs 可选数组
*/
public Graph(T... vertexs) {
super();
this.vertexs = vertexs;
this.size = vertexs.length;
}
/**
* 基础添加方法
* @param vertex 顶点
*/
private void basicAdd(T vertex) {
// 创建新顶点数组
T[] newVertexs = (T[]) Array.newInstance(Class, vertexs.length + 1);
// 将原顶点数组复制到新顶点数组
System.arraycopy(vertexs, 0, newVertexs, 0, vertexs.length);
// 将新顶点添加到新顶点数组
newVertexs[newVertexs.length - 1] = vertex;
// 将新顶点数组设置为原顶点数组
vertexs = newVertexs;
// 长度增加
size++;
}
/**
* 添加顶点方法（无邻接矩阵）
* @param vertex 顶点
* @return 顶点的下标
* @throws Exception 有邻接矩阵
*/
public int add(T vertex) throws Exception {
// 判断当前对象是否含有邻接矩阵、
// 没有则进入
if (matrix == null) {
// 添加顶点
basicAdd(vertex);
// 返回新顶点下标
return vertexs.length - 1;
} else {
// 有邻接矩阵则抛出异常
throw new Exception("当前存在邻接矩阵！请使用重载方法！");
}
}
/**
* 添加节点（有邻接矩阵）
* @param vertex 顶点
* @param inWeight 入度(不包含自己)
* @param outWeight 出度(不包含自己)
* @return 顶点下标
* @throws Exception 邻接数组长度不对
* @throws Exception 不存在邻接数组
*/
public int add(T vertex, int[] inWeight, int[] outWeight) throws Exception {
// 判断是否有邻接矩阵，如果没有则抛出异常
if (matrix == null) {
throw new Exception("当前不存在邻接矩阵！请使用重载方法！或建立邻接矩阵！");
}
// 判断邻接数组长度是否与顶点数组长度相同
if (inWeight.length != vertexs.length
|| outWeight.length != vertexs.length) {
throw new Exception("邻接数组长度不对");
}
// 添加元素
basicAdd(vertex);
// 创建新邻接矩阵
int[][] newMatrix = new int[vertexs.length][vertexs.length];
// 遍历原邻接矩阵
for (int i = 0; i < matrix.length; i++) {
// 将原邻接矩阵数组元素复制到新邻接矩阵数组中
System.arraycopy(matrix[i], 0, newMatrix[i], 0, matrix[i].length);
// 将新顶点的出度添加到邻接矩阵中
newMatrix[i][vertexs.length - 1] = inWeight[i];
// 将新节点的入度添加到邻接矩阵中
newMatrix[vertexs.length - 1][i] = outWeight[i];
}
// 顶点与自己的度为0
newMatrix[vertexs.length - 1][vertexs.length - 1] = 0;
// 将新的邻接矩阵设置为邻接矩阵
matrix = newMatrix;
// 返回行顶点的下标
return vertexs.length - 1;
}
/**
* 得到出度数量
* @param vertex 顶点
* @return 出度数量
* @throws Exception 未定义邻接矩阵
*/
public int getOutSize(T vertex) throws Exception {
// 如果邻接矩阵为空
if (matrix == null) {
// 抛出异常
throw new Exception("未找到邻接矩阵");
}
// 得到顶点下标
int position = getIndex(vertex);
// 判断是否找到
if (position != -1) {
// 出度数量
int size = 0;
// 遍历顶点的出度数组
for (int i = 0; i < matrix[position].length; i++) {
// 不为自己 并且 有链接
if (matrix[position][i] > 0 && matrix[position][i] != NO_LINK) {
// 出度数量增加
size++;
}
}
} else {
throw new Exception("未找到该顶点");
}
// 返回出度数量
return size;
}
/**
* 得到入度数量
* @param vertex 顶点
* @return 入度数量
* @throws Exception 未找到邻接矩阵
*/
public int getInSize(T vertex) throws Exception {
// 如果邻接矩阵为空
if (matrix == null) {
// 抛出异常
throw new Exception("未找到邻接矩阵");
}
// 得到顶点下标
int position = getIndex(vertex);
// 判断是否找到
if (position != -1) {
// 出度数量
int size = 0;
// 遍历入度数组
for (int i = 0; i < matrix.length; i++) {
// 不为自己 并且 有链接
if (matrix[i][position] > 0 && matrix[i][position] != NO_LINK) {
// 出度数量增加
size++;
}
}
} else {
throw new Exception("未找到该节点");
}
// 返回出度数量
return size;
}
/**
* 得到下标位置
* @param vertex 顶点
* @return下标位置
*/
public int getIndex(T vertex) {
// 遍历顶点数组
for (int i = 0; i < vertexs.length; i++) {
// 顶点不为空 并且 相同
if (vertexs[i] != null && vertexs[i].equals(vertex)) {
// 找到则返回下标
return i;
}
}
// 找不到返回-1
return -1;
}
/**
* 得到邻接矩阵
* @return
*/
public int[][] getMatrix() {
return matrix;
}
/**
* 设置邻接矩阵
* @param matrix 邻接矩阵
* @throws Exception 数组长度不对
*/
public void setMatrix(int[][] matrix) throws Exception {
if (matrix.length != this.vertexs.length) {
throw new Exception("二维数组长度不对");
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i].length != this.vertexs.length) {
throw new Exception("二维数组长度不对");
}
}
this.matrix = matrix;
}
/**
* 得到顶点数量
* @return 顶点数量
*/
public int getSize() {
return size;
}
/**
* 设置顶点数组
* @param vertexs 顶点数组
*/
public void setVertexs(T[] vertexs) {
this.vertexs = vertexs;
this.size = vertexs.length;
}
/**
* 得到顶点数组
* @return 顶点数组
*/
public T[] getVertexs() {
return vertexs;
}
/**
* 得到度数组
* @return
*/
public Edge[] getEdges() {
return edges;
}
/**
* 深度优先遍历方法（递归）
*/
public void depthFirst() {
// 建立记录数组
boolean[] isVisited = new boolean[size];
// 顶点数组循环
for (int i = 0; i < vertexs.length; i++) {
// 全部遍历标记，为节省资源
boolean isAllTrue = true;
// 遍历记录数组是否已全部记录
for (int j = 0; j < isVisited.length; j++) {
// 如果有一个没记录
if (isVisited[j] == false) {
// 则将全部遍历标记设置为false
isAllTrue = false;
// 跳出该循环
break;
}
}
// 如果已全部遍历
if (isAllTrue) {
// 跳出循环，不再继续
break;
}
// 判断当前顶点是否已遍历，如果没有则进行遍历
if (!isVisited[i]) {
// 遍历该顶点
depthFirst(isVisited, i);
}
}
}
/**
* 深度优先遍历实现方法（递归）
* @param isVisited 遍历记录数组
* @param i 遍历的起点
*/
private void depthFirst(boolean[] isVisited, int i) {
// 将当前顶点设置为已遍历
isVisited[i] = true;
// 找到该顶点的第一个出度顶点下标
int weight = getFirstNeighbor(i);
// 深度遍历出度顶点，直到没有出度顶点
while (weight != -1) {
// 判断出度顶点是否已遍历过，如果没遍历过则进行遍历
if (!isVisited[weight]) {
// 输出该出度顶点的信息
System.out.println("第" + weight + "个顶点被访问：" + vertexs[weight]);
// 深度遍历该出度顶点
depthFirst(isVisited, weight);
}
// 如果没有出度顶点，则查找该顶点下一个出度顶点
weight = getNextNeighbor(i, weight);
}
}
/**
* 得到该顶点的第一个出度顶点下标
* @param i 顶点数组下标
* @return 第一个出度顶点下标
*/
private int getFirstNeighbor(int i) {
// 循环矩阵中顶点的出度数组
for (int j = 0; j < size; j++) {
// 如果该出度不为0，并且相连
if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK) {
// 返回出度顶点下标
return j;
}
}
// 返回未连接
return NO_LINK;
}
/**
* 得到该顶点从某位置后的第一个出度顶点下标
* @param i 顶点数组下标
* @param weight 位置
* @return 出度顶点下标
*/
private int getNextNeighbor(int i, int weight) {
// 从某位置开始循环矩阵中顶点的出度数组
for (int j = weight + 1; j < size; j++) {
// 如果该出度不为0，并且相连
if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK) {
// 返回出度顶点下标
return j;
}
}
// 返回未连接
return NO_LINK;
}
/**
* 广度优先遍历方法（递归）
*/
public void bredthFirst() {
// 建立记录数组
boolean[] isVisited = new boolean[size];
// 创建队列
LinkedList queue = new LinkedList();
// 广度优先遍历方法实现，从第一个开始
bredthFirst(isVisited, queue, 0);
}
/**
* 广度优先算法遍历方法实现
* @param isVisited 记录数组
* @param queue 队列
* @param i 开始顶点
*/
private void bredthFirst(boolean[] isVisited, LinkedList queue,
int i) {
// 将当前顶点设置为已遍历
isVisited[i] = true;
System.out.println("第" + i + "个顶点被访问了：" + vertexs[i]);
// 循环将该顶点的出度顶点下标添加到队列中
for (int j = 0; j < size; j++) {
// 出度顶点判断，不为自己 并且 相连 并且没有访问过
if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK && !isVisited[j]) {
// 添加到队列
queue.offer(j);
}
}
// 如果队列不为空则循环
while (!queue.isEmpty()) {
// 将顶点下标从队首移出
int weight = queue.poll();
// 如果该顶点没访问过
if (!isVisited[weight]) {
// 递归广度遍历该方法
bredthFirst(isVisited, queue, weight);
}
}
}
/**
* 最小生成树方法-普里姆算法
*
*/
public void prim() {
// 创建最小权值数组
int[] least = new int[size];
// 上一个顶点下标数组
int[] lastIndex = new int[size];
// 最小权值和
int sum = 0;
// 初始化最小权值数组
for (int i = 0; i < least.length; i++) {
least[i] = matrix[0][i];
}
// 循环查找最小生成树
for (int i = 1; i < least.length; i++) {
// 将最小权值设置为int最大值
int min = Integer.MAX_VALUE;
// 将最小权值下标设置为0
int minIndex = 0;
// 循环查找最小权值数组中的最小值
for (int j = 1; j < least.length; j++) {
// 大于0的最小权值
if (least[j] > 0 && least[j] < min) {
// 设置为最小值
min = least[j];
// 将当前下标设置为最小权值下标
minIndex = j;
}
}
// 输出已找到的最小顶点
System.out.println(
lastIndex[minIndex] + "顶点---" + minIndex + "顶点:" + min);
// 将已找到的最小权值点设置为0，标记为已找到
least[minIndex] = 0;
// 将最小权值累加到最小权值和中
sum += min;
// 将上一个顶点的所有出度权值添加到最小权值数组中
for (int j = 1; j < least.length; j++) {
// 没遍历的顶点 并且 上一个顶点所到该顶点的权值 小于 最小权值数组中到该顶点的权值时 进入
// 最小权值数组中无法到达的顶点 并且上一个顶点能到达该顶点时 进入
if ((least[j] > 0 && matrix[minIndex][j] != NO_LINK
&& matrix[minIndex][j] < least[j])
|| (least[j] == NO_LINK
&& matrix[minIndex][j] != NO_LINK)) {
// 将上一个顶点到该顶点的出度权值添加到最小权值数组中
least[j] = matrix[minIndex][j];
// 将上一个顶点设置为该顶点的入度顶点
lastIndex[j] = minIndex;
}
}
}
// 输出最小权值和
System.out.println(sum);
}
/**
* 最小生成树方法-克鲁斯卡尔算法
*/
public void kruskal() {
// 创建查找数组
// 该数组下标为顶点下边
// 该数组值为顶点出度顶点下标
int[] parent = new int[size];
// 最小权值和
int sum = 0;
// 构建度数组
createEdge();
// 循环出度数组
for (Edge edge : edges) {
// 从查找数组中寻找该出度的头所到达的顶点下标
int n = find(parent, edge.begin);
// 从查找数组中寻找该出度的尾所到达的顶点下标
int m = find(parent, edge.end);
// 如果头尾顶点下标不相等，进入
// 如果头尾顶点下标相对，则代表该度为多余度
if (n != m) {
// 输出该度信息
System.out.println(
edge.begin + "顶点---" + edge.end + "顶点：" + edge.weight);
// 将查询数组中头下标的值设置为尾下标
parent[n] = m;
// 累计权值
sum += edge.weight;
}
}
// 输出权值
System.out.println(sum);
}
/**
* 查找数组中该顶点能到达的最后位置
* @param parent 查找数组
* @param i 顶点下标
* @return 最后位置
*/
private int find(int[] parent, int i) {
// 如果该下标位置有出度则循环
while (parent[i] > 0) {
// 将出度下标设置为下一次查找的下标
i = parent[i];
}
// 返回最后位置
return i;
}
/**
* 构建度数组
*/
public void createEdge() {
// 创建度的链表，不确定度的数量，所以使用链表
List edgeList = new LinkedList();
// 从第一个顶点开始构建度的链表
createEdge(edgeList, 0);
// 创建度的数组
this.edges = new Edge[edgeList.size()];
// 数组赋值标记
int i = 0;
// 遍历链表，添加到数组
for (Edge edge : edgeList) {
// 将链表值添加到数组
this.edges[i] = edge;
// 标记自增
i++;
}
// 通过Edge类实现Comparable接口进行排序
Arrays.sort(this.edges);
}
/**
* 构建度数组
*
* 此方法思路与广度优先相同
* 但是没有采用上面的递归广度优先思路
* 而是使用迭代完成
* @param edges 度的链表
* @param i 开始节点
*/
private void createEdge(List edges, int i) {
// 创建度的队列
LinkedList queue = new LinkedList();
// 将顶点下标添加到队列中
queue.offer(i);
// 队列不为空则循环
while (!queue.isEmpty()) {
// 取出队首顶点下标
int n = queue.poll();
// 取得顶点的第一个邻接点
int m = getFirstNeighbor(n);
// 当邻接点连接时循环
while (m != NO_LINK) {
// 是否包含度标记
boolean isHave = false;
// 遍历度链表
for (Edge e : edges) {
// 如果两节点相等
if (e.equals(n, m, matrix[n][m])) {
// 将标记设置为真
isHave = true;
break;
}
}
// 当没有该度时
if (!isHave) {
// 向度链表中添加该度
edges.add(new Edge(n, m, matrix[n][m]));
// 将邻接点下标添加到队尾
queue.offer(m);
}
// 得到m邻接点后的一个邻接点
m = getNextNeighbor(n, m);
}
}
}
/**
* 最短路径-迪杰特斯拉算法
* @param v 下标
* @return 最小路径数组
* @throws Exception
*/
public int[] dijstra(int v) throws Exception {
// 如果链接矩阵为空，则
if (matrix == null) {
// 抛出异常
throw new Exception("未找到邻接矩阵");
}
// 创建最短路径数组
int[] least = new int[size];
// 创建记录数组
boolean[] getLeastWeight = new boolean[size];
int k = 0;
// 初始化最短路径数组
for (int i = 0; i < least.length; i++) {
least[i] = matrix[v][i];
}
// 将当前下标记录
getLeastWeight[v] = true;
// 循环找出最短路径
for (int i = 0; i < least.length; i++) {
// 将最小值赋值
int min = Integer.MAX_VALUE;
// 循环查找最小的权值，并暂时保存下标
for (int j = 0; j < least.length; j++) {
if (!getLeastWeight[j] && least[j] > 0 && least[j] < min) {
min = least[j];
k = j;
}
}
// 将该顶点记录
getLeastWeight[k] = true;
// 循环最小权值的顶点，如果有比上一个顶点到那个顶点权值更小，则将更小的权值赋值
for (int j = 0; j < getLeastWeight.length; j++) {
if (!getLeastWeight[j] && ((matrix[k][j] + min < least[j]
&& matrix[k][j] > 0)
|| (least[j] == NO_LINK && matrix[k][j] != NO_LINK))) {
least[j] = matrix[k][j] + min;
}
}
}
// 返回最小路径数组
return least;
}
/**
* 通过顶点的入度数量来构建邻接表
* @param vertexsInEdgeNum 顶点的入度数量数组
* @return 邻接表
* @throws Exception 未找到顶点数组
*/
public VertexNeighborNode[] getNeighborArray(int... vertexsInEdgeNum)
throws Exception {
// 如果未找到顶点数组，抛出异常
if (vertexs == null) {
throw new Exception("未找到顶点数组!");
}
// 创建邻接表
neighborArray = new VertexNeighborNode[size];
// 通过传入的顶点入度数量数组构建邻接表
for (int i = 0; i < size; i++) {
// 通过顶点入度数量创建邻接表元素
neighborArray[i] = new VertexNeighborNode(vertexsInEdgeNum[i]);
}
// 返回邻接表
return neighborArray;
}
/**
* 设置邻接表元素的度
* @param neighborIndex 邻接表数组元素下标
* @param array 邻接表度元素数组
* @throws Exception 未找到邻接数组
*/
public void setNeighborEdgeNode(int neighborIndex, EdgeNode... array)
throws Exception {
// 如果邻接数组为空，抛出异常
if (neighborArray == null) {
throw new Exception("未找到邻接数组!");
}
// 如果度元素数组有元素，则
if (array.length > 0) {
// 将度元素数组第一个设置为邻接表元素的第一个度
neighborArray[neighborIndex].setFirstEdge(array[0]);
}
// 如果度元素数组长度超过1，则
if (array.length > 1) {
// 通过循环，将度元素数组剩余度链接到度元素链表中
for (int i = 1; i < array.length; i++) {
// 获取邻接表数组中的当前元素的第一个度
EdgeNode en = neighborArray[neighborIndex].getFirstEdge();
// 将当前度的下一个引用为第一个度
array[i].setNext(en);
// 将当前元素的第一个度设置为当前度
neighborArray[neighborIndex].setFirstEdge(array[i]);
}
}
}
/**
* 拓扑排序方法
* @throws Exception
*/
public void Topologic() throws Exception {
// 创建栈，用于添加入度为0的邻接元素下标
Stack zero = new Stack();
// 创建拓扑排序数量
int count = 0;
// 循环邻接表元素数组
for (int i = 0; i < size; i++) {
// 如果当前元素的入度数量为0
if (neighborArray[i].getIn() == 0) {
// 将当前元素的下标压入栈中
zero.push(i);
}
}
// 如果栈不为空，遍历栈
while (!zero.isEmpty()) {
// 弹出栈顶的下标
int zeroIndex = zero.pop();
// 输出该顶点的下标和值
System.out.println(zeroIndex + ":" + vertexs[zeroIndex]);
// 拓扑数量自增
count++;
// 遍历入度为0的邻接表元素的度元素
for (EdgeNode e = neighborArray[zeroIndex]
.getFirstEdge(); e != null; e = e.getNext()) {
// 取得弧尾顶点的下标（顶点的出度顶点）
int nextIndex = e.getIndex();
// 通过下标取得邻接表数组元素
VertexNeighborNode v = neighborArray[nextIndex];
// 将该元素的入度减1，证明该元素的入度有一个已遍历过
v.setIn(v.getIn() - 1);
// 如果该元素的当前入度为0，则
if (v.getIn() == 0) {
// 将该元素的下标压入栈中
zero.push(nextIndex);
}
}
}
// 如果遍历过的顶点数量不是全部顶点数量
if (count != size) {
// 则代表拓扑失败，有回环
throw new Exception("拓扑失败！有回环");
}
}
}
/**
*
* ClassNameCh 度
* ClassNameEn Edge
* Description 度的数据结构
* Company
* @author Naah
* @date 2017年8月14日 下午10:52:53
*/
class Edge implements Comparable {
// 度的头顶点下标
int begin;
// 度的尾顶点下标
int end;
// 度的权值
int weight;
public Edge() {
super();
}
/**
* 构造函数
* @param begin 头顶点下标
* @param end 尾顶点下标
* @param weight 权值
*/
public Edge(int begin, int end, int weight) {
super();
this.begin = begin;
this.end = end;
this.weight = weight;
}
/**
* 判断相等方法
* @param begin
* @param end
* @param weight
* @return true/false
*/
public boolean equals(int begin, int end, int weight) {
// 首先判断权值相等
if (weight == this.weight) {
// 判断下标是否相同，包括头尾互换
if ((begin == this.begin && end == this.end)
|| (end == this.begin && begin == this.end)) {
// 返回相等
return true;
}
}
// 返回不相等
return false;
}
@Override
public String toString() {
return "Edge [begin=" + begin + ", end=" + end + ", weight=" + weight
+ "]";
}
/**
* 判断大小方法
* 以权值大小判断，为度数组的从小到大排序
*/
@Override
public int compareTo(Edge o) {
if (this.weight > o.weight) {
return 1;
} else if (this.weight < o.weight) {
return -1;
}
return 0;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
边节点类
package com.naah.s4_Graph;
/**
*
* ClassNameCh 边节点
* ClassNameEn EdgeNode
* Description 边节点 ，用于记录该顶点的出度顶点
* Company
* @author Naah
* @date 2017年8月17日 下午9:27:19
*/
public class EdgeNode {
// 出度顶点下标
private int index;
// 下一个出度顶点的引用
private EdgeNode next;
// 权值
private int weight;
public EdgeNode(int index) {
super();
this.index = index;
}
public EdgeNode(int index, int weight) {
super();
this.index = index;
this.weight = weight;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public EdgeNode getNext() {
return next;
}
public void setNext(EdgeNode next) {
this.next = next;
}
@Override
public String toString() {
return "EdgeNode [index=" + index + ", next=" + next + ", weight="
+ weight + "]";
}
}
邻接表元素类
package com.naah.s4_Graph;
/**
*
* ClassNameCh 邻接表元素
* ClassNameEn VertexNeighborNode
* Description 邻接表数组的元素，包括该顶点的第一条边
* Company
* @author Naah
* @date 2017年8月17日 下午9:25:59
* @param
*/
public class VertexNeighborNode {
// 入度数
private int in;
// 边节点
private EdgeNode firstEdge;
public VertexNeighborNode(int in) {
super();
this.in = in;
}
public int getIn() {
return in;
}
public void setIn(int in) {
this.in = in;
}
public EdgeNode getFirstEdge() {
return firstEdge;
}
public void setFirstEdge(EdgeNode firstEdge) {
this.firstEdge = firstEdge;
}
@Override
public String toString() {
return "[in=" + in + ", firstEdge=" + firstEdge + "]";
}
}
