package com.zhiyiyo.graph;

/**
 * 無(wú)向圖
 */
public interface Graph {
    /**
     * 返回圖中的頂點(diǎn)數(shù)
     */
    int V();

    /**
     * 返回圖中的邊數(shù)
     */
    int E();

    /**
     * 向圖中添加一條邊
     * @param v 頂點(diǎn) v
     * @param w 頂點(diǎn) w
     */
    void addEdge(int v, int w);

    /**
     * 返回所有相鄰頂點(diǎn)
     * @param v 頂點(diǎn) v
     * @return 所有相鄰頂點(diǎn)
     */
    Iterable<Integer> adj(int v);
}

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;

/**
 * 使用鄰接表實(shí)現(xiàn)的無(wú)向圖
 */
public class LinkGraph implements Graph {
    private final int V;
    private int E;
    private LinkStack<Integer>[] adj;

    public LinkGraph(int V) {
        this.V = V;
        adj = (LinkStack<Integer>[]) new LinkStack[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new LinkStack<>();
        }
    }

    @Override
    public int V() {
        return V;
    }

    @Override
    public int E() {
        return E;
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].push(w);
        adj[w].push(v);
        E++;
    }

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

package com.zhiyiyo.collection.stack;

import java.util.EmptyStackException;
import java.util.Iterator;

/**
 * 使用鏈表實(shí)現(xiàn)的堆棧
 */
public class LinkStack<T> {
    private int N;
    private Node first;

    public void push(T item) {
        first = new Node(item, first);
        N++;
    }

    public T pop() throws EmptyStackException {
        if (N == 0) {
            throw new EmptyStackException();
        }

        T item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public Iterator<T> iterator() {
        return new ReverseIterator();
    }

    private class Node {
        T item;
        Node next;

        public Node() {
        }

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }


    private class ReverseIterator implements Iterator<T> {
        private Node node = first;

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public T next() {
            T item = node.item;
            node = node.next;
            return item;
        }

        @Override
        public void remove() {
        }
    }
}

package com.zhiyiyo.graph;

public interface Search {
    /**
     * 起點(diǎn) s 和 頂點(diǎn) v 之間是否連通
     * @param v 頂點(diǎn) v
     * @return 是否連通
     */
    boolean connected(int v);

    /**
     * 返回與頂點(diǎn) s 相連通的頂點(diǎn)個(gè)數(shù)（包括 s）
     */
    int count();

    /**
     * 是否存在從起點(diǎn) s 到頂點(diǎn) v 的路徑
     * @param v 頂點(diǎn) v
     * @return 是否存在路徑
     */
    boolean hasPathTo(int v);

    /**
     * 從起點(diǎn) s 到頂點(diǎn) v 的路徑，不存在則返回 null
     * @param v 頂點(diǎn) v
     * @return 路徑
     */
    Iterable<Integer> pathTo(int v);
}

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;


public class DepthFirstSearch implements Search {
    private boolean[] marked;
    private int[] edgeTo;
    private Graph graph;
    private int s;
    private int N;

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

    /**
     * 遞歸實(shí)現(xiàn)的深度優(yōu)先搜索
     *
     * @param v 頂點(diǎn) v
     */
    private void dfs(int v) {
        marked[v] = true;
        N++;
        for (int i : graph.adj(v)) {
            if (!marked[i]) {
                edgeTo[i] = v;
                dfs(i);
            }
        }
    }

    /**
     * 堆棧實(shí)現(xiàn)的深度優(yōu)先搜索
     */
    private void dfs() {
        Stack<Integer> vertexes = new LinkStack<>();
        vertexes.push(s);
        marked[s] = true;

        while (!vertexes.isEmpty()) {
            Integer v = vertexes.pop();
            N++;

            // 將所有相鄰頂點(diǎn)加到堆棧中
            for (Integer i : graph.adj(v)) {
                if (!marked[i]) {
                    edgeTo[i] = v;
                    marked[i] = true;
                    vertexes.push(i);
                }
            }
        }
    }

    @Override
    public boolean connected(int v) {
        return marked[v];
    }

    @Override
    public int count() {
        return N;
    }

    @Override
    public boolean hasPathTo(int v) {
        return connected(v);
    }

    @Override
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new LinkStack<>();

        int vertex = v;
        while (vertex != s) {
            path.push(vertex);
            vertex = edgeTo[vertex];
        }

        path.push(s);
        return path;
    }
}

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.queue.LinkQueue;

public class BreadthFirstSearch implements Search {
    private boolean[] marked;
    private int[] edgeTo;
    private Graph graph;
    private int s;
    private int N;

    public BreadthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        marked = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        bfs();
    }

    private void bfs() {
        LinkQueue<Integer> queue = new LinkQueue<>();
        marked[s] = true;
        queue.enqueue(s);

        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            N++;

            for (Integer i : graph.adj(v)) {
                if (!marked[i]) {
                    edgeTo[i] = v;
                    marked[i] = true;
                    queue.enqueue(i);
                }
            }
        }
    }
}

package com.zhiyiyo.collection.queue;


import java.util.EmptyStackException;


public class LinkQueue<T> {
    private int N;
    private Node first;
    private Node last;

    public void enqueue(T item) {
        Node node = new Node(item, null);
        if (++N == 1) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
    }

    public T dequeue() throws EmptyStackException {
        if (N == 0) {
            throw new EmptyStackException();
        }

        T item = first.item;
        first = first.next;
        if (--N == 0) {
            last = null;
        }
        return item;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private class Node {
        T item;
        Node next;

        public Node() {
        }

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}