package Graph;

import LinearLIst.bag.Bag;

import edu.princeton.cs.algs4.In;

public class Graph {

    private final int V;        //顶点数目

    private int E;              //边的数目

    private Bag<Integer>[] adj;     //邻接表

    /*创建一个包含V个顶点但是不包含边的图*/

    public Graph(int V){

        this.V=V;

        this.E=0;

        adj=(Bag<Integer>[]) new Bag[V];        //创建邻接表

        for(int v=0;v<V;v++)                    //将所有链表初始化为空

            adj[v]=new Bag<Integer>();

    }

    /*从标准输入流读入一幅图*/

    public Graph(In in){

        this(in.readInt());         //读取V并将图初始化

        int E=in.readInt();         //读取E

        for (int i=0;i<E;i++){

            int v=in.readInt();     //读取一个顶点

            int w=in.readInt();     //读取另一个顶点

            addEdge(v,w);           //添加一条连接他们的边

        }

    }

    /**

     * 返回图中顶点（结点）数目

     */

    public int V(){

        return V;

    }

    /**

     *返回图中边的数目

     */

    public int E(){

        return E;

    }

    /*向图中增加一条边v-w */

    public void addEdge(int v,int w){

        adj[v].add(w);      //将W添加到V的链表中

        adj[w].add(v);      //将V添加到W的链表中

        E++;

    }

    /*和v相邻的所有顶点*/

    /*返回的是该点的邻接表*/

    public Iterable<Integer> adj(int v){

        return adj[v];

    }

    /*下面是最常用的图处理操作*/

    /*计算v的度数*/

    public static int degree(Graph G,int v){

        int degree=0;

        for (int w:G.adj(v))

            degree++;

        return degree;

    }

    /*计算所有顶点的最大度数*/

    public static int maxDegree(Graph G){

        int max=0;

        for (int v=0;v<G.V();v++){

            if (degree(G,v)>max)

                max=degree(G,v);

        }

        return max;

    }

    /*计算所有顶点的平均度数*/

    public static double avgDegree(Graph G){

        return 2*G.E()/G.V();

    }

    /*计算子环的个数*/

    public static int numberOfSelfLoops(Graph G){

        int count=0;

        for (int v=0;v<G.V();v++)

            for (int w:G.adj(v))

                if (v==w)

                    count++;

        return count/2;

    }

    /*图的邻接表的字符串表示*/

    public String toString(){

        String s=V+" vertices,"+E+" edges\n";

        for (int v=0;v<V;v++){

            s+=v+": ";

            for (int w:this.adj(v))

                s+=w+" ";

            s+="\n";

        }

        return s;

    }

}

package Graph;

public class DepthFirstSearch {

    /*marked数组的索引代表一个顶点，元素值代表该点与起点s是否联通*/

    private boolean[] marked;

    /*与s联通的点的总数*/

    /*需要注意的是，这里不是指与s相邻的点的数量*/

    /*s与自己是联通的*/

    /*即s所在的联通子图中顶点的数量*/

    private int count;

    /**

     *

     * @param G 一个图

     * @param s s代表图中的起点

     */

    public DepthFirstSearch(Graph G,int s){

        marked=new boolean[G.V()];

        dfs(G,s);

    }

    private void dfs(Graph G,int v){

        marked[v]=true;

        count++;

        for(int w:G.adj(v)){

            if (!marked[w])

                dfs(G,w);

        }

    }

    /**

     *

     * @param w：输入一个顶点

     * @return 该顶点是否与起点s联通

     */

    public boolean marked(int w){

        return marked[w];

    }

    /**

     *

     * @return 与s联通的点的总数（所在联通子图的节点数）

     */

    public int count(){

        return count;

    }

}

package Graph;

import LinearLIst.stack.Stack;

import edu.princeton.cs.algs4.In;

public class DepthFirstPaths {

    private boolean[] marked;

    private int[] edgeTo;

    private final int s;

    public DepthFirstPaths(Graph G,int s){

        marked=new boolean[G.V()];

        edgeTo=new int[G.V()];

        this.s=s;

        dfs(G,s);

    }

    private void dfs(Graph G,int v) {

        marked[v] = true;

        for (int w : G.adj(v)) {

            if (!marked[w]) {

                edgeTo[w] = v;

            }

        }

    }

    public boolean hasPathTo(int v) {

        return marked[v];

    }

    public Iterable<Integer> pathTo(int v){

        if (!hasPathTo(v))

            return null;

        Stack<Integer> path=new Stack<Integer>();

        for(int x=v;x!=s;x=edgeTo[x])

            path.push(x);

        path.push(s);

        return path;

    }

}

package Graph;

import LinearLIst.queue.Queue;

public class BreadthFirstSearch {

    /*从起点s到达某个顶点的最短路径是否已知*/

    private boolean[] marked;

    /*到达该顶点的已知路径上的最后一个顶点*/

    /*“最短路径的最后一条边”*/

    private int[] edgeTo;

    /*起点*/

    private final int s;

    public BreadthFirstSearch(Graph G,int s){

        /*V()返回的是图中顶点的数目*/

        marked=new boolean[G.V()];

        edgeTo=new int[G.V()];

        this.s=s;

        bfs(G,s);

    }

    private void bfs(Graph G,int s){

        Queue<Integer> queue=new Queue<Integer>();

        marked[s]=true;             //标记起点

        queue.enqueue(s);               //将其加入队列

        while(!queue.isEmpty()){

            int v=queue.dequeue();   //从队列中删去下一顶点

            for (int w:G.adj(v)){

                edgeTo[w]=v;        //保存最短路径的最后一条边

                marked[w]=true;     //标记它。因为最短路径已知

                queue.enqueue(w);       //将它加入到队列中

            }

        }

    }

    /*判断一个顶点与s是否联通*/

    public boolean hasPathTo(int v){

        return marked[v];

    }

    /*得到一条从s到v的路径*/

    /*确保没有从其它s到v的路径所含的边比这条路径更少*/

    /*

    public Iterable<Integer> pathTo(int v){

        if(!hasPathTo(v))

            return null;

        Stack<Integer> path=new Stack<Integer>();

        for(int x=v;x!=s;x=edgeTo[x])

            path.push(x);

        path.push(s);

        return path;

    }

    */

}