数据结构选择TreeSet的原因：通过自定义的Compare方法，保证了点元素的唯一性，有序性（方便检验）；
传入Set和Map中的元素类似于C中的指针操作，即共享地址，改变其中一个中的元素，与之相关的都会被改变；
实现代码内容：
1.图的定义；
2.插入点；
3.插入边；
4.BFS;
5.DFS;
代码如下：
/**
* FileName: Graph
* Author: Jerry
* Date: 2020/2/8 10:33
* Description: 图
*/
package Graph_DFS_AND_BFS;
import java.util.*;
public class Graph {
//点类
static class Vertex implements Comparable<Vertex> {
private int name;
private boolean isVisiable;
Vertex(int name) {
this.name = name;
}
@Override
public int compareTo(Vertex o) {
return this.name-o.name;
}
}
//图定义的顶点表和邻接表
private TreeSet<Vertex> vertexSet = new TreeSet<Vertex>();
private TreeMap<Vertex, LinkedList<Vertex>> map = new TreeMap<Vertex, LinkedList<Vertex>>();
//返回定点表和邻接表
private TreeSet<Vertex> getVertexSet()
{
return vertexSet;
}
private TreeMap<Vertex,LinkedList<Vertex>> getMap(){
return map;
}
//图的初始化
//主要是为了先深搜索和先广搜索不会干扰考虑
private void initial(){
TreeSet<Vertex> vertexSet = getVertexSet();
TreeMap<Vertex,LinkedList<Vertex>> treeMap = getMap();
for(Vertex vertex:vertexSet){
vertex.isVisiable=false;
}
for(Vertex vertex:treeMap.keySet()){
vertex.isVisiable=false;
}
}
//构造函数
public Graph(TreeSet<Vertex> vertexSet,TreeMap<Vertex,LinkedList<Vertex>> map){
this.vertexSet=vertexSet;
this.map=map;
initial();
}
//图的元素扩充
//放入点
public void putVertex(Vertex vertex){
TreeSet<Vertex> vertexSet = getVertexSet();
TreeMap<Vertex,LinkedList<Vertex>> map = getMap();
if(vertexSet.contains(vertex)){
System.out.println("重复元素！输入无效！");
}
else{
vertex.isVisiable=false;
vertexSet.add(vertex);
LinkedList<Vertex> list = new LinkedList<Vertex>();
map.put(vertex,list);
}
}
//放入边
public void putEdge(Vertex vertex1,Vertex vertex2){
TreeSet<Vertex> vertexSet = getVertexSet();
TreeMap<Vertex,LinkedList<Vertex>> map = getMap();
//在这里默认通过构造函数传入的TreeSet，TreeMap没有错误
//对vertex1的分析
if(vertexSet.contains(vertex1)){
if(!map.get(vertex1).contains(vertex2)){
map.get(vertex1).add(vertex2);
}//if
}//if
else{
vertexSet.add(vertex1);
LinkedList<Vertex> list = new LinkedList<>();
list.add(vertex2);
map.put(vertex1,list);
}//else
//对vertex2的分析
if(vertexSet.contains(vertex2)){
if(!map.get(vertex2).contains(vertex1)){
map.get(vertex2).add(vertex1);
}//if
}//if
else{
vertexSet.add(vertex2);
LinkedList<Vertex> list = new LinkedList<>();
list.add(vertex1);
map.put(vertex2,list);
}//else
}
//以上为图的构造过程，元素添加
//以下为图的搜索，DFS和BFS,由于图的搜索确定进入点很关键，我们采用重载，两个同名方法（参数是否包含搜索起始点）
private void visit(Vertex vertex){
System.out.println(vertex.name);
}
//图的先深搜索
//默认从name最小的点开始搜索
public void DFS(){
System.out.println("先深搜索为：");
TreeMap<Vertex,LinkedList<Vertex>> map = getMap();
Vertex vertex = map.firstKey();
DFS(vertex);//如果确定从第一个键开始搜索，DFS可以优化，这里不作说明
}
//带有起始点的搜索
public void DFS(Vertex vertex){
TreeMap<Vertex,LinkedList<Vertex>> map = getMap();
//访问vertex的连通区域
if(!vertex.isVisiable){
visit(vertex);
vertex.isVisiable=true;
for(Vertex vertex1:map.get(vertex)){
if(!vertex1.isVisiable){
DFS(vertex1);
}//if
}//for
}//if
//处理其它非连通区域,这里效率不高，但也很没有办法，否则无法保证从任意点开始访问
for(Vertex vertex2:map.keySet()){
if(!vertex2.isVisiable){
DFS(vertex2);
}
}
}
//先广搜索,从第一个节点开始搜索
//值得注意的一点是，Set和Map中传入的元素是共享的，即它们传入的是类似于C中的指针操作；
public void BFS(){
System.out.println("BFS搜索如下：");
initial();
TreeMap<Vertex,LinkedList<Vertex>> map = getMap();
TreeSet<Vertex> treeSet = getVertexSet();
Queue<Vertex> queue = new LinkedList<Vertex>();
int i=0;
for(Vertex vertex:treeSet){
if(!vertex.isVisiable){
vertex.isVisiable=true;
visit(vertex);
queue.add(vertex);
while(!queue.isEmpty()){
Vertex vertex1 = queue.poll();
for(Vertex vertex2:map.get(vertex1)){
if (!vertex2.isVisiable) {
visit(vertex2);
vertex2.isVisiable=true;
queue.add(vertex2);
}//if
}//for
}//while
}
}
}
public static void main(String []args){
TreeSet<Vertex> vertexSet= new TreeSet<>();
Vertex vertex1 = new Vertex(1);
Vertex vertex2 = new Vertex(2);
Vertex vertex3 = new Vertex(3);
Vertex vertex4 = new Vertex(4);
Vertex vertex5 = new Vertex(5);
vertexSet.add(vertex1);
vertexSet.add(vertex2);
vertexSet.add(vertex3);
vertexSet.add(vertex4);
vertexSet.add(vertex5);
LinkedList<Vertex> list1 = new LinkedList<Vertex>();
LinkedList<Vertex> list2 = new LinkedList<Vertex>();
LinkedList<Vertex> list3 = new LinkedList<>();
LinkedList<Vertex> list4 = new LinkedList<>();
LinkedList<Vertex> list5 = new LinkedList<>();
list1.add(vertex2);list1.add(vertex3);list1.add(vertex4);
list2.add(vertex1);list2.add(vertex4);
list3.add(vertex1);list3.add(vertex5);
list4.add(vertex1);list4.add(vertex2);list4.add(vertex5);
list5.add(vertex4);list5.add(vertex3);
TreeMap<Vertex,LinkedList<Vertex>> map = new TreeMap<Vertex, LinkedList<Vertex>>() ;
map.put(vertex1,list1);map.put(vertex2,list2);map.put(vertex3,list3);
map.put(vertex4,list4);map.put(vertex5,list5);
Graph graph = new Graph(vertexSet,map);
graph.DFS();
graph.BFS();
}
}