数据结构与算法学习笔记（基础班十）---并查集和图

并查集

  • 有若干个样本a、b、c、d…类型假设是V。
  • 在并查集中一开始认为每个样本都在单独的集合里。
  • 用户可以在任何时候调用如下两个方法：
    1.boolean isSameSet(V x, V y) : 查询样本x和样本y是否属于一个集合。
    2.void union(V x, V y) : 把x和y各自所在集合的所有样本合并成一个。
  • isSameSet和union方法的代价越低越好。（时间复杂度O(1)）。

并查集特征

1）每个节点都有一条往上指的指针。
2）节点a往上找到的头节点，叫做a所在集合的代表节点。
3）查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个。
4）把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方即可。

并查集的优化

1）节点往上找代表点的过程，把沿途的链变成扁平的。
2）小集合挂在大集合的下面。
3）如果方法调用很频繁，那么单次调用的代价为O(1)，两个方法都如此。

/**
 * 并查集
 * 提供两个方法：
 * 1、查询两个元素是否在同一个集合中  isSameSet
 * 2、把两个元素所在的集合合并成一个  union
 *
 * 假定用户一次直接给出所有集合
 */
public class UnionSearch<V> {
    // 节点位置表
    Map<V,Node> nodes;
    // 查找当前节点对应的父节点表
    Map<Node,Node> parents;
    // 作为代表元素表 k代表元素 v 集合中有几个元素
    Map<Node,Integer> size;
    public UnionSearch(List<V> list){
        nodes = new HashMap<>();
        parents = new HashMap<>();
        size = new HashMap<>();
        for(V v : list){
            // 出事时每个元素单独作为一个结合
            Node node = new Node(v);
            nodes.put(v,node);
            parents.put(node,node);
            size.put(node,1);
        }
    }


    public  boolean isSameSet(V v1,V v2){
        if(!nodes.containsKey(v1)
                || !nodes.containsKey(v2)){
            return false;
        }
        Node node1 = findFather(v1);
        Node node2 = findFather(v2);
        if(node1 == node2){
            return true;
        }

        return false;
    }


    public void union(V v1,V v2){
        if(!nodes.containsKey(v1)
                || !nodes.containsKey(v2)){
            return;
        }
        Node node1 = findFather(v1);
        Node node2 = findFather(v2);
        // 两个元素不在一个集合中才合并
        if(node1 != node2){
           // 看谁的元素多
            Node big = size.get(node1) > size.get(node2) ? node1 : node2;
            Node small = size.get(node1) <= size.get(node2) ? node1 : node2;
            // 小的挂在大的上面
            parents.put(small,big);
            size.put(big,size.get(big) + size.get(small));
            size.remove(small);
        }

    }

    // 调用此方法是一定保证集合中有此元素
    private Node findFather(V node){
        // 做一个扁平化优化,把从当前节点网上找的节点都加入容器中
        Stack<Node> stack = new Stack<>();
        Node cur = nodes.get(node);
        while (parents.get(cur) != cur){
            // 路径上经过的节点加入容器
            stack.push(cur);
            // 只要此时节点不等于父节点，说明不是代表节点就一直往上找
            cur = parents.get(cur);
        }

        // 把所有经过节点直接和代表节点相连，下次查找是O（1）
        while (!stack.isEmpty()){
            parents.put(stack.pop(),cur);
        }
        //跳出来说明已经找到了
        return cur;
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList();

        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        list.add("f");
        list.add("g");
        UnionSearch<String> unionSearch = new UnionSearch<>(list);
        unionSearch.union("a","b");
        unionSearch.union("c","b");
        System.out.println(unionSearch.isSameSet("a", "g"));

    }
}

图

1）由点的集合和边的集合构成。
2）虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达。
3）边上可能带有权值。

图结构的表达

1）邻接表法
2）邻接矩阵法
3）除此之外还有其他众多的方式

图的数据结构

  • 点
// 点
public class Node {
    // 结点值
    public int value;
    // 入度
    public int in;
    // 出度
    public int out;
    // 邻居
    List<Node> nexts;
    // 存一份边
    List<Edge> edges;

    public Node(int value){
        this.value = value;
        // 新结点入度为0
        this.in = 0;
        // 新结点出度为0
        this.out = 0;
        // 新结点邻居为空
        this.nexts = new ArrayList<>();
        this.edges = new ArrayList<>();
    }
}
  • 边
// 边
public class Edge {
    // 权重
    public int weight;
    // 起点边
    public Node from;
    // 终点边
    public Node to;
    public Edge(Node from,Node to,int weight){
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}
  • 图
// 图
public class Graph {
    // 点的集合
    HashMap<Integer,Node> nodes;
    // 边的集合
    HashSet<Edge> edges;
    public Graph(){
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }
}
  • 生成图
public class GraphGenerator {
    // matrix 所有的边
    // N*3 的矩阵
    // [weight, from节点上面的值，to节点上面的值]
    public static Graph graphGenerator(Integer[][] matrix){
        Graph graph = new Graph();
        for (int i = 0;i < matrix.length;i++){
            // 每一行代表一个点
            // 权重
            int weight = matrix[i][0];
            // 起始点
            int from = matrix[i][1];
            // 终点
            int to = matrix[i][2];
            // 如果没有起始点就新建
            if(graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if(graph.nodes.containsKey(to)){
                graph.nodes.put(to,new Node(to));
            }

            // 取出点构建图
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            // 构建边
            Edge edge = new Edge(fromNode,toNode,weight);
            // fromNode 几点出度加一，邻居加一
            fromNode.out ++;
            fromNode.nexts.add(toNode);
            fromNode.edges.add(edge);
            // toNode入度加一
            toNode.in ++;
            // 图中边集加一
            graph.edges.add(edge);
        }
        return graph;
    }
}

宽度优先遍历

1，利用队列实现
2，从源节点开始依次按照宽度进队列，然后弹出
3，每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
4，直到队列变空

  • 注意要点，不能重复遍历，便利过的点应该排除。
// 图的宽度有限便利
public class GraphBfs {
    public static void graphBfs(Node node){
        if(node == null){
            return;
        }
        HashSet<Node> set = new HashSet<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        set.add(node);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(cur.value + " ");
            // 全部邻居加入队列
            for (Node next : cur.nexts){
                if(!set.contains(next)){
                    queue.offer(next);
                    set.add(next);
                }
            }
        }
    }
}

深度优先遍历

1.利用栈实现
2.从源节点开始把节点按照深度放入栈，然后弹出
3.每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
4.直到栈变空

- 图的深度优先遍历主要注意重复结点不遍历
// 图的宽度优先遍历
public class GraphDfs {
    public static void  graphDfs(Node node){
        if(node == null){
            return;
        }
        HashSet<Node> set = new HashSet<>();
        // 利用栈
        Stack<Node> stack = new Stack<>();
        // 入栈就打印
        stack.push(node);
        System.out.print(node.value + " ");
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            for(Node item : cur.nexts){
                if(!set.contains(item)){
                    stack.push(cur);
                    stack.push(item);
                    set.add(item);
                    System.out.print(item.value + " ");
                    break;
                }
            }
        }  
    }
}

图的拓扑排序算法

1）在图中找到所有入度为0的点输出
2）把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
3）图的所有点都被删除后，依次输出的顺序就是拓扑排序
要求：有向图且其中没有环
应用：事件安排、编译顺序

// 拓扑排序
public class TopologySort {

    public static List<Node> topologySort(Graph graph){
        if(graph == null){
            return null;
        }
        // 入度为0的点进入此队列
        Queue<Node> zeroQueue = new LinkedList<>();
        // k ：结点  v ：入度数
        HashMap<Node,Integer> map = new HashMap<>();
        List<Node> res = new ArrayList<>();
        for(Node item : graph.nodes.values()){
            map.put(item,item.in);
            if(item.in == 0){
                zeroQueue.offer(item);
            }
        }
        while (!zeroQueue.isEmpty()){
            Node cur = zeroQueue.poll();
            res.add(cur);
            for(Node temp : cur.nexts){
                map.put(temp,map.get(temp)-1);
                if(map.get(temp) == 0){
                    zeroQueue.offer(temp);
                }
            }
            
        }
        return res;
    }
}

最小生成树K算法

/**
 * 最小生成树算法之Kruskal
 * 1）总是从权值最小的边开始考虑，依次考察权值依次变大的边(优先级队列)
 * 2）当前的边要么进入最小生成树的集合，要么丢弃
 * 3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边
 * 4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边
 * 5）考察完所有边之后，最小生成树的集合也得到了
 */
public class Kruskal {
    public static Set<Edge> kruskal(Graph graph){
        if(graph == null){
            return null;
        }
        Set<Edge> res = new HashSet<>();
        // 先把所有点都加入并查集
        List<Node> nodeList = (List<Node>)graph.nodes.values();
        UnionSearch<Node> unionSearch = new UnionSearch<>(nodeList);
        // 获取所有边
        PriorityQueue<Edge> queue = new PriorityQueue<>(new MyComparator());
        for(Edge item : graph.edges){
            queue.offer(item);
        }
        while (!queue.isEmpty()){
            Edge cur = queue.poll();
            Node from = cur.from;
            Node to = cur.to;
            if(!unionSearch.isSameSet(from,to)){
               res.add(cur);
                // 加入并查集
                unionSearch.union(from,to);
            }
        }
        
        return res;

    }
    
    private void makeUnion(List<Node> list,UnionSearch<Node> unionSearch){
        for(Node item : list){
            
        }
    }

    static class MyComparator implements Comparator<Edge>{

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }


     static class UnionSearch<V> {
        // 节点位置表
        Map<V,Node2> nodes;
        // 查找当前节点对应的父节点表
        Map<Node2,Node2> parents;
        // 作为代表元素表 k代表元素 v 集合中有几个元素
        Map<Node2,Integer> size;
        public UnionSearch(List<V> list){
            nodes = new HashMap<>();
            parents = new HashMap<>();
            size = new HashMap<>();
            for(V v : list){
                // 出事时每个元素单独作为一个结合
                Node2 node = new Node2(v);
                nodes.put(v,node);
                parents.put(node,node);
                size.put(node,1);
            }
        }


        public  boolean isSameSet(V v1,V v2){
            if(!nodes.containsKey(v1)
                    || !nodes.containsKey(v2)){
                return false;
            }
            Node2 node1 = findFather(v1);
            Node2 node2 = findFather(v2);
            if(node1 == node2){
                return true;
            }

            return false;
        }


        public void union(V v1,V v2){
            if(!nodes.containsKey(v1)
                    || !nodes.containsKey(v2)){
                return;
            }
            Node2 node1 = findFather(v1);
            Node2 node2 = findFather(v2);
            // 两个元素不在一个集合中才合并
            if(node1 != node2){
                // 看谁的元素多
                Node2 big = size.get(node1) > size.get(node2) ? node1 : node2;
                Node2 small = size.get(node1) <= size.get(node2) ? node1 : node2;
                // 小的挂在大的上面
                parents.put(small,big);
                size.put(big,size.get(big) + size.get(small));
                size.remove(small);
            }

        }

        // 调用此方法是一定保证集合中有此元素
        private Node2 findFather(V node){
            // 做一个扁平化优化,把从当前节点网上找的节点都加入容器中
            Stack<Node2> stack = new Stack<>();
            Node2 cur = nodes.get(node);
            while (parents.get(cur) != cur){
                // 路径上经过的节点加入容器
                stack.push(cur);
                // 只要此时节点不等于父节点，说明不是代表节点就一直往上找
                cur = parents.get(cur);
            }

            // 把所有经过节点直接和代表节点相连，下次查找是O（1）
            while (!stack.isEmpty()){
                parents.put(stack.pop(),cur);
            }
            //跳出来说明已经找到了
            return cur;
        }

        
    }
}

最小生成树p算法

/**
 * 最小生成树，p算法
 * 1）可以从任意节点出发来寻找最小生成树
 * 2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边
 * 3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环
 * 4）如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）
 * 5）如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）
 * 6）当所有点都被选取，最小生成树就得到了
 */
public class Prim {
    public static Set<Edge> prim(Graph graph){
        if(graph == null){
            return null;
        }
        // 生成优先级队列
        PriorityQueue<Edge> queue = new PriorityQueue<>(new MyComparator());
        Set<Edge> edgeSet = new HashSet<>();
        Set<Node> nodeSet = new HashSet<>();
        Set<Edge> res = new HashSet<>();
        List<Node> nodeList = (List<Node>)graph.nodes.values();
        for(Node node : nodeList){ // 防止森林，如果明确没有森林可不要此循环。
            if(!nodeSet.contains(node)){
                // 解锁点的所有边
                nodeSet.add(node);
                for(Edge temp : node.edges){
                    if(!edgeSet.contains(temp)){
                        queue.offer(temp);
                        edgeSet.add(temp);
                    }
                }
                while (!queue.isEmpty()){
                    // 权重最小的边
                    Edge cur = queue.poll();
                    // 此时from节点已经在nodeSet结合中解锁出来了，只需判断to节点是否解锁了
                    if(!nodeSet.contains(cur.to)){
                        // 要这条边
                        res.add(cur);
                        // 加入点的集合
                        nodeSet.add(cur.to);
                        // 解锁cur.to的所有边
                        for (Edge e : cur.to.edges){
                            if(!edgeSet.contains(e)){
                                queue.offer(e);
                                edgeSet.add(e);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
   static class MyComparator implements Comparator<Edge>{
       @Override
       public int compare(Edge o1, Edge o2) {
           return o1.weight - o2.weight;
       }
   }
}

Dijkstra算法

1）Dijkstra算法必须指定一个源点
2）生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步
4）源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了

  • 优化点，在distanceMap中查找起点到其他点的最短距离是用遍历的方式时间复杂度是O(N),如果用小根堆，可以让时间复杂度降到O(logn),但是应为会更新加入到小根堆中的距离数据，一般的小根堆不能自动调整，所以要自己手动改写小根堆。
/**
 * 1）Dijkstra算法必须指定一个源点
 * 2）生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
 * 3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步
 * 4）源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
 */
public class Dijkstra {
    
    public static Map<Node2,Integer> dijkstra1(Node2 node){
        if(node == null){
            return null;
        }
        // 距离表,一开始只有出发点到出发点的距离为0
        Map<Node2,Integer> distanceMap = new HashMap<>();
        distanceMap.put(node,0);
        // 去重黑名单，每次选举最小记录时排除此表中的数据
        Set<Node2> noSelect = new HashSet<>();
        // 获取最小记录点（出发点到某一点的最短距离）
        Node2 minDistance = getMinAndNoSelect(distanceMap,noSelect);
        while (minDistance != null){ // 把表中数据都遍历完
            for (Edge temp : minDistance.edges){
                // 这个点往能出去的所有边能不能更新表中的距离
                Node2 to = temp.to;
                if(!distanceMap.containsKey(to)){
                    // 如果表中不包含这个点，说明还没找到过重from点到这个距离，直接加入表中
                    distanceMap.put(to,distanceMap.get(minDistance) + temp.weight);
                }else{
                    distanceMap.put(to,Math.min(distanceMap.get(to),distanceMap.get(minDistance) + temp.weight));
                }
            }
            minDistance = getMinAndNoSelect(distanceMap,noSelect);
            
        }
        
        return distanceMap;
    }
    
    
    private static Node2 getMinAndNoSelect(Map<Node2,Integer> distanceMap,Set<Node2> noSelcet){
        // 由于Dijkstra算法中边都是非负的用0就可以了
        int min = 0;
        Node2 res = null;
        // 遍历距离表
        for (Map.Entry<Node2, Integer> item : distanceMap.entrySet()){
            Node2 key = item.getKey();
            if(noSelcet.contains(key)){
                continue;
            }
            // 比较大小
            if(item.getValue() < min){
                min = item.getValue();
                res = item.getKey();
            }
        }
        noSelcet.add(res);
        return res;
    }

}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,657评论 6赞 505
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,889评论 3赞 394
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,057评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,509评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,562评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,443评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,251评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,129评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,561评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,779评论 3赞 335
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,902评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,621评论 5赞 345
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,220评论 3赞 328
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,838评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,971评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,025评论 2赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,843评论 2赞 354