首页 > Hot资讯 > 正文

Java数据结构：有向图的深度优先遍历

2022-09-07 09:51:50
879次极悦

程序中的“图”

图的存储

需要一个Java Set集合来存储我们的节点元素。

需要一个映射(HashMap)来存储节点是否被访问过。

需要一个 HashMap 来存储节点间的通路。

如下图所示：

代码实现

DFS深度优先遍历算法也在里面。

import java.util.*;
/**
 * @ClassName ArrayGraph
 * @Description 自定义“有向图”class，不允许有重复的元素
 * @Author SkySong
 * @Date 2021-05-16 17:14
 */
public class ArrayGraph<T> {
    //存放节点元素
    private Set<T> vars;
    //标记节点是否被访问过
    private HashMap<T, Boolean> visit;
    //节点间的通路
    private HashMap<T, ArrayList<T>> accesses = new HashMap<>();
    /**
     * 清空访问
     */
    public void clearVisit() {
        try {
            vars.forEach((k) -> visit.put(k, false));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    /**
     * 初始化节点集合
     *
     * @param vars 节点集合
     */
    public ArrayGraph(Set<T> vars) {
        this.vars = vars;
        visit  = new HashMap<>();
        clearVisit();
    }
    /**
     * 添加节点间通路
     *
     * @param from 出发节点
     * @param to   目的节点
     */
    public void addAccess(T from, T to) {
        if (!vars.contains(from) && !vars.contains(to)) {
            return;
        }
        ArrayList<T> ts = accesses.get(from);
        if (ts == null) {
            ts = new ArrayList<>();
        }
        ts.add(to);
        accesses.put(from, ts);
    }
    /**
     * DFS 深度优先遍历
     *
     * @param head 起始节点
     * @return 图 “变” 数组
     */
    public List<T> DFSOrder(T head) {
        if (!vars.contains(head)) {
            return null;
        }
         //创建一个list，用来存放最终的有序 序列
        ArrayList<T> list = new ArrayList<>();
        //毫无疑问，第一个遍历的节点元素一定是 我们传进去的 head
        list.add(head);
        //确定 head 的通路（head通向的节点）
        ArrayList<T> ts = accesses.get(head);
        if (ts == null || ts.isEmpty()){
            visit.put(head,true);
            return list;
        }
        //改变 head 的访问状态
        visit.put(head,true);
        Stack<T> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()){
            int index = 0;
            for (T t : ts) {
                //如果此节点已经访问过了，我们就不做任何操作
                if (visit.get(t)){
                    continue;
                }
                //如果此节点没有访问过，访问之
                list.add(t);
                //改变节点访问状态
                visit.put(t,true);
                //探寻此节点的下一层“通路”
                ts = accesses.get(t);
                if (ts != null){
                    //如果此节点下一层有“通路”，便将此节点放入栈中
                    stack.push(t);
                    //并改变标志位，跳过出栈操作
                    index++;
                }
                break;
            }
            //如果此节点没有下一层可以访问，则触发出栈操作，去上一层寻找
            if (index == 0){
                T pop = stack.pop();
                ts = accesses.get(pop);
            }
        }
        return list;
    }
}

针对这个DFS，我们大致阐述一下思路。

首先明确一点，图的遍历是需要确定一个起始节点的。(这也是我们这个DFS方法的参数)。

首先我们需要一个栈，这个栈是完成我们“深度优先”的主要工具

何为“深度优先”，当我们在访问过程中，遇到分支了，优先选择下一层的分支进行访问。

我们利用栈“先进后出”的特性，将当前节点的“上级”们先逐层保存起来。确保我们能向上逐层找到他们。

我们开始进行访问，每层访问一个节点便向下层访问，当我们发现不能向下了(与当前节点相连的节点都被访问过了)，就往上倒一层，然后重复上述过程。

测试

public static void main(String[] args) {
        ArrayGraph<Integer> graph = new ArrayGraph<>(Sets.newHashSet(1,2,3,4,5));
        graph.addAccess(1,2);
        graph.addAccess(1,3);
        graph.addAccess(2,4);
        graph.addAccess(3,4);
        graph.addAccess(5,1);        
        System.out.println(graph.DFSOrder(5).toString());
    }

结果：