无向图

概念轰炸

• 图是由一组顶点和一组能够将两个顶点连接的边组成的
• x-y表示x到y的一条边
• 一条连接一个顶点和其自身的边称为自环
• 连接同一对顶点的两条边称为平行边
• 含有平行边的图称为多重图
• 某个顶点的度数即为依附于它的边的总数
• 当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并称这条边依附于这两个顶点
• 子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图
• 如果从任何一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图为连通图。
• 一幅非连通的图由若干连通的部分组成，它们都是它的极大连通子图
• 二分图是一种能够将所有结点分为两部分的图，也就是说图中每条边连接的两个顶点属于不同的部分

无向图的表示

今天的主角是无向图，顾名思义，无向图就是边没有方向的图。每当一个概念拿到程序中，总是需要抽象出一个数据结构来表示这个概念。那么，图怎么表示呢？表示图的这个数据结构叫做邻接表。

这个邻接表表示的就是下面这个图

首先，邻接表使用了一个数组来存放各个顶点，各个顶点又都指向了一个链表，链表里存放了与这个顶点相邻的顶点。1与2、5相邻，于是数组下标为1的元素指向的链表结点中含有2和5，同样数组下标为2和5的元素指向的链表中也一定含有1。当我们对一个图进行操作的时候，其实就是对这个邻接表进行操作。同时我们也可以看到，如果要访问与顶点3相邻的顶点，我们势必会先访问到2，然后是5，最后是9。但是对与顶点3来说，和它相邻的任何一个顶点低位都是相同的，但这个先后顺序却是确定的。所以构造这个图的时候，也就是构造这个邻接表的时候就已经决定了我们操作图中结点时的某些顺序。

对与领接表数组中的元素，本身是一个链表，为了方便操作，我们用一个Bag类来实现这个链表。

public class Bag<Item> implements Iterable<Item>{
    private Node first;
    private class Node{
        Item item;
        Node next;
    }
    public void add(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item=item;
        first.next=oldfirst;
    }
    public Iterator<Item> iterator(){
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item>{
        private Node current = first;
        public boolean hasNext(){
            return current!=null;
        }
        public Item next(){
            Item item = current.item;
            current=current.next;
            return item;
        }
    }
}

从而我们就可以用这个Bag来构造我们的无向图

public class Graph {
    private final int V;//顶点数
    private int E;      //边数
    private Bag<Integer>[] adj;//邻接表
    public Graph(int V){
        this.V=V;
        this.E=0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int i=0;i<V;i++){
            adj[i]=new Bag<Integer>();
        }
    }
    public Graph(In in){
        this(in.readInt());
        this.E=in.readInt();
        for (int i=0;i<V;i++){
            int w = in.readInt();
            int v = in.readInt();

        }

    }
    public int V(){
        return V;
    }
    public int E(){
        return E;
    }
    public void addEdge(int v,int w){
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
}

今天主要说一下图的两种搜索方法，深度优先搜索和广度优先搜索。

深度优先搜索（递归）

深度优先搜索就是：一条路走到黑，装了南墙就返回，再找一条路往黑了走。还以上边的图为例，我们从1开始进行深度优先搜索，首先他会先访问1，然后访问1的相邻顶点，于是找到了2（为什么不是5？因为构造邻接表时，2排在了5前边），然后再去找2的相邻顶点，当它开始访问2的相邻顶点的时候，1的相邻顶点其实还没有访问完，这就体现了深度优先，访问过程是一直深入的，直到碰了南墙才会返回。这里的碰了南墙其实就是访问的顶点已经被访问过。

public class DeepFirstSearch {
    private boolean[] marked;
    private int count;//被访问过的结点的个数
    public DeepFirstSearch(Graph g,int s){
        marked = new boolean[g.V()];
        dfs(g,s);
    }
    private void dfs(Graph g,int s){
        marked[s] = true;
        count++;
        for (int v:g.adj(s)
             ) {
            if (!marked[v])dfs(g,v);
        }
    }
    public boolean marked(int v){
        return marked[v];
    }
    public int count(){
        return count;
    }
}

marked这个boolean数组用来记录哪些顶点被访问过，以完成撞南墙检测。深度优先搜索可以用来解决单点路径问题。如：从1到9是否存在一条路径？如果有，找出这条路径。
其实我们只需要改动一点点上边的代码就可以解决这个问题

public class DeepFirstPath {
    private final int s;
    private boolean[] marked;
    private int[] edgeTo;
    public DeepFirstPath(Graph g,int s){
        this.s=s;
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];

    }
    private void dfs(Graph g,int v){
        marked[v] = true;
        for (int w :
                g.adj(v)) {
            if (!marked[v]){
                edgeTo[w] = v;
                dfs(g,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 i = v;i!=s;i=edgeTo[i]){
            path.push(i);
        }
        path.push(s);
        return path;
    }
}

我们只是加了一个Int数组edgeTo，这个数组记录了路径的信息。edgeTo[2]=1，表示1-2是第一次访问2时经过的边。通过edgeTo这个数组我们就可以还原出一个路径。除此之外，深度优先搜索还可以找出图中的所有连通分量。

public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;
    public CC(Graph graph){
        marked = new boolean[graph.V()];
        id = new int[graph.V()];
        for (int s = 0;s> graph.V();s++){
            if (!marked[s]){
                dfs(graph,s);
                count++;
            }
        }

    }
    public void dfs(Graph g,int v){
        marked[v] = true;
        id[v] = count;
        for (int w :
                g.adj(v)) {
            if (!marked[w]) dfs(g, w);
        }
    }
    public boolean connected(int v,int w){
        return id[v]==id[w];
    }
    public int id(int v){
        return id[v];
    }
    public int count(){
        return count;
    }
}

在原来一篇文中我们通过union-find算法寻找了连通分量，今天这个深度优先算法一样可以用来寻找连通分量。其中的id数组起到的就是这个作用，如若x和y两个顶点属于一个连通分量，那么id[x]=id[y]。

广度优先搜索

刚才说到深度优先搜索可以找到两个顶点之间的一个路径，但当两个顶点之间有多个路径的时候，我们需要找出最短的那一条时，深度优先搜索就束手无策了。此刻只能我们广度优先搜索出来亮亮相了。广度优先搜索会先搜索最近的顶点（也就是邻接表中的顶点），然后再去搜索最近的顶点的相邻顶点，就像是一个扩散的过程。所以第一次访问到的顶点所经过的边构成的路径一定是最短的路径。广度优先搜索的实现没有使用递归，而是用了一个队列来保存已经被访问过但其领接表还没有被访问的顶点。然后重复以下两步：①取队列中的下一个顶点并标记为已访问。②将和这个顶点相邻的所有未访问的顶点加入队列

public class BreadthFirstPaths {
    private boolean[] marked;
    private final int s;
    private int[] edgeTo;
    public BreadthFirstPaths(Graph g,int s){
        this.s=s;
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];
    }
    private void bfs(Graph g,int v){
        Queue<Integer> queue = new LinkedBlockingQueue<Integer>();
        marked[v]=true;
        queue.add(v);
        while (!queue.isEmpty()){
            int w = queue.remove();
            for (int ss :
                    g.adj(w)) {
                if (!marked[ss]) {
                edgeTo[ss]=w;
                queue.add(ss);
                }
        }
    }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v){
        if (!marked[v]) return null;
        Stack<Integer> path = new Stack<>();
        for (int i=v;i!=s;i=edgeTo[i]){
            path.push(i);
        }
        path.push(s);
        return path;
    }

}