图基础

图可分为有向图和无向图，一般用G=(V,E)来表示图，V表示顶点，E表示通过图的边，常用邻接矩阵或者邻接表来描述一副图。图的遍历算法，根据访问节点的顺序，可分为广度优先搜索（BFS：Breadth First Search）和深度优先搜索（DFS：Depth First Search），图的存储常用邻接矩阵和邻接表。

邻接矩阵是指用矩阵来表示图。它是采用矩阵来描述图中顶点之间的关系（及弧或边的权），通常采用两个数组来实现邻接矩阵：一个一维数组用来保存顶点信息，一个二维数组来用保存边的信息，邻接矩阵的缺点就是比较耗费空间。

邻接表是图的一种链式存储表示方法。它是改进后的邻接矩阵，它的缺点是不方便判断两个顶点之间是否有边，但是相对邻接矩阵来说更省空间。

一条边上的两个顶点叫做邻接点，有向图有入边（以该点为终点的边）和出边（以该点为起点的边）的概念。无向图中，某个顶点的度是邻接到该顶到的边的数目。有向图有入度和出度之分。

简单路径：一条路径上顶点不重复出现

简单回路：第一个顶点和最后一个顶点相同，其它各顶点都不重复的回路则是简单回路

连通图：对无向图而言，任意两顶点之间存在一条无向路径，则称该无向图为连通图。对有向图而言，若图中任意两个顶点之间存在一条有向路径，则称该有向图为强连通图。

连通分量：非连通图中的各个连通子图称为该图的连通分量。

广度优先搜索（BFS）

广度优先搜索在进一步遍历图中顶点之前，先访问当前顶点的所有邻接结点。

首先选择一个顶点作为起始结点
将起始结点放入队列中
从队列首部选出一个顶点，并找出所有与之邻接的结点，将找到的邻接结点放入队列尾部
按照同样的方法处理队列中的下一个结点

深度优先搜索（DFS）

深度优先搜索在搜索过程中访问某个顶点后，需要递归地访问此顶点的所有未访问过的相邻顶点，和树的遍历比较类似，若初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。DFS在环监测和拓扑排序中都有不错的应用。

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。在一些有N个元素的集合应用问题中，通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

合并操作是把两个不相交的集合合并为一个集合，查询操作是查询两个元素是否在同一个集合中。最简单的并查集效率比较低，可以使用路径压缩的方法，使每个元素到根节点的路径尽可能短，最好只需要一步。

class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int n = 0; n < N; ++n) {
            parent[n] = n;
        }
    }
    
    public int find(int x) {
        return parent[x] == x ? x : find(parent[x]);
    }

    public int findCompress(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }
    
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

可能会认为并查集始终都是一个只有两层的树，由于压缩路径值在查询时进行，也只压缩一条路径，应该把简单的树往复杂的树上合并，用一个数组rank[]记录每个根节点对应的树的深度，把所有元素的rank秩设为1。按秩合并会带来额外的空间复杂度。

class DSU {
    int[] parent;
    int[] rank;

    public void init(int N) {
        parent = new int[N];
        for (int n = 0; n < N; ++n) {
            parent[n] = n;
            rank[n] = 1;
        }
    }
    
    public int findCompress(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    public void merge(int i, int j) {
        int x = find(i), y = find(j);
        if (rank[x] <= rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
        }
        if (rank[x] == rank[y] && x != y) {
            rank[y]++;
        }
    }
}

克隆图

使用哈希表存储所有已被访问和克隆的节点。哈希表中的 key 是原始图中的节点，value 是克隆图中的对应节点。若某个节点已经被访问过，则返回其克隆图中的对应节点。若当前访问的节点不在哈希表中，则创建其克隆节点并存储在哈希表中。递归调用每个节点的邻接点。

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

private Map<Node, Node> nodeMap = new HashMap<>();
public Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }

    if (nodeMap.containsKey(node)) {
        return nodeMap.get(node);
    }

    Node cloneNode = new Node(node.val, new ArrayList<>());
    nodeMap.put(node, cloneNode);

    for (Node neighbor : node.neighbors) {
        cloneNode.neighbors.add(cloneGraph(neighbor));
    }
    return cloneNode;
}