图论——基础

如何确定两点连通？如何确定两点有最短路径？最短路径是什么？任务的优先调度如何安排？如何在最短时间内安排有时间限制的任务优先调度？人际关系或是社交网络的关系该如何表达？……

如果你想探寻以上类似的问题，那么图的模型对你非常有帮助。

精力有限，图论无法像之前一样，详细解释算法的推导和原理，感兴趣的朋友请自行查阅资料，推荐《算法导论》和《Algorithm》。

YifHong

• 图由边E和顶点V组成。
• 图最重要的四种模型分别是无向图、有向图、加权图、加权有向图，因而边对应为无向边、有向边、加权无向边、加权有向边，顶点则为边的顶点。
• 将各个顶点和边组合起来，可以形成许多大小不一的树或环，进而组成森林，构成图。

这里先介绍几个基本的概念：

1. 自环：一条连接一个顶点和其自身的边。
2. 平行边：连接同一对顶点的两条边。
3. 树：是一幅无环连通图。
4. 稠密图：指的是顶点大部分互相连接的图。
5. 稀疏图：指的是顶点之间连接较少的图。(v ~cV)
6. 度数：一个顶点所连接的边的数目。

基础数据结构

无向图 Graph

我们可以通过邻接表或邻接矩阵来表示无向图。

邻接表

大部分情况下，我们研究的是稀疏图，邻接表要优于邻接矩阵。某些情况下，邻接矩阵优于邻接表。比如在稠密图中。

• 邻接表是一种数组+背包Bag（一种无序的链表存储结构）组成的数据结构。

性能

存储空间 V+E

添加边的时间为常数

遍历顶点v的邻接表时间与v的度数成正比

下面展示了无向图的基本数据结构，其中的背包Bag实现：

Graph 无向图的数据结构Graph.java

public class Graph {
    private final int V;        //num of vertex, 顶点的数目
    private int E;              //num of edge
    private Bag<Integer>[] adj; //邻接表, implement of Bag

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

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(int v, int w) {
        if (v > V || v < 0 || w > V || w < 0) throw new IllegalArgumentException();
        if (v == w) throw new IllegalArgumentException("Don't allow self-loop!");
        if (adj[v].contains(w) || adj[w].contains(v)) throw new IllegalArgumentException("Don't allow parallel-edge!");
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }

    public boolean hasEdge(int v, int w) {
        if (V() < 2) return false;
        if (v < 0 || v >= V()) return false;
        return adj[v].contains(w);
    }

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

基础介绍完了，接下来进入经典的深度优先搜索和广度优先搜索，这两个可谓是实用最广泛的暴力遍历算法了。

深度优先搜索 DFS

深度优先搜索的模型，最早可以追溯到一种走迷宫的问题(Tremaux搜索)，如何探索迷宫中所有的通道：

1. 选择一个起始点出发，并在你走过的每条路都做好标记（放上绳子）。
2. 标记你所有第一次来到的路口。
3. 当来到了已经标记过的路口时，回退到上一个路口，换一条路走。
4. 当回退的路口无路可走时，继续回退。

这里，路口就是顶点，路径就是边。

• 通过理解这个类似Stack LIFO栈的流程，可以轻松的完成算法构建。

深度优先搜索更注重两个顶点是否连通，并不关心路径长短。

DepthFirstSearch 深度优先搜索DepthFirstSearch.java

public class DepthFirstSearch {
    private final int s;
    private boolean[] marked;
    private int count;
    private int[] edgeTo;

    public DepthFirstSearch(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;
        count++;
        for (int w : G.adj(V)) {
            if (!marked[w]) {
                edgeTo[w] = V;
                dfs(G, w);
            }
        }
    }

    public boolean hasPathTo(int w) {
        return marked[w];
    }

    public int count() {
        return count;
    }

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

广度优先搜索 BFS

相对于深度优先搜索而言，广度优先搜索更注重单点最短路径的选择。

同样以走迷宫的模型举例，相对于DFS一个人探索迷宫而言，BFS更像是团队合作。

1. 在遇到路口时，会选择好几个人去同时探寻迷宫。
2. 当两人相遇时，会合二为一，并选用先到的人继续探寻。

• 所有深度优先搜索能实现的，广度优先搜索也可以实现，只是效率上的问题有差异。
• 广度优先搜索的实现思想更类似于 Queue FIFO队列。

BreadthFirstPaths 广度优先搜索BreadthFirstPaths.java

public class BreadthFirstPaths {
    private final int s;        //startup
    private boolean[] marked;   //vertex marked
    private int[] edgeTo;       //last vertex in road

    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 Queue<>();
        marked[s] = true;
        queue.enqueue(s);
        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.enqueue(w);
                }
            }
        }
    }

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

    public int distTo(int v) {
        //0~v distance
        int dis = 0;
        if (!hasPathTo(v)) return dis;
        for (int x = v; x != s; x = edgeTo[x])
            dis++;
        return dis;
    }
}

有向图

有向图和无向图的区别，仅在于边变为有向了。在图的构建上，仅需更改addEdge()，由邻接表的双向添加，变为单向添加边。

Digraph 有向图Digraph.java

public class Digraph {
    ···
    public void addEdge(int v, int w) {
        ···
        adj[v].add(w);
        E++;
    }
    ···
}

有向图的可达性

就是使用有向图进行深度优先搜索，很简单，暴力搜索邻接表即可。

DirectedDFS 有向图深度优先搜索DirectedDFS.java

public class DirectedDFS {
    private boolean marked[];
    private int count;

    public DirectedDFS(Digraph G, int s) {
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    //接受多个顶点的构造方法
    public DirectedDFS(Digraph G, Iterable<Integer> sources) {
        marked = new boolean[G.V()];
        for (int s : sources)
            if (!marked[s]) dfs(G, s);
    }
    
    private void dfs(Digraph G, int v) {
        count++;
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
    }

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

    public int count() {
        return count;
    }
}

标记-java GC机制

在这里，有向图可以被应用于GC模型。顶点表示对象，有向边表示对象对另一个对象的引用。有一个根对象（起点）指向所有堆上的对象，周期性的执行DFS，而只要发现某个对象无访问路径，则记为可回收对象，以腾出空闲内存。

当然，实际的GC算法更为复杂，这里只是举例简化，便于理解。

有向图的路径

通过像Graph结构一样，添加edgeTo[]记录路径，并引入Digraph结构来表示，即可轻松得到有向路径DFS和有向最短路径BFS的实现。

---

参考文献：《算法导论》 《Algorithms, 4th Edition》