欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java基础总结(六十四)--【图数据结构的遍历】java实现广度优先和深度优先遍历

程序员文章站 2022-05-20 20:23:30
...

来自

宽度优先搜索(BFS)遍历图需要使用队列queue数据结构; 深度优先搜索(DFS, Depth First Search)的实现
需要使用到栈stack数据结构。

java中虽然有Queue接口,单java并没有给出具体的队列实现类,而Java中让LinkedList类实现了Queue接口,所以使用队列的时候,一般采用LinkedList。因为LinkedList是双向链表,可以很方便的实现队列的所有功能。
java中定义队列 一般这样定义: Queue queue = new LinkedList();

java中的栈由java.util.Stack类实现,是一个后进先出(last in first out,LIFO)的堆栈,在Vector类的基础上扩展5个方法而来。

E push(E item)   
         把项压入堆栈顶部。   
E pop()   
         移除堆栈顶部的对象,并作为此函数的值返回该对象。   
E peek()   
         查看堆栈顶部的对象,但不从堆栈中移除它。   
boolean empty()   
         测试堆栈是否为空。    
int search(Object o)   
         返回对象在堆栈中的位置,以 1 为基数。

 BFS和DFS遍历代码实现如下:

import java.util.*;

/**
 * 使用java实现图的图的广度优先 和深度优先遍历算法。
 */
public class GraphLoopTest {
    private Map<String, List<String>> graph = new HashMap<String, List<String>>();

    /**
     * 初始化图数据:使用邻居表来表示图数据。
     */
    public void initGraphData() {
//        图结构如下
//          1
//        /   \
//       2     3
//      / \   / \
//     4  5  6  7
//      \ | / \ /
//        8    9
        graph.put("1", Arrays.asList("2", "3"));
        graph.put("2", Arrays.asList("1", "4", "5"));
        graph.put("3", Arrays.asList("1", "6", "7"));
        graph.put("4", Arrays.asList("2", "8"));
        graph.put("5", Arrays.asList("2", "8"));
        graph.put("6", Arrays.asList("3", "8", "9"));
        graph.put("7", Arrays.asList("3", "9"));
        graph.put("8", Arrays.asList("4", "5", "6"));
        graph.put("9", Arrays.asList("6", "7"));
    }

    /**
     * 宽度优先搜索(BFS, Breadth First Search)
     * BFS使用队列(queue)来实施算法过程
     */
    private Queue<String> queue = new LinkedList<String>();
    private Map<String, Boolean> status = new HashMap<String, Boolean>();

    /**
     * 开始点
     *
     * @param startPoint
     */
    public void BFSSearch(String startPoint) {
        //1.把起始点放入queue;
        queue.add(startPoint);
        status.put(startPoint, false);
        bfsLoop();
    }

    private void bfsLoop() {
        //  1) 从queue中取出队列头的点;更新状态为已经遍历。
        String currentQueueHeader = queue.poll(); //出队
        status.put(currentQueueHeader, true);
        System.out.println(currentQueueHeader);
        //  2) 找出与此点邻接的且尚未遍历的点,进行标记,然后全部放入queue中。
        List<String> neighborPoints = graph.get(currentQueueHeader);
        for (String poinit : neighborPoints) {
            if (!status.getOrDefault(poinit, false)) { //未被遍历
                if (queue.contains(poinit)) continue;
                queue.add(poinit);
                status.put(poinit, false);
            }
        }
        if (!queue.isEmpty()) {  //如果队列不为空继续遍历
            bfsLoop();
        }
    }


    /**
     * 深度优先搜索(DFS, Depth First Search)
     * DFS使用队列(queue)来实施算法过程
     * stack具有后进先出LIFO(Last Input First Output)的特性,DFS的操作步骤如下:
     */
//     1、把起始点放入stack;
//     2、重复下述3步骤,直到stack为空为止:
//    从stack中访问栈顶的点;
//    找出与此点邻接的且尚未遍历的点,进行标记,然后全部放入stack中;
//    如果此点没有尚未遍历的邻接点,则将此点从stack中弹出。

    private Stack<String> stack = new Stack<String>();
    public void DFSSearch(String startPoint) {
        stack.push(startPoint);
        status.put(startPoint, true);
        dfsLoop();
    }

    private void dfsLoop() {
        if(stack.empty()){
            return;
        }
        //查看栈顶元素,但并不出栈
        String stackTopPoint = stack.peek();
        //  2) 找出与此点邻接的且尚未遍历的点,进行标记,然后全部放入queue中。
        List<String> neighborPoints = graph.get(stackTopPoint);
        for (String point : neighborPoints) {
            if (!status.getOrDefault(point, false)) { //未被遍历
                stack.push(point);
                status.put(point, true);
                dfsLoop();
            }
        }
        String popPoint =  stack.pop();
        System.out.println(popPoint);
    }

    public static void main(String[] args) {
        GraphLoopTest test = new GraphLoopTest();
        test.initGraphData();
//        test.BFSSearch("1");
        test.DFSSearch("1");
    }
}