无向图DFS和BFS

基本结构

public class Graph {
    private int V;  //顶点数
    private int E;  //边数
    private ArrayList<Integer>[] adj;

    public Graph(int v) {
        V = v;
        E = 0;
        adj = new ArrayList[v];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int v, int w) {
        if (v < 0 || v > V) {
            throw new IndexOutOfBoundsException();
        }
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }

    public int getE() {
        return E;
    }

    public int getV() {
        return V;
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

DFS深度优先遍历

public class DepthFirstSearch {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;
    private int count;

    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.getV()];
        edgeTo = new int[G.getV()];
        this.s = s;
        dfs(G, s);
    }

    public boolean marked(int w) {
        return marked[w];
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x]) path.push(x);
        path.push(s);
        return path;
    }

    public int count() {
        return count;
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        count++;
        for (int w : G.adj(v)) {
            if (!marked[w]) dfs(G, w);
        }
    }
}

BFS广度优先遍历

public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;

    public BreadthFirstPaths(Graph G, int s) {
        marked = new boolean[G.getV()];
        edgeTo = new int[G.getV()];
        this.s = s;
        bfs(G, s);
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x]) path.push(x);
        path.push(s);
        return path;
    }

    private void bfs(Graph G, int v) {
        Queue<Integer> queue = new ConcurrentLinkedQueue<>();
        marked[s] = true;
        queue.offer(s);
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            for (int w : G.adj(tmp)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.offer(w);
                }
            }
        }
    }
}

符号图

public class SymbolGraph {
    private Map<String, Integer> map;
    private String[] keys;
    private Graph G;

    public SymbolGraph(InputStream stream, String sp) throws IOException {
        map = new HashMap<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(stream));
        String data = null;
        while ((data = br.readLine()) != null) {
            String[] a = data.split(sp);
            for (int i = 0; i < a.length; i++) {
                if (!map.containsKey(a[i])) map.put(a[i], map.size());
            }
        }

        keys = new String[map.size()];
        for (String name : map.keySet()) {
            keys[map.get(name)] = name;
        }

        G = new Graph(map.size());
        while ((data = br.readLine()) != null) {
            String[] a = data.split(sp);
            int v = map.get(a[0]);
            for (int i = 1; i < a.length; i++) {
                G.addEdge(v, map.get(a[i]));
            }
        }
    }

    public Graph getG() {
        return G;
    }

    public int index(String s){ return map.get(s); }

    public String name(int v){ return keys[v]; }
}