无向图

1. 图的几种表示方法

我们希望表示图的数据结构具有以下特点

• 为可能在应用中碰到的各种类型的图预留出足够的空间
• 图的实例方法的实现一定要快----他们是开发处理图的各种用例的基础

① 邻接矩阵
使用V×V的boolean矩阵，当顶点V和顶点W之间有相连的边时，定义V行W列的元素为true

• 但这种表示方法不能满足第一个条件，对于包含上百万个节点的图，V²个布尔值所需要的空间是不能满足的
• 且无法表示平行边
  

② 边的数组
使用Edge类来表示边，里面存储边两边的点
但是不满足第二个条件，如果我们想找一个顶点的相邻顶点需要遍历所有的Edge实例

③ 邻接表数组
使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表

1.1 邻接表数组

1.1.1 Graph的数据类型

import java.util.Iterator;

public class Graph {
    private Vertex[] verticesList;//邻接表数组
    private int V;//顶点数目
    private int E;//边数

    class Vertex implements Iterable<Integer>{
        private Node first;
        private Node last;

        class Node{
            int item;//顶点从1开始数字编号
            Node next;//下一个
        }

        void add(int newPoint){//这里添加到头(也可以实现添加到尾) 常数时间
            Node oldFirst = first;
            first = new Node();
            first.item = newPoint;
            first.next = oldFirst;
        }

        @Override
        public Iterator<Integer> iterator() {
            return null;
        }

        private class ListIterator implements Iterator<Integer>{
            private Node current = first;
            @Override
            public boolean hasNext() {
                return current!=null;
            }

            @Override
            public Integer next() {
                int item = current.item;
                current = current.next;
                return item;
            }

            @Override
            public void remove() {

            }
        }

    }
    public Graph(int V){//初始化
        this.V = V;
        this.E = 0;
        verticesList = new Vertex[V];
        for(int i = 0; i<V; i++){
            verticesList[i] = new Vertex();
        }
    }

    /**
     * 添加边
     * @param v 顶点
     * @param w 顶点
     */
    public void addEdge(int v, int w){
        verticesList[v].add(w);
        verticesList[w].add(v);
        E++;
    }

    public int getV(){
        return V;
    }

    /**
     *
     * @param v
     * @return 实现了Iterable接口
     */
    public Iterable<Integer> verticesList(int v){
        return verticesList[v];
    }

}

1.1.2 深度优先搜索

通过深度优先搜索寻找从顶点s到其他顶点的路径(如果连通)

将图的表示和方法的实现分开写，一个方法作为一个单独的类，用例可以创建相应的对象来完成任务

package GraphPag;

import java.util.Stack;

public class DepthFirstSearch {
    private boolean[] marked;//marked[m]=true表示连接
    private int count;//判断是不是连通图
    private int[] edgeTo;//edgeTo[1] = 0 表示去顶点1的前一个顶点是0
    private int s;//起点
    /**
     * 深度优先寻找和S连通的所有顶点
     * @param G 图
     * @param s 顶点
     */

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

    void dfs(Graph G, int v){
        marked[v] = true;//到达顶点v
        count++;
        Iterable<Integer> verticesList = G.verticesList(v);
        for (Integer integer : verticesList) {
            if(!marked[integer]){
                edgeTo[integer] = v;
                dfs(G,integer);
            }
        }
    }

    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;
    }
}

以下是代码测试，输出顶点s到其他所有顶点的一条路径(如果能到达)

 Graph G = new Graph(V);
        DepthFirstSearch search = new DepthFirstSearch(G,s);
        for(int v = 0; v<G.getV(); v++){
            System.out.println(s+"to"+v+":");
            if(search.hasPathTo(v)){
                for(int x:search.pathTo(v)){
                    if(x != s){
                        System.out.print("->"+x);
                    }else {
                        System.out.print(x);
                    }
                }
            }
            System.out.println("-------------------");
        }
      

1.1.3 广度优先搜索

广度优先搜索适合寻找从起点s到达目标点v的最短路径
深度优先搜索就像一个人在走迷宫，而广度优先搜索就像一个顶点上不同的人往不同的分岔口走去走迷宫

void bfs(Graph G, int s){
        LinkedList<Integer> queue = new LinkedList<>();
        marked[s] = true;
        queue.add(s);
        while (!queue.isEmpty()){
            Integer v = queue.poll();
            for(int w:G.verticesList(v)){
                if(!marked[w]){
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.add(w);
                }
            }
        }
    }