程序中的“圖”

圖的存儲

需要一個Java Set集合來存儲我們的節(jié)點元素。

需要一個映射(HashMap)來存儲節(jié)點是否被訪問過。

需要一個 HashMap 來存儲節(jié)點間的通路。

如下圖所示：

代碼實現(xiàn)

DFS深度優(yōu)先遍歷算法也在里面。

import java.util.*;
/**
 * @ClassName ArrayGraph
 * @Description 自定義“有向圖”class，不允許有重復的元素
 * @Author SkySong
 * @Date 2021-05-16 17:14
 */
public class ArrayGraph<T> {
    //存放節(jié)點元素
    private Set<T> vars;
    //標記節(jié)點是否被訪問過
    private HashMap<T, Boolean> visit;
    //節(jié)點間的通路
    private HashMap<T, ArrayList<T>> accesses = new HashMap<>();
    /**
     * 清空訪問
     */
    public void clearVisit() {
        try {
            vars.forEach((k) -> visit.put(k, false));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    /**
     * 初始化節(jié)點集合
     *
     * @param vars 節(jié)點集合
     */
    public ArrayGraph(Set<T> vars) {
        this.vars = vars;
        visit  = new HashMap<>();
        clearVisit();
    }
    /**
     * 添加節(jié)點間通路
     *
     * @param from 出發(fā)節(jié)點
     * @param to   目的節(jié)點
     */
    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 深度優(yōu)先遍歷
     *
     * @param head 起始節(jié)點
     * @return 圖 “變” 數(shù)組
     */
    public List<T> DFSOrder(T head) {
        if (!vars.contains(head)) {
            return null;
        }
         //創(chuàng)建一個list，用來存放最終的有序 序列
        ArrayList<T> list = new ArrayList<>();
        //毫無疑問，第一個遍歷的節(jié)點元素一定是 我們傳進去的 head
        list.add(head);
        //確定 head 的通路（head通向的節(jié)點）
        ArrayList<T> ts = accesses.get(head);
        if (ts == null || ts.isEmpty()){
            visit.put(head,true);
            return list;
        }
        //改變 head 的訪問狀態(tài)
        visit.put(head,true);
        Stack<T> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()){
            int index = 0;
            for (T t : ts) {
                //如果此節(jié)點已經(jīng)訪問過了，我們就不做任何操作
                if (visit.get(t)){
                    continue;
                }
                //如果此節(jié)點沒有訪問過，訪問之
                list.add(t);
                //改變節(jié)點訪問狀態(tài)
                visit.put(t,true);
                //探尋此節(jié)點的下一層“通路”
                ts = accesses.get(t);
                if (ts != null){
                    //如果此節(jié)點下一層有“通路”，便將此節(jié)點放入棧中
                    stack.push(t);
                    //并改變標志位，跳過出棧操作
                    index++;
                }
                break;
            }
            //如果此節(jié)點沒有下一層可以訪問，則觸發(fā)出棧操作，去上一層尋找
            if (index == 0){
                T pop = stack.pop();
                ts = accesses.get(pop);
            }
        }
        return list;
    }
}

針對這個DFS，我們大致闡述一下思路。

首先明確一點，圖的遍歷是需要確定一個起始節(jié)點的。(這也是我們這個DFS方法的參數(shù))。

首先我們需要一個棧，這個棧是完成我們“深度優(yōu)先”的主要工具

何為“深度優(yōu)先”，當我們在訪問過程中，遇到分支了，優(yōu)先選擇下一層的分支進行訪問。

我們利用棧“先進后出”的特性，將當前節(jié)點的“上級”們先逐層保存起來。確保我們能向上逐層找到他們。

我們開始進行訪問，每層訪問一個節(jié)點便向下層訪問，當我們發(fā)現(xiàn)不能向下了(與當前節(jié)點相連的節(jié)點都被訪問過了)，就往上倒一層，然后重復上述過程。

測試

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());
    }

結(jié)果：

[5, 1, 2, 4, 3]

以上就是關于“Java數(shù)據(jù)結(jié)構(gòu)：有向圖的深度優(yōu)先遍歷”介紹，大家如果想了解更多相關知識，不妨來關注一下動力節(jié)點的Java在線學習技術(shù)文檔，里面的課程內(nèi)容由淺到深，很適合沒有基礎的小伙伴學習，希望對大家能夠有所幫助。