数据结构选择 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();
- }
- }
来源: http://www.bubuko.com/infodetail-3412039.html