Java 目錄遍歷兩大算法實戰：非遞歸廣度優先 vs 遞歸深度優先性能對比

問題背景

文件系統遍歷是 Java IO 常見需求。本文對比兩種經典實現：非遞歸廣度優先（隊列） 與 遞歸深度優先（棧/調用棧），並通過實測數據分析性能差異。

方案 A：非遞歸廣度優先遍歷（LinkedList 隊列）

import java.io.File;
import java.util.LinkedList;

public class FileSystemBFS {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        LinkedList<File> queue = new LinkedList<>();
        File root = new File("C:\\Program Files\\Java\\");
        
        File[] files = root.listFiles();
        if (files != null) {
            for (File f : files) {
                if (f.isDirectory()) queue.add(f);
                else System.out.println(f.getAbsolutePath());
            }
        }

        File current;
        while (!queue.isEmpty()) {
            current = queue.removeFirst();
            File[] children = current.listFiles();
            if (children == null) continue;  // 權限不足等情況
            
            for (File f : children) {
                if (f.isDirectory()) queue.add(f);
                else System.out.println(f.getAbsolutePath());
            }
        }
        System.out.println("耗時: " + (System.currentTimeMillis() - start) + "ms");
    }
}

特點分析

• 顯式隊列：將待處理目錄入隊，逐層展開，屬於 BFS（廣度優先搜索）
• 無棧溢出風險：極深目錄結構也不會導致 StackOverflowError
• 內存佔用：隊列峰值約等於最寬一層的目錄數 × 引用大小

方案 B：遞歸深度優先遍歷（隱式調用棧）

import java.io.File;
import java.util.ArrayList;

public class FileSystemDFS {
    private static ArrayList<String> fileList = new ArrayList<>();

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        refreshFileList("C:\\Program Files\\Java\\");
        System.out.println("耗時: " + (System.currentTimeMillis() - start) + "ms");
    }

    public static void refreshFileList(String path) {
        File dir = new File(path);
        File[] files = dir.listFiles();
        if (files == null) return;  // 關鍵防禦：權限不足返回 null

        for (File f : files) {
            if (f.isDirectory()) {
                refreshFileList(f.getAbsolutePath());  // 遞歸調用
            } else {
                String name = f.getAbsolutePath().toLowerCase();
                System.out.println("---" + name);
                fileList.add(f.getAbsolutePath());
            }
        }
    }
}

特點分析

• 代碼極簡：利用方法調用棧天然實現 DFS（深度優先搜索）
• 棧溢出風險：目錄深度超過 JVM 棧限制（默認 ~1024 幀）會拋出 StackOverflowError
• 局部性好：連續訪問同一分支文件，利於操作系統文件系統緩存

性能實測對比（同一環境、同一目錄樹）

核心優化建議

1. 必須檢查 listFiles() == null：權限不足、非目錄、IO 錯誤均返回 null，直接遍歷會拋 NPE。
2. 大量文件場景：考慮 Files.walkFileTree() (NIO.2) + 並行流，或使用 File.listFiles(FileFilter) 早期過濾。
3. 遞歸深度可控：若確定業務目錄深度 < 500 層，遞歸優先；否則改用顯式棧模擬遞歸。
4. 結果收集：避免在遍歷中直接打印/處理，先收集路徑列表，後續批量處理，便於單元測試與異步化。

現代替代方案：NIO.2 Files.walkFileTree

Files.walkFileTree(Paths.get(rootPath), new SimpleFileVisitor<Path>() {
    @Override
    public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {
        System.out.println(file.toAbsolutePath());
        return FileVisitResult.CONTINUE;
    }
    @Override
    public FileVisitResult visitFileFailed(Path file, IOException exc) {
        // 統一錯誤處理
        return FileVisitResult.CONTINUE;
    }
});

優勢：自動處理循環鏈接、權限錯誤、屬性預取；支持 maxDepth 限制深度；Java 8+ 可配合 Stream API 並行處理。

結論

遞歸 DFS 在常規目錄結構下性能略優且代碼最簡潔，是首選方案。非遞歸 BFS 適合極深目錄或需層級控制的場景。生產環境建議直接使用 Files.walkFileTree，獲得健壯性與現代 API 支持的雙重保障。