数据结构笔记 part2

首页 > 代码库 > 数据结构笔记 part2

2024-08-17 08:49:44 225人阅读

1. union find 并查集

一种用来解决集合查询和合并的数据结构

并查集能够干什么？

　　1. find 操作判断在不在同一个集合中

　　2. union关于集合合并

例子：

A, B, C的boss 是B D,E,F的boss是E 那么组成了两个集合。

每个节点都包含了一个指针，指向其boss，boss自身指向自己。数据可以用hashmap或者2个数组来表示。

技术分享

union

老大哥之间的合并，和小弟没关系。

当需要合并的时候，只需要把被合并的部分的boss指针指向合并后的boss。只需要改1个指针。

union模版：

HashMap<Integer, Integer> father = HashMap<Integer, Integer>();

void union( int x, int y) {
  int fa_x = find(x);
  int fa_y = find(y);
  if (fa_x != fa_y) {
      father.put(fa_x, fa_y);
  }              
}

技术分享

当需要查找的时候，用非递归的方式找到一个节点，其boss为自身的就是该集合的boss。

技术分享

find 模版：

HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

int find(int x) {
    int parent = father.get(x);
    while(parent != father.get(partent)) {
        parent = father.get(parent);
    }
    return parent;
}

完整并查集合模版：

class UnionFind {
    HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
    UnionFind(){}

    int find(int x) {
        int parent = father.get(x);
        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }
        return parent;
    }

    void union (int x, int y) {
        int fa_x = find(x);
        int fa_y = find(y);
        if (fa_x != fa_y) {
            father.put(fa_x, fa_y);
        }
    }
}

UnionFind

-------我是分割线---------

Find the Connected Component in the Undirected Graph

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

Example

Given graph:

A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   E

Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}

BFS方法：

开辟一个hashmap vistied来存当前遍历的情况，如果是需要返回联通块的数目，那么 value就用integer来表示，如果要返回所有联通块的具体node，那么可以直接用true／false来表示。

技术分享

/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param nodes a array of Undirected graph node
     * @return a connected set of a Undirected graph
     */
    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Map<UndirectedGraphNode, Boolean> visited = new HashMap<UndirectedGraphNode, Boolean>();
        
        for (UndirectedGraphNode node : nodes) {
            visited.put (node, false);
        }

        for (UndirectedGraphNode node : nodes){
            if (visited.get(node) == false){
                bfs(node, visited, result);
            }
        }
        return result;
    }
    private static void bfs(UndirectedGraphNode node, Map<UndirectedGraphNode, Boolean> visited, List<List<Integer>> result) {
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        List<Integer> row = new ArrayList<>();
        
        visited.put(node, true);
        queue.offer(node);
        while (!queue.isEmpty()) {
            UndirectedGraphNode u = queue.poll();
            row.add(u.label);
            for (UndirectedGraphNode temp : u.neighbors) {
                if (visited.get(temp) == false) {
                    queue.offer(temp);
                    visited.put(temp, true);
                }
            }
        }
        Collections.sort(row);
        result.add(row);
    }
}

View Code

并查集方法：

找集合个数的题目，要想到用并查集

/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param nodes a array of Undirected graph node
     * @return a connected set of a Undirected graph
     */
    class UnionFind {
        HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
        UnionFind(HashSet<Integer> set) {
            for (Integer temp : set) {
                father.put(temp, temp);
            }
        }
     
        int find(int target) {
            while (father.get(target) != target) {
                target = father.get(target);
            }
            return target;
        }
        
        void union(int x, int y) {
            int fa_x = find(x);
            int fa_y = find(y);
            if (fa_x != fa_y) {
                father.put(fa_x, fa_y);
            }
        }
    }
    public List<List<Integer>> generateRes(HashSet<Integer> hashSet, UnionFind uf, int n) {
            List<List<Integer>> ans = new ArrayList<List<Integer> >();
            HashMap<Integer, List<Integer>> hashMap = new HashMap<Integer, List<Integer>>();
            for (int i : hashSet) {
                int fa = uf.find(i);
                if (!hashMap.containsKey(fa)) {
                    hashMap.put(fa, new ArrayList<Integer>());
                }
                List<Integer> now = hashMap.get(fa);
                now.add(i);
                hashMap.put(fa, now);
            }
            for (List<Integer> now : hashMap.values()) {
                Collections.sort(now);
                ans.add(now);
            }
            return ans;
        }
    
    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        // Write your code here
        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (UndirectedGraphNode now : nodes) {
            hashSet.add(now.label);
        }
        UnionFind uf = new UnionFind(hashSet);

        for (UndirectedGraphNode now : nodes) {
            for (UndirectedGraphNode neighbour : now.neighbors) {
                int fnow = uf.find(now.label);
                int fneighbour = uf.find(neighbour.label);
                if (fnow != fneighbour) {
                    uf.union(now.label, neighbour.label);
                }
            }
        }
        return generateRes(hashSet, uf, nodes.size());
    }
}

connectedSet

由于father指针的链可能会非常长，find 和 union操作都是o(n)的时间复杂度。可以做以下优化，在写并查集find操作的时候，做路径压缩。

 public int find(int target){
        int parent = target;
        while(parent != map.get(parent)){
            parent = map.get(parent);
        }
        int current = target;
        int next;
        while (current != map.get(current)) {
            next = map.get(current);
            map.put(current, parent);
            current = next;
        }
        return parent;

    }

带路径压缩的find

--------我是分割线------

联通块：强联通块：有向图一个块当中，你找得到我，我可以找不到你。

　　　　弱联通块：在有向图一个块当中，你找得到我，我也找得到你。

------我还是分割线----

Number of Islands

Given a 2d grid map of ‘1‘s (land) and ‘0‘s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

bfs/dfs都可以做，另外如何存储点，可以新建个point类，或者把二元坐标转化为一元坐标

bfs代码：

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        boolean[] visited = new boolean[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i * n + j] == false && grid[i][j] == ‘1‘) {
                    count++;
                    bfs(grid, visited, i * n + j, m , n);
                }
            }
        }
        return count;
    }
    public void bfs(char[][] grid, boolean[] visited, int k, int m, int n){
        Queue<Integer> queue = new LinkedList<Integer>();
        visited[k] = true;
        queue.offer(k);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            if ((current - n) >= 0 && visited[current - n] == false &&grid[current / n - 1][current % n] == ‘1‘) {
                visited[current - n] = true;
                queue.offer(current - n);
            } 
            if (current + n < m * n && visited[current + n] == false && grid[current / n + 1][current % n] == ‘1‘) {
                visited[current + n] = true;
                queue.offer(current + n);

            } 
            if (current % n - 1 >= 0 && visited[current - 1] == false && grid[current/n][current % n - 1] == ‘1‘) {
                visited[current - 1] = true;
                queue.offer(current - 1);

            } 
            if ((current % n + 1) < n  && visited[current + 1] == false && grid[current / n][current % n + 1] == ‘1‘) {
                visited[current + 1] = true;
                queue.offer(current + 1);

            }
        }
    }
}

number of island bfs

dfs做递归调用，代码简介很多

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    private int m, n;
    public void dfs(boolean[][] grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n) return;
        
        if (grid[i][j]) {
            grid[i][j] = false;
            dfs(grid, i - 1, j);
            dfs(grid, i + 1, j);
            dfs(grid, i, j - 1);
            dfs(grid, i, j + 1);
        }
    }

    public int numIslands(boolean[][] grid) {
        // Write your code here
        m = grid.length;
        if (m == 0) return 0;
        n = grid[0].length;
        if (n == 0) return 0;
        
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!grid[i][j]) continue;
                ans++;
                dfs(grid, i, j);
            }
        }
        return ans;
    }
}

dfs

会stack overflow = = 懒得改了

并查集的做法：

数据结构笔记 part2

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 数据结构 笔记 part2