java数据结构与算法总结(七)--【图数据结构的遍历】java实现广度优先和深度优先遍历

ゝ一世哀愁。 2023-07-23 11:57 11阅读 0赞

[来自][Link 1]

宽度优先搜索(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");
        }
    }

[Link 1]: https://www.cnblogs.com/honeybee/p/8557159.html