图的java实现以及深度优先搜索和广度优先搜索
接口的定义
图一般需要实现的接口
edge 边
vertex 顶点
public interface Gragh<V ,E> {
int edgesSize();
int VerticesSize();
void addVertex(V v);
void addEdge(V from , V to);
void addEdge(V from , V to , E weight);
void removeVertex(V v);
void removeEdge(V from , V to);
void bfs(V begin, vertexVisitor<V> visitor);//广度优先搜索
void dfs2(V begin, vertexVisitor<V> visitor);//深度优先搜索的非递归实现
void dfs(V begin, vertexVisitor<V> visitor);//深度优先搜索
interface vertexVisitor<V>{
boolean visit(V v);//返回一个Boolean值，如果返回的是true，退出遍历
}
}
实现类的实现
内部顶点类
在实现类中，顶点内部类存放:
1该顶点的数据信息 value
2以它为出度的边 outEdges
3以它为入度的边 inEdges
这样，使用HashSet存储与某一顶点有关的边，可以很方便地通过该顶点遍历这些边。
由于后面会使用HashMap和HashSet，所以实现了hashCode方法和equals方法
//顶点和边的信息使用泛型<V , E> ，是因为节点标识和边的权重信息应该是不同的数据类型
private static class Vertex<V , E>{
V value;//存放节点标识
/*用于存放到达该节点和以该节点出发的所有边的信息，使用hashSet数据结构对它们进行存储，是因为它们（边）没有顺序
* 而对没有顺序的数据，使用HashSet数据结构，查询效率较高
*/
HashSet<Edge<V , E>> inEdges=new HashSet<>();
HashSet<Edge<V , E>> outEdges=new HashSet<>();
public Vertex(V value) {
this.value = value;
}
//使用哈希表一般需要实现hashCode方法和equals方法
@Override
public boolean equals(Object obj) {
return Objects.equals(value, ((Vertex<V , E>)obj).value) ;
}
@Override
public int hashCode() {
return value==null?0:value.hashCode();
}
@Override
public String toString() {
return "Vertex [value=" + (value==null?"null":value) + "]";
}
}
内部边类
一条边包含3个信息：
1.边的权值
2.边的起点 from
3.边的终点 to
这样，可以通过边方便地找到与该边有关的顶点（from和to）。
注：由于后面会使用HashMap和HashSet，所以实现了hashCode方法和equals方法
/*
* 一条边包含三个信息；该边的起点（inVertex），该边的终点（outVertex），权重weight
*/
private static class Edge<V , E>{
Vertex<V , E>from;
Vertex<V , E>to;
E weight;
public Edge(Vertex<V , E> from, Vertex<V , E>to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object obj) {
Edge<E, V> edge=(Edge<E, V>)obj;
return Objects.equals(from, edge.from)&&Objects.equals(to, edge.to);
}
@Override
public int hashCode() {
//顶点对象不会为空，所以不需要判空
return from.hashCode()*31+to.hashCode();
}
@Override
public String toString() {
return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
}
}
实现类中成员变量
在实现类中使用两个成员变量：
1.一个HashMap类型的vertices ，这样可以通过用户传入的V类型数据，很方便地找到对应的顶点（Vertex<V , E>类型），使得顶点不必对外公开，保持私有。
2.一个用于统计图中所有的边的HashSet类型的edges，由于在内部顶点类和内部边类中，存放的都是与某一顶点或边有关的信息，很难通过这些信息获取边数，所有使用一个成员变量edges来较为容易地得到边数。
//使用hashMap存储顶点信息，这样可以通过V值查找对应的节点
HashMap<V, Vertex<V , E>> vertices = new HashMap<>();
//使用HashSet存放所有的边，该结构只能使用遍历的方式访问
private Set<Edge<V , E>> edges= new HashSet<>() ;
实现类中主要方法的实现
edgesSize和VerticesSize
由于定义了vertices 和edges两个成员，获得边数和顶点数的方法就可以十分容易地写出：
@Override
public int edgesSize() {
return edges.size();
}
@Override
public int VerticesSize() {
return vertices.size();
}
addVertex和addEdge
添加节点不需要做额外处理，直接判断合法后将该节点放入到vertices 中
@Override
public void addVertex(V v) {
//如果存放顶点的容器中已经有了该顶点，就不需要添加
if(vertices.containsKey(v)) return;
//创建顶点将其放入到hashmap中，并与v（作为key)绑定
vertices.put(v,new Vertex<>(v));
}
添加边的时候需要考虑如下问题：
1.边的起点是否存在，如果不存在，采取创建该顶点加入到vertices 中的策略
2.边的终点是否存在，如果不存在，采取创建该顶点加入到vertices 中的策略
3.待添加的边是否存在，如果存在，删除该边，重新添加（重新添加一般用于用户对某条边的权值的更改）
注：在删除的时候，fromVertex，toVertex以及edges三个HashSet对边的匹配策略已经被内部顶点类（Vertex<V , E>）和内部边类（ Edge<V , E>）中的hashCode方法和equals方法限制，即对于边的匹配，只要起点和终点相同就视为两边相等。
@Override
public void addEdge(V from, V to) {
addEdge(from, to,null);
}
@Override
public void addEdge(V from, V to, E weight) {
Vertex<V , E> fromVertex = vertices.get(from);
if(fromVertex == null) {
//如果该顶点不在vertices中，将其以（key,value）形式加入
fromVertex = new Vertex<>(from);
vertices.put(from , fromVertex);
}
Vertex<V , E> toVertex = vertices.get(to);
if(toVertex == null) {
toVertex = new Vertex<>(to);
vertices.put(to , toVertex);
}
//以from 和 to 创建一条边，并判断该边是否已经存在，如果存在，先将其移除，在重新添加，这样重新添加会更新weight，如果不存在，直接添加
Edge<V , E> edge = new Edge<>(fromVertex, toVertex);
edge.weight = weight;
//尝试在fromVertex.outEdges中删除edge，如果删除成功，再在其他容器中将该边删除
if(fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
//无论是否删除成功，都将该边加入到对应的各个容器中
fromVertex.outEdges.add(edge);
toVertex.inEdges.add(edge);
edges.add(edge);
}
removeEdge
删除边的过程比较简单，先判断起点和终点是否存在（如果起点和终点有一个不存在，直接表明该边不存在，退出该方法），再判断该边是否存在，如果存在，应在所有存储该边的容器中将其删除
@Override
public void removeEdge(V from, V to) {
//如果顶点有一个不存在，直接返回
Vertex<V , E> fromVertex=vertices.get(from);
if(fromVertex==null) return;
Vertex<V , E>toVertex=vertices.get(to);
if(toVertex==null) return;
//以传入的两个顶点作为参数创建边
Edge<V , E>edge= new Edge<>(fromVertex, toVertex);
//在fromVertex.outEdges中尝试删除该边，如果删除失败，表明该边不存在，如果删除成功，remove方法返回true，进行if内部继续在对应容器中依次删除该边
if(fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
}
删除顶点的过程：
1.如果顶点不存在，直接退出该方法
2.使用迭代器删除该顶点outEdges域中与该顶点相关的边，并在删除这些边之前通过这些边找到这些边的终点，移除这些边的终点节点对该边的存储。同时要删除该边在成员edges中的保存。
3.使用迭代器删除该顶点inEdges域中与该顶点相关的边，并在删除这些边之前通过这些边找到这些边的起点，移除这些边的起点节点对该边的存储，同时要删除该边在成员edges中的保存。
@Override
public void removeVertex(V v) {
//尝试在vertices中删除v对应的顶点，如果删除成功，该顶点会被返回
Vertex<V , E>vertex=vertices.remove(v);
if(vertex==null) return;//如果返回的为空，表明该顶点不存在，直接退出
//使用迭代器删除，对容器中的数据，如果需要在遍历的过程中将其中的数据删除，一般使用迭代器
//使用迭代器遍历顶点的outEdges域,并将其中的所有边删除
for (Iterator iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
Edge<V , E> edge = (Edge<V , E>) iterator.next();
edge.to.inEdges.remove(edge);//删除该边的终点节点对该边的保存
iterator.remove();//删除当前遍历位置的该边（即vertex.outEdges中遍历到
edges.remove(edge);//删除成员变量中的该边
}
//使用迭代器遍历顶点的inEdges域，并删除其中的所有边
for(Iterator iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
Edge<V , E> edge = (Edge<V , E>) iterator.next();
edge.from.outEdges.remove(edge);//删除该边的起点节点对该边的保存
iterator.remove();//删除遍历到的所有边，
edges.remove(edge);//删除成员变量中的该边
}
}
广度优先搜索
广度优先遍历的逻辑是：传入一个起点，先访问以该起点出发，能够直接抵达的所有顶点，然后以被抵达的那些顶点出发，访问那些顶点能够直接抵达的节点。这样直到所有可达的顶点被访问完。
访问过程中不可重复访问。
广度优先搜索可以类比二叉树的层序遍历（更准确的说，是多叉树的层序遍历），在二叉树的层序遍历中，我们使用了队列作为辅助，这里同样使用队列，来完成对当前节点访问后储存它的直接可达节点，便于之后继续以这些节点向后遍历。
@Override
public void bfs(V begin, vertexVisitor<V> visitor) {
if(visitor==null) return ;
Vertex<V , E> beginVertex= vertices.get(begin);//用传入的参数作为key获取HashMap中的对应节点。
if(beginVertex==null) return;
Queue<Vertex<V , E>> queue=new LinkedList<>();
Set<Vertex<V , E>> visitedVertexs= new HashSet<>();
queue.add(beginVertex);//先将起点元素添加进入队列
visitedVertexs.add(beginVertex);//将起点元素添加到Set中
while(!queue.isEmpty()) {//当队列不为空时执行循环
Vertex<V , E> vertex = queue.poll(); //每次取出队列头部元素，处理该元素
if(visitor.visit(vertex.value)) return;
//使用增强循环遍历当前节点的outEdges域（这里可以用增强循环，而在remove方法中只能用迭代器，是因为
//在remove方法中遍历的过程对遍历到的元素进行了删除操作，只能使用迭代器）
for(Edge<V , E> edge:vertex.outEdges) {
//每次判断遍历到的节点的终点顶点如果已经在Set中，就不进行处理，如果不在，将它入队并加入到set中
if(visitedVertexs.contains(edge.to)) continue;
queue.add(edge.to);//将遍历到的边的终点节点添加到队列中
visitedVertexs.add(edge.to);
}
}
}
深度优先搜索
深度优先搜索的逻辑是：
从起始节点开始，找到一条出去的边，访问该边的终点，再以该终点为起点，继续向下访问，直到该路径无法继续访问后，依次退回到之前的节点，判断之前的节点是否还有其他未被访问的路径，如果有，朝这些路径继续访问。
深度优先搜索递归实现
该算法在递归过程中，每次遍历一个节点的outEdges域时，都对新节点进行递归，使得只要该路径还能向下遍历，就继续向下遍历，而如果该路径不能再向下遍历（无路可走或者路径上的节点都已经被访问过），在退回过程中，会回退到对outEdges域的遍历过程，去试探其他未被访问的路径。
@Override
public void dfs(V begin, vertexVisitor<V> visitor) {
if(visitor==null) return ;
Vertex<V, E> beginVertex=vertices.get(begin);
if(beginVertex==null) return;
dfs(beginVertex,new HashSet<>(),visitor);
}
private void dfs(Vertex<V, E> vertex,Set<Vertex<V, E>> visitedVertice, vertexVisitor<V> visitor) {
//先访问当前节点，使用访问器，如果访问器返回true，退出遍历过程
if(visitor.visit(vertex.value)) return;
visitedVertice.add(vertex);//将当前被访问的节点添加到记录已被访问的节点的set中
for(Edge<V, E> edge:vertex.outEdges) {//遍历访问所有与当前节点相邻的节点
if(visitedVertice.contains(edge.to)) continue;//如果已经被访问过，不做任何处理
//如果没有被访问过，以该节点为vertex,递归调用
dfs(edge.to, visitedVertice,visitor);
}
}
深度优先搜索非递归实现
非递归实现使用栈辅助遍历。该算法先将起点入栈并处理（否则后面将没有机会处理该顶点），然后进入循环，循环中每次取出栈顶元素对其outEdges域进行遍历，如果找到一条可行边（该边终点未被访问过），就将当前节点与该边对应的终点依次放入栈中，并退出对当前节点的outEdges域的遍历过程。 继续进入到出栈、处理栈顶元素的过程。（每次新节点的访问时机是在新节点入栈时）
@Override
public void dfs2(V begin, vertexVisitor<V> visitor) {
//先进行参数合法检查
if(visitor==null) return ;
Vertex<V, E> beginVertex=vertices.get(begin);
if(beginVertex==null) return ;
Set<Vertex<V, E>> visitedVertices = new HashSet<>();
ArrayDeque<Vertex<V, E>> stack= new ArrayDeque<>();
stack.push(beginVertex);
visitedVertices.add(beginVertex);
if(visitor.visit(beginVertex.value)) return;
while(!stack.isEmpty()) {
Vertex<V, E> vertex=stack.pop();
for(Edge<V, E> edge : vertex.outEdges) {
if(visitedVertices.contains(edge.to))continue;
stack.push(vertex); //当前元素再次入栈
stack.push(edge.to);//新元素每次进栈的时候被打印，并包含到set中
visitedVertices.add(edge.to);
if(visitor.visit(edge.to.value)) return;
break;//每次找到一条可行路径，就退出循环，以实现深度优先
}
}
}
上一篇： jQuery 源码解析(二十七) 样式操作模块 坐标详解
下一篇： 银企支付-详细设计文档