无向图

无向图

边仅仅连接两个顶点

常见图的存储结构有两种：邻接矩阵和邻接表

邻接矩阵

1.使用一个v*v的二维数组int[V][V] adj，把索引的值看做顶点
2.如果顶点v和顶点w相连，我们只需要将adj[v][w]和adj[w][v]的值设置为1，否则设置为0

邻接表

1.使用一个大小为V的数组 Queue[V] adj,把索引看做顶点
2.每个索引处adj[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的顶点

//无向图
public class Graph {
    private final int V;  //顶点数目
    private int E;   //边的数目
    private Queue<Integer>[] adj;   //邻接表

    public Graph(int V) {
        this.V = V;   //初始化顶点的数量
        this.E=0;  //初始化边的数量
        this.adj=new Queue[V];  //初始化领接表

        //初始化邻接表中的空队列
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new Queue<Integer>();
        }
    }

    //获取顶点数目
    public int V(){
        return V;
    }

    //获取边的数目
    public int E(){
        return E;
    }

    //向图中添加一条边v-w
    public void addEdge(int v,int w){
        //把v添加到w的邻接表中
        adj[w].enqueue(v);
        //把w添加到v的邻接表中
        adj[v].enqueue(w);

        //边数加1
        E++;
    }

    //获取和顶点v相邻的所有顶点
    public Queue<Integer> adj(int v){
        return adj[v];
    }
}

深度优先搜索

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。

//深度优先搜索
public class DepthFirstSearch {
    private boolean[] marked;  //索引代表顶点，值代表当前顶点是否被搜索
    private int count;  //记录有多少个顶点与s顶点相同

    //构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻接点
    public DepthFirstSearch(Graph G,int s) {
        //创建一个和图的定点数一样大小的布尔数组
        marked=new boolean[G.V()];
        this.count=0;
        //搜索g图中与顶点s相同的所有顶点
        dfs(G,s);
    }

    //使用深度优先搜索找出G图中v顶点的所有相邻顶点
    private void dfs(Graph G,int v){
        //把当前顶点标记为已搜索
        marked[v]=true;
        //遍历v顶点的邻接点，得到每一个顶点w
        for (Integer w :G.adj(v)){
            //如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
            if(!marked[w]){
                dfs(G,w);
            }
        }
        //相通的顶点数量加1
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w){
        return marked[w];
    }

    //获取与结点相通的所有顶点的总数
    public int count(){
        return count;
    }
}

广度优先搜索

//广度优先搜索
public class BreadthFirstSearch {
    private boolean[] marked;  //索引代表顶点，值表示当前顶点是否已经被搜索
    private int count;  //记录有多少个顶点与s顶点相遇
    private Queue<Integer> waitSearch; //用来存储待搜索邻接表的点

    //构建广度优先搜索对象，使用广度优先搜索找出图G中s顶点的所有相邻结点
    public BreadthFirstSearch(Graph G,int s){
        //创建一个和图顶点一样大小的布尔数组
        marked=new boolean[G.V()];
        this.count=0;
        //初始化待搜索的队列
        waitSearch=new Queue<Integer>();
        //搜索G图中与顶点s相同的所有顶点
        dfs(G,s);

    }

    //使用广度优先搜索找出G图中v顶点的所有相邻结点
    private void dfs(Graph G,int v){
        //把当前顶点v标记为已搜索
        marked[v]=true;
        //把当前顶点v放入到队列中，等待搜索它的邻接点
        waitSearch.enqueue(v);
        //使用while循环从队列中拿出待搜索的顶点wait，进行搜索邻接表
        while (!waitSearch.isEmpty()){
            Integer wait=waitSearch.dequeue();
            //遍历wait顶点的邻接表，得到每一个顶点w
            for (Integer w: G.adj(wait)){
                //如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他节点
                if (!marked[w]){
                    dfs(G,w);
                }
            }
        }
        //相通的顶点数量加1
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w){
        return marked[w];
    }

    //获取和顶点s相通的所有顶点总和
    public int count(){
        return count;
    }
}

路径查找

//路径查找
public class DepthFirstPaths {
    private boolean[] marked;  //索引代表当前顶点，值表示当前顶点是否已经被搜索
    private int s;  //起点
    //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个结点
    private int[] edgeTo;

    //构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
    public DepthFirstPaths(Graph G,int s){
        //创建一个和图顶点数一样大小的布尔数组
        marked=new boolean[G.V()];
        //创建一个和图顶点数一样大小的整形数组
        edgeTo=new int[G.V()];
        //初始化顶点
        this.s=s;
        //搜索G图中起点为s是所有路径
        dfs(G,s);
    }

    private void dfs(Graph G,int v){
        //把当前结点标记为已搜索
        marked[v]=true;
        //遍历v的邻接表，得到每一个顶点w
        for(Integer w: G.adj(v)){
            //如果当前顶点w没有被搜索过，则将edgeTo[w]设置为v,表示w的前一个顶点
            //为v,并递归搜索与w相通的其他顶点
            if(!marked[w]){
                edgeTo[w]=v;
                dfs(G,w);
            }
        }
    }

    //判断w顶点与s顶点是否存在路径
    public boolean hasPathTo(int v){
        return marked[v];
    }

    //找出从起点s到顶点v的路径
    public Stack<Integer> pathTo(int v){
        //如果v顶点和s顶点不连通，直接返回null
        if(!hasPathTo(v)){
            return null;
        }
        //创建路径中经过顶点的容器
        Stack<Integer> path=new Stack<Integer>();
        for (int x=v;x!=s;x=edgeTo[x]){
            path.push(x);
        }
        //把起点s放入容器
        path.push(s);
        return path;
    }
}