有向图（directed graph）DFS/BFS及实现（Java）

DFS/BFS
DFS——深度优先搜素，递归；
BFS——广度优先搜索，队列；


java代码
  使用如下所示的有向图作为示例
  GraphSearch.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GraphSearch {
    private List res;
    private int[] marked;
    private Graph graph;
    private List BFSQueue;

    GraphSearch(Graph graph) {
        this.graph = graph;
    }

    private void init() {
        
        res = new ArrayList<>();
        this.BFSQueue = new ArrayList<>();
        this.marked = new int[graph.V()];
        Arrays.fill(marked, 0);
    }

    public List DFS() {
        
        init();
        DFSHelper(0);
        return res;
    }

    private void DFSHelper(int curV) {
        res.add(curV);
        marked[curV] = 1;
        visitUnmarked(curV);
        return;
    }

    private void visitUnmarked(int v) {
        
        if (graph.adj(v) == null) {
            return;
        }
        for (int adjV : graph.adj(v)) {
            if (marked[adjV] == 0) {
                DFSHelper(adjV);
            }
        }
    }

    public List BFS() {
        init();
        BFSHelper(0);
        return res;
    }

    private void BFSHelper(int sourceV) {
        BFSQueue.add(sourceV);
        marked[sourceV] = 1;
        while (BFSQueue.size() != 0) {
            int curV = BFSQueue.remove(0);
            res.add(curV);
            if (graph.adj(curV) != null) {
                for (int adjV : graph.adj(curV)) {
                    if (marked[adjV] == 0) {
                        BFSQueue.add(adjV);
                        marked[adjV] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph test = new Graph(7);
        test.addEdge(0, 1);
        test.addEdge(0, 2);
        test.addEdge(1, 3);
        test.addEdge(1, 4);
        test.addEdge(2, 4);
        test.addEdge(2, 5);
        test.addEdge(3, 6);
        test.addEdge(4, 6);
        test.addEdge(5, 6);
        GraphSearch t = new GraphSearch(test);
        System.out.println("DFS遍历：" + t.DFS());
        System.out.println("BFS遍历：" + t.BFS());
    }
}

  Graph.java

import java.util.ArrayList;
import java.util.List;

public class Graph {
    
    private List[] ver;

    Graph(int v) {
        
        ver = new List[v];
    }

    public void addEdge(int v, int w) {
        
        if (ver[v] == null) {
            ver[v] = new ArrayList<>();
        }
        ver[v].add(w);
    }

    Iterable adj(int v) {
        
        return ver[v];
    }

    public int V() {
        
        return ver.length;
    }

    public int E() {
        
        int res = 0;
        for (int i = 0; i < ver.length; i++) {
            if (ver[i] == null) {
                ver[i] = new ArrayList<>();
            }
            res += ver[i].size();
        }
        return res;
    }
}