（四）图

无向图

图：是由一组顶点和一组能够将两个顶点相连的边组成的
自环：即可一条龙连接一个顶点和其自身的边
平行边：连接同一对顶点的两条边
常将含有平行边的图称为多重图，而没有平行边或自环的图称为简单图
相邻：当两顶点通过一条边相连时，称这两个顶点是相邻的，并称连接依附于这两个顶点
度数：顶点的度数就是依附于它的边数
子图：由所有边的一个子集以及这些边依附的所有顶点组成的图
路径是由边顺序连接的一系列顶点；简单路径是一条没有重复顶点的路径
环是一条至少含有一条边且起点和终点相同的路径；简单环（除了起始和终点必须相同外）是一条不含有重复顶点和边的环
路径和环的长度为其中包含的边数
连通图：若从任意一个顶点都存在一条路径到达另一个任意顶点；非连通图：由若干连通部分组成，它们都是其极大连通子图
树是无环连通图；互不相连的树组成的集合称为森林；连通图的生成树是它的一幅子图，它含有图中所有顶点且是一棵树；图的生成树森林是它的所有连通子图的生成树的集合
当且仅当V个结点的图G满足下列5个条件之一时是树
- G有V-1条边且不含环
- G有V-1条边且是连通的
- G是连通的，但删除任意一条边都会使它不再连通
- G是无环图，但添加任意一条边都会产生一条环
- G中任意一对顶点之间仅存在一条简单路径
二分图中每条边连接的两个顶点分别属于不同部分

图的数据结构

必须为可能在应用中碰到的各种类型的图预留出足够空间
Graph 实例方法的实现一定要快

三种图的表示方法：

邻接矩阵：VxV 布尔矩阵，当顶点v和顶点w之间有相连的边时，定义v行w列元素值为true，否则为false。该方法不满足第一个条件，上百万顶点的图所需空间不能满足。（邻接矩阵也无法表示平行边）
边的数组：使用一个Edge类，含有两个int实例变量。该方法简洁但不满足第二个条件——查找结点的相邻结点需要检查图中所有边
邻接表数组：使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表。该数据结构能同时满足两个条件。

非稠密图标准表示称为邻接表，在该数据结构中每条边都会出现两次，其实现有如下性能：

空间和V+E成正比
添加一条边所需时间为常数
遍历顶点v所有相邻顶点所需时间和v度数成正比（处理每个相邻顶点所需时间为常数）

当需要添加/删除顶点时，使用符号表（ST）来代替由顶点索引构成的数组；当需要删除一条边/检查图是否含有边v-w时，可以用SET代替Bag来实现邻接表。这种方法称为邻接集。

图处理算法的设计模式

图的表示和实现分离

深度优先搜索（栈）

在访问其中任何一个顶点时：

将它标记为已访问
递归地访问它所没有被标记过的邻居节点

public class DepthFirstSearch {
    private boolean[] marked;
    private int count;
    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);
            }
        }
    }
    public boolean marked(int w) {
        return marked[w];
    }
    public int count() {
        return count;
    }
}

深度优先搜索标记与起点相连通的所有顶点所需时间和顶点度数之和成正比

寻找路径

基于深度优先搜索查找路径（从给定起点s到它连通的所有顶点的路径）：

public class DepthFirstPaths {
    private boolean[] marked;
    /**
     * 起点
     */
    private final int s;
    /**
     * 该顶点到一个顶点的已知路径上的最后一个顶点
     */
    private int[] edgeTo;
    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(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 dfs(Graph g, int v) {
        marked[v] = true;
        for (Integer w : g.adj(v)) {
            if (!marked[w]){
                edgeTo[w] = v;
            }
        }
    }
}

深度优先搜索得到从给定起点到任意标记顶点的路径所需时间和路径长度成正比

广度优先搜索（队列）

单点最短路径。若s到v存在一条路径，找出最短那条（边数最少）。
要找到从s到v的最短路径，从s开始，在所有由一条边就可以到达的顶点中寻找v，若找不到则继续在与s距离两条边的所有顶点中查找v，如此一直进行。

public class BreadthFirstPaths {
    /**
     * 到达该店的最短路径是否已知
     */
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;
    public BreadthFirstPaths(Graph G, int s) {
        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 LinkedBlockingDeque<>();
        marked[s] = true;
        queue.add(s);
        //一层一层遍历
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (Integer w : G.adj(v)) {
                if (!marked[w]) {
                    queue.add(w);
                    edgeTo[w] = v;
                    marked[w] = true;
                }
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack<>();
        path.push(v);
        for (int x = v; x != s; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(s);
        return path;
    }
}

广度优先搜索所需时间在最坏情况下和 V+E 成正比

Why is the time complexity of both DFS and BFS O( V + E )

连通分量

DFS可以应用找出一幅图所有连通分量

public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;
    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int s = 0; s < G.V(); s++) {
            if (!marked[s]) {
                //一次深度优先搜索就是一个连通分量
                dfs(G, s);
                count++;
            }
        }
    }
    private void dfs(Graph g, int s) {
        marked[s] = true;
        //同一连通分量同一编号
        id[s] = count;
        for (Integer v : g.adj(s)) {
            if (!marked[v]) {
                dfs(g, v);
            }
        }
    }
    public int count(){
        return count;
    }
    public boolean connected(int w ,int v){
        return id[w] == id[v];
    }
    public int id(int v){
        return id[v];
    }
}

CC中基于DFS搜索解决图连通性问题相比：理论上，DFS 搜索比 union-find 快，因为它能保证所需时间是常数而 union-find 不行；但实际应用中，union-find 更快，因为它不需完整构造并表示一幅图。但DFS必须对图进行预处理，在只需判断连通性或只需完成大量连通性查询和插入操作混合等类似任务时，更倾向union-find，而DFS更适合实现抽象数据类型，它能更有效利用已有数据结构。

使用深度优先搜索处理图的其它实例
- 判断 G 是否为无环图
  1
  2
- G 是二分图吗？（双色问题）
  1
  2

无向图