站点图标

Java图实现

2019-05-05折腾记录Java / 算法
本文最后更新于 410 天前,文中所描述的信息可能已发生改变

没有介绍,请自行百度或谷歌,代码经过了一定的测试,但不保证没有 Bug。


_263
package MyGraphDemo;
_263
_263
import java.util.ArrayList;
_263
import java.util.Arrays;
_263
import java.util.Collections;
_263
import java.util.LinkedList;
_263
import java.util.List;
_263
import java.util.Scanner;
_263
_263
/**
_263
* MyGraphDemo
_263
*/
_263
public class MyGraphDemo {
_263
public static void main(String[] args) {
_263
Scanner in = new Scanner(System.in);
_263
MyGraph<Integer> gra = new MyGraph<Integer>();
_263
gra.add(null, 0, 1);
_263
gra.add(0, 1, 1);
_263
gra.add(0, 2, 1);
_263
gra.add(0, 3, 1);
_263
gra.add(1, 2, 1);
_263
gra.add(2, 3, 1);
_263
gra.testString();
_263
// List<MyGraph<Integer>.Vertex> list = gra.BFS(0, 3);
_263
// for (MyGraph<Integer>.Vertex var : list) {
_263
// System.out.print(var.data);
_263
// }
_263
int[][] a = gra.toAssociationMatrix();
_263
for (int i = 0; i < 4; i++) {
_263
System.out.println(Arrays.toString(a[i]));
_263
}
_263
in.close();
_263
}
_263
}
_263
_263
/**
_263
* MyGraph
_263
* Vertex中存放顶点的信息,以及连接点列表
_263
* Edge中存放权重,和与之连接点在VertexList中的索引
_263
*/
_263
class MyGraph<T extends Comparable> {
_263
List<Vertex> vertexList;
_263
List<EdgeNoPath> edgeList;
_263
MyGraph() {
_263
this.vertexList = new LinkedList<Vertex>();
_263
this.edgeList = new LinkedList<EdgeNoPath>();
_263
}
_263
// 顶点类
_263
class Vertex {
_263
T data;
_263
List<Edge> link;
_263
Vertex() {}
_263
Vertex(T data) {
_263
link = new LinkedList<Edge>();
_263
this.data = data;
_263
}
_263
}
_263
// 边类
_263
class Edge {
_263
int prev;
_263
int index;
_263
int weight;
_263
Edge(int index, int weight, int prev) {
_263
this.prev = prev;
_263
this.index = index;
_263
this.weight = weight;
_263
}
_263
}
_263
class EdgeNoPath {
_263
int[] index;
_263
int weight;
_263
EdgeNoPath(int index1, int index2, int weight) {
_263
boolean is = true;
_263
for (int i = 0; i < edgeList.size(); i++) {
_263
if((edgeList.get(i).index[0] == index1 && edgeList.get(i).index[1] == index2) || (edgeList.get(i).index[0] == index2 && edgeList.get(i).index[1] == index1)) {
_263
is = false;
_263
break;
_263
}
_263
}
_263
if(is) {
_263
this.weight = weight;
_263
this.index = new int[2];
_263
this.index[0] = index1;
_263
this.index[1] = index2;
_263
}
_263
}
_263
}
_263
/**
_263
* 添加顶点
_263
* @param prevData 连接的上一个顶点的数据
_263
* @param nextData 连接的上一个顶点的数据
_263
* @param weight 边的权重
_263
*/
_263
public void add(T prevData, T nextData, int weight) {
_263
if(prevData == null && vertexList.size() == 0) {
_263
vertexList.add(new Vertex(nextData));
_263
return;
_263
} else if(prevData == null && vertexList.size() != 0) {
_263
return;
_263
}
_263
// 定位上一个节点
_263
int prev_index = this.getIndexFromData(prevData);
_263
int next_index = this.getIndexFromData(nextData);
_263
Vertex new_vertex;
_263
if(next_index == -1) {
_263
new_vertex = new Vertex(nextData);
_263
// 将新节点添加到顶点列表中
_263
vertexList.add(new_vertex);
_263
next_index = vertexList.size()-1;
_263
} else {
_263
new_vertex = vertexList.get(next_index);
_263
}
_263
// 将边的信息添加到新节点
_263
new_vertex.link.add(new Edge(prev_index, weight, next_index));
_263
// 将边的信息添加到上一个节点
_263
vertexList.get(prev_index).link.add(new Edge(next_index, weight, prev_index));
_263
edgeList.add(new EdgeNoPath(prev_index, next_index, weight));
_263
}
_263
/**
_263
* 获取制定data的顶点在顶点列表中的索引
_263
* @param data 要进行搜索的数据
_263
* @return 返回当前数据的顶点在顶点邻接表的索引,若未找到就返回 -1
_263
*/
_263
public int getIndexFromData(T data) {
_263
int i = -1;
_263
while(vertexList.size() > i+1) {
_263
if(vertexList.get(i+1).data.compareTo(data) == 0) {
_263
i++;
_263
return i;
_263
}
_263
i++;
_263
}
_263
return -1;
_263
}
_263
// public int vertexOfEdge(T data) {
_263
_263
// }
_263
public void testString() {
_263
for (Vertex var : vertexList) {
_263
System.out.print(var.data.toString() + ",");
_263
for (Edge v : var.link) {
_263
System.out.print(vertexList.get(v.index).data.toString()+" ");
_263
}
_263
System.out.println();
_263
}
_263
}
_263
// 深度优先搜索 - 递归隐藏方法
_263
private boolean DFS(Vertex vertex, T data, List<Vertex> list, boolean[] visited) {
_263
if(vertex == null) return false;
_263
if(vertex.data.compareTo(data) == 0) {
_263
list.add(vertex);
_263
return true;
_263
}
_263
for (int i = vertex.link.size()-1; i >= 0; i--) {
_263
int ver_index = vertex.link.get(i).index;
_263
if(!visited[ver_index]) {
_263
Vertex tempVertex = vertexList.get(ver_index);
_263
visited[ver_index] = true;
_263
boolean is = DFS(tempVertex, data, list, visited);
_263
if(is) {
_263
list.add(vertex);
_263
return true;
_263
}
_263
visited[ver_index] = false;
_263
}
_263
}
_263
return false;
_263
}
_263
/**
_263
* 深度优先搜索进行路径查找
_263
* @param startData 起点
_263
* @param Enddata 终点
_263
* @return 返回路径的点列表
_263
*/
_263
public List<Vertex> DFS(T startData, T endData) {
_263
int start_index = this.getIndexFromData(startData);
_263
boolean[] visited = new boolean[vertexList.size()];
_263
visited[start_index] = true;
_263
List<Vertex> list = new ArrayList<Vertex>();
_263
DFS(vertexList.get(start_index), endData, list, visited);
_263
Collections.reverse(list);
_263
return list;
_263
}
_263
/**
_263
* 广度优先搜索进行路径查找
_263
* @param startData 起点
_263
* @param Enddata 终点
_263
* @return 返回路径的点列表
_263
*/
_263
public List<Vertex> BFS(T startData, T endData) {
_263
int start_index = this.getIndexFromData(startData);
_263
BFS_Node endNode = null;
_263
List<BFS_Node> queue = new LinkedList<BFS_Node>();
_263
queue.add(new BFS_Node(vertexList.get(start_index), null));
_263
while (!queue.isEmpty()) {
_263
BFS_Node currentNode = queue.remove(0);
_263
if(currentNode.vertex.data.compareTo(endData) == 0) {
_263
endNode = currentNode;
_263
break;
_263
}
_263
for (int i = 0; i < currentNode.vertex.link.size(); i++) {
_263
queue.add(new BFS_Node(vertexList.get(currentNode.vertex.link.get(i).index), currentNode));
_263
}
_263
}
_263
List<Vertex> list = new LinkedList<Vertex>();
_263
while (endNode != null) {
_263
list.add(endNode.vertex);
_263
endNode = endNode.parent;
_263
}
_263
Collections.reverse(list);
_263
return list;
_263
}
_263
// 广度优先搜索进行路径追踪需要的类
_263
class BFS_Node {
_263
Vertex vertex;
_263
BFS_Node parent;
_263
BFS_Node(Vertex vertex, BFS_Node parent) {
_263
this.vertex = vertex;
_263
this.parent = parent;
_263
}
_263
}
_263
_263
/**
_263
* 将顶点列表转换为顶点数组
_263
* @return 顶点数组
_263
*/
_263
public Object[] toArraysVertex() {
_263
Object[] vertexs = vertexList.toArray();
_263
return vertexs;
_263
}
_263
/**
_263
* 将邻接表的图转换为邻接矩阵
_263
* @return 邻接矩阵数组
_263
*/
_263
public int[][] toAdjacencyMatrix() {
_263
int vertexSize = vertexList.size();
_263
int[][] matrix = new int[vertexSize][vertexSize];
_263
for (int i = 0; i < vertexSize; i++) {
_263
Vertex currentVertex = vertexList.get(i);
_263
for (int j = 0; j < currentVertex.link.size(); j++) {
_263
Edge currentEdge = currentVertex.link.get(j);
_263
matrix[i][currentEdge.index] = currentEdge.weight;
_263
}
_263
}
_263
return matrix;
_263
}
_263
_263
/**
_263
* 将邻接表图转换为关联矩阵
_263
* @return 关联矩阵数组
_263
*/
_263
public int[][] toAssociationMatrix() {
_263
int vertexSize = vertexList.size();
_263
int edgeSize = edgeList.size();
_263
int[][] matrix = new int[vertexSize][edgeSize];
_263
for (int j = 0; j < edgeSize; j++) {
_263
EdgeNoPath currentEdge = edgeList.get(j);
_263
matrix[currentEdge.index[0]][j]++;
_263
matrix[currentEdge.index[1]][j]++;
_263
}
_263
return matrix;
_263
}
_263
}

Java图实现

https://blog.ixk.me/post/java-graph-implementation
  • 许可协议

    BY-NC-SA

  • 发布于

    2019-05-05

  • 本文作者

    Otstar Lin

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

Java二叉树实现为apt方式安装的nginx重新编译增加WebDAV