[CS for Non-Tech] Part 2— Data Structures/Algorithms Zone [ไทย]

สวัสดีครับทุกคน บทความนี้จะเป็นไปที่ Non-Linear Data Structures เป็นหลักนะครับ ก็ประกอบไปด้วยเรื่องของ Tree และ Graph

เพื่อไม่ให้เป็นการเสียเวลา เรามาเริ่มต้นกันเลยมั้ยครับ ✌️🤩

Part 2— Data Structures/Algorithms Zone

Tree

Tree (ต้นไม้) เป็นโครงสร้างข้อมูลแบบลำดับชั้นที่ประกอบด้วย Node และแต่ละ Node จะมีลูกได้ตั้งแต่ 0-N ซึ่งอยู่ด้านล่างของ Node ในลำดับชั้น

• Node บนสุดเรียกว่า Root node (ราก) จากตัวอย่างด้านบน 3 คือ Root
• Node ในลำดับถัดไป ที่ตัว Node เองเป็น parent เรียกว่า children (ถ้าตัวเดียวก็เรียก child node) ตัวอย่างด้านบน 7, 8 เป็น children ของ 3
• Node ที่ไม่มี children แล้ว เรียกว่า Leaf node (ใบ) จากตัวอย่างด้านบนได้แก่ 2, 6, 0, 1

public class TreeNode<T> {
    public T value;
    public final List<TreeNode<T>> children;

    public TreeNode(T value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public void addChild(TreeNode<T> child) {
        this.children.add(child);
    }

    public void addChildren(List<TreeNode<T>> children) {
        this.children.addAll(children);
    }

    public void removeChild(TreeNode<T> child) {
        this.children.remove(child);
    }

    public void removeChildren(List<TreeNode<T>> children) {
        this.children.removeAll(children);
    }

    public boolean isLeaf() {
        return this.children.isEmpty();
    }
}

หรือคุณจะเรียกว่า N-ary Tree ก็ได้ครับ เพราะมี children มากกว่า 2 ตัว ส่วน children มี 2 ตัว ผมจะพูดต่อในถัดไปนี้

Binary Tree

Tree ที่มี children อย่างมาก 2 ตัว มักเรียกว่า left child และ right child

Type of Binary Tree

• Full binary tree — แต่ละ Node มีลูกไม่ 0 ก็ 2
• Complete binary tree — ในแต่ละ level ถูกเติมเต็มยกเว้น level สุดท้าย จะโดนเติมเต็มจากฝั่งด้านซ้ายเป็นหลัก
• Perfect binary tree — Every node มี 2 children ยกเว้น leaves level สุดท้าย
• Balanced binary tree — ความต่างในความลึกของ level แต่ละข้างไม่ห่างกันมาก เช่น AVL Tree ที่ให้ต่างกันมากสุดแค่ 1

Binary Search Tree (BST)

เป็นหนึ่งใน Type ของ Tree ที่เราใช้เรียก

• Binary Tree
• ค่า value ถูก sorted ในรูปแบบของ Tree
• ค่า value ภายใน Node ที่สนใจ จะมีค่ามากกว่า Left child
• ค่า value ภายใน Node ที่สนใจ จะมีค่าน้อยกว่า Right child

ด้านล่างเป็นโค้ด Example ที่ implement ด้วย Java

package datastructurealgorithms.tree.binary;

public class BinarySearchTreeNode<T extends Comparable<T>> {
    public T value;
    public BinarySearchTreeNode<T> left;
    public BinarySearchTreeNode<T> right;

    public BinarySearchTreeNode(T value) {
        this.value = value;
    }

    public BinarySearchTreeNode(T value, BinarySearchTreeNode<T> left, BinarySearchTreeNode<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public boolean isLeaf() {
        return this.left == null && this.right == null;
    }

    public void insert(T value) {
        if (value.compareTo(this.value) < 0) {
            if (this.left == null) {
                this.left = new BinarySearchTreeNode<>(value);
            } else {
                this.left.insert(value);
            }
        } else if (value.compareTo(this.value) > 0) {
            if (this.right == null) {
                this.right = new BinarySearchTreeNode<>(value);
            } else {
                this.right.insert(value);
            }
        }
    }

    public static <T extends Comparable<T>> BinarySearchTreeNode<T> searchBST(BinarySearchTreeNode<T> root, T val) {
        if (root == null) {
            return null;
        }
        if (val.compareTo(root.value) == 0) {
            return root;
        } else if (root.value.compareTo(val) > 0) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }

    public static <T extends Comparable<T>> BinarySearchTreeNode<T> deleteNode(BinarySearchTreeNode<T> root, T key) {
        if (root == null) {
            return null;
        }

        if (root.value.compareTo(key) > 0) {
            root.left = deleteNode(root.left, key);
        } else if (root.value.compareTo(key) < 0) {
            root.right = deleteNode(root.right, key);
        } else {
            // Found the node
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            // Seem have both child
            // Select Right
            BinarySearchTreeNode<T> leftMostRightChild = findMostLeft(root.right);
            leftMostRightChild.left = root.left;
            return root.right;
        }
        return root;
    }

    private static <T extends Comparable<T>> BinarySearchTreeNode<T> findMostLeft(BinarySearchTreeNode<T> node) {
        BinarySearchTreeNode<T> ptr = node;
        while (ptr.left != null) {
            ptr = ptr.left;
        }
        return ptr;
    }
}

ตัวอย่าง Validate BST — Leetcode 98. Validate Binary Search Tree

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        if (min != null && node.val <= min) {
            return false;
        }
        if (max != null && node.val >= max) {
            return false;
        }
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
}

Heap Tree

Heap Tree เป็นคำเรียก Binary Tree อีกเหมือนกันล่ะ แต่พื้นฐานอยู่บนหลักของ Complete Binary Tree โดยที่ value ของแต่ละ Node จะมีค่ามากกว่า/น้อยกว่า children node ขึ้นอยู่กับประเภทของ Heap

มี 2 ประเภท

• Max Heap: value ของแต่ละ Node จะมีค่ามากกว่า children ที่ Root Node คือค่าสูงสุด

• Min Heap: value ของแต่ละ Node จะมีค่าน้อยกว่า children ที่ Root Node คือค่าต่ำสุด

มักใช้ในการทำ Priority Queue โดยแบ่งความสำคัญตามเงื่อนไขที่เรากำหนด และยังเอาไปใช้ใน Heap Sort ด้วย (ที่ผมไม่ได้พูดถึง)

ถ้าหากว่าอยากใช้ Heap แต่ไม่อยากสร้าง Tree ล่ะ 5555555 งั้นนี่คือ List ของ API/Library ที่สามารถเอามาใช้ได้

• Java-PriorityQueue
• Python-heapq
• JavaScript-priority-queue

Trie

Trie หรือ Prefix Tree เป็นโครงสร้างข้อมูล Tree ที่ดัดแปลงให้ใช้เก็บค่าภายในเป็นแต่ละอักขระ อันนี้ผมเขียนเมื่อสมัยหนุ่ม ๆ

รื้อฟื้นความหลัง กลับไปทบทวน Trie (Data Structure)

คราวนี้มาลองดูร่างเติบโตกันบ้างดีกว่า ตัวอย่างโค้ดอยู่ในนี้ ImplemenTrie โดยพื้นฐานมาจาก Leetcode 208. Implement Trie (Prefix Tree) และผมใส่ “pet” ไปอีก 1 ตัว diagram จะได้สวย ๆ 🤣

public class ImplementTrie_208 implements GenerateExample {

  @Override
  public void example() {
    Trie trie = new Trie();
    List<String> words = List.of("apple", "app", "application", "ape", "pet");
    words.forEach(trie::insert);
    System.out.println("Search 'apple': " + trie.search("apple"));
    System.out.println("Contain prefix 'app': " + trie.startWith("app"));
  }

  private static class Trie {

    private final TrieNode root;

    public Trie() {
      root = new TrieNode();
    }

    public void insert(String word) {
      TrieNode ptr = root;
      for (char c : word.toCharArray()) {
        int index = Util.getLowercaseIndex(c);
        if (ptr.children[index] == null) {
          ptr.children[index] = new TrieNode();
        }
        ptr = ptr.children[index];
      }
      ptr.isWord = true;
    }

    public boolean search(String word) {
      TrieNode ptr = root;
      for (char c : word.toCharArray()) {
        int index = Util.getLowercaseIndex(c);
        if (ptr.children[index] == null) {
          return false;
        }
        ptr = ptr.children[index];
      }
      return true;
    }

    public boolean startWith(String prefix) {
      TrieNode ptr = root;
      for (char c : prefix.toCharArray()) {
        int index = Util.getLowercaseIndex(c);
        if (ptr.children[index] == null) {
          return false;
        }
        ptr = ptr.children[index];
      }
      return ptr != null;
    }
  }

  private static class TrieNode {

    boolean isWord = true;
    TrieNode[] children = new TrieNode[LOWERCASE_AMOUNT];
  }
}

Graph

เป็นโครงสร้างข้อมูลที่ใช้แสดงถึงความสัมพันธ์ของ Element โดย base จาก จุดยอด (Vertex) และขอบ (Edge)

กราฟมี 2 แบบคือ

• Directed Graph (กราฟระบุทิศทาง): edge จะมีทิศทางและเชื่อมต่อ vertex หนึ่งกับอีก vertex หนึ่ง
• Undirected Graph (กราฟไม่ระบุทิศทาง): edge connect 2 vertices เข้าด้วยกันเฉย ๆ

เราสามารถ Represent ความสัมพันธ์ของ Graph ได้ 2 แบบ

• Adjacency matrix ในกรณีที่เป็น Directed Graph ฝั่ง row (ABCD ฝั่งซ้าย) เป็น Source และฝั่ง column (ABCD ด้านบน) เป็น Destination

  A B C D
A 0 1 1 0
B 0 0 1 0
C 0 0 0 1
D 0 0 0 0

• Adjacency List

A: [B, C]
B: [C]
C: [D]
D: []

หากนำมา Plot to diagram ด้านล่างคือผลลัพธ์ที่ได้ (ก็เอามาจากไอรูปด้านบนแหละ)

Tree ก็คือ Graph เหมือนกันน่ะแหละ แต่ไม่มี Loop เป็น Graph ชนิดพิเศษ

Building Graph Example => Result as Adjacency List

public class GraphExample {
    public static Map<Integer, List<Integer>> buildGraph(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] e : edges) {
            graph.putIfAbsent(e[0], new ArrayList<>());
            graph.putIfAbsent(e[1], new ArrayList<>());
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        return graph;
    }
}

Depth First Search (DFS) — การค้นหาทางลึก

Depth First Search (DFS) อัลกอริทึมสำหรับการสำรวจ (Traverse) หรือค้นหา (Search) ผ่านมุมมอง Graph หรือ Tree โดยเริ่มที่ Node แรกและสำรวจให้ไกลที่สุดก่อน ตาม branches หรือ edges ที่มี หลังจากนั้นถ้าทำครบส่วนนี้แล้ว ก็ย้อนกลับไปทำฝั่งที่ยังไม่ได้ทำการสำรวจ ใช้ Stack หรือ Recursion มาช่วย โดยสามารถประยุกต์ใช้ได้ทั้งการสำรวจ และการค้นหา

Use cases ที่ใช้ได้ดี

• Maze solving
• Web crawler

Tree — DFS

หรือส่วนใหญ่ที่เขาเรียกกันตรงนี้ก็คือ Tree Traversal น่ะแหละ ด้านล่างจะเป็นตัวอย่าง Tree จากรูปก่อน ๆ

• Preorder (Root => Left => Right)
  ผลลัพธ์ที่ได้: A, B, D, G, H, C, E, F

public class Traversal {

    private static void preorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorderTraversal(root.left, result);
        preorderTraversal(root.right, result);
    }

}

• Inorder (Left => Root => Right)
  ผลลัพธ์ที่ได้: G, D, H, B, A, E, C, F

public class Traversal {

    private static void inorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }

}

• Postorder (Left => Right => Root)
  ผลลัพธ์ที่ได้: G, H, D, B, E, F, C, A

public class Traversal {

    private static void postorderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left, result);
        postorderTraversal(root.right, result);
        result.add(root.val);
    }
}

แล้วถ้าจะเอาให้มัน Search จริง ๆ ล่ะ โค้ดด้านล่าง base on Leetcode 700. Search in a Binary Search Tree ก็คือมันจะเข้าไปหาลึกขึ้นเรื่อย ๆ แต่ว่าเนื่องจากเป็น BST ดังนั้นเงื่อนไขก็ต้องใช้เหมือนกัน Binary Search

public class SearchInBST_700 {

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        } else if (root.val > val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

Graph — DFS

คำเตือน อย่าลืมจำไว้ว่า Vertex ไหนเคยมาแล้ว ไม่งั้นเกม (กรณีผมตัวอย่างนี้ใช้ HashSet) ตัวอย่างเช่นรูปด้านล่าง จะเป็นตัวอย่างของ DFS ใน Graph

package datastructurealgorithms.graph;

import java.util.*;

public class GraphExample {

    public static boolean dfs(int source, int destination, 
                              Map<Integer, List<Integer>> graph, 
                              Set<Integer> visited) {
        if (source == destination) {
            return true;
        }
        for (int v : graph.get(source)) {
            if (!visited.add(v)) {
                if (dfs(v, destination, graph, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Breath First Search (BFS) — การค้นหาทางกว้าง

Breath First Search (BFS) อัลกอริทึมสำหรับการสำรวจหรือค้นหาผ่านมุมมอง Graph หรือ Tree โดยเริ่มที่ Node แรกและสำรวจทุก ๆ branches หรือ edges ที่มี ก่อน หลังจากนั้นถ้าทำครบส่วนนี้แล้ว ก็จะไปทำที่ level/layer ถัดไป ใช้ Queue มาช่วย

Use cases ที่ใช้ได้ดี

• Shortest path in a graph
• Network connectivity

Tree — BFS

เรียกอีกอย่างได้ว่า Level Order Traversal อ่านไปทีละ level ถ้ามี children ก็โยนใส่เข้า Queue รอไว้ ตัวอย่างด้านล่าง เอามาจาก 102. Binary Tree Level Order Traversal

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> currLevel = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currLevel.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add(currLevel);
        }
        return result;
    }
}

Graph — BFS

คำเตือน อย่าลืมจำไว้ว่า Vertex ไหนเคยมาแล้ว ไม่งั้นเกมรอบ 2 (กรณีผมตัวอย่างนี้ใช้ HashSet) ตัวอย่างเช่นรูปด้านล่าง จะบอกลำดับการของ BFS ใน Graph

public class GraphExample {

    public static boolean bfs(Map<Integer, List<Integer>> graph, 
                              Set<Integer> visited, int start, int end) {
        if (start == end) {
            return true;
        }

        Set<Integer> seen = new HashSet<>();
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addAll(graph.get(start));

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == end) {
                return true;
            }
            for (int child : graph.get(node)) {
                if (!seen.contains(child)) {
                    queue.add(child);
                    seen.add(child);
                }
            }
        }

        return false;
    }
}

Dijkstra’s Algorithm

หนึ่งใน Single Source Shortest Path (SSSP) algorithm ในการหาระยะทางที่สั้นที่สุดจาก Vertex สู่ Vertex โดยการจัดเรียง Weight ให้อยู่ใน Min Heap หลังจากนั้นค่อย ๆ เลือกมา relaxing ทีละตัว ๆ จนครบ ข้อแม้คือ สามารถใช้ Dijkstra’s algorithm ได้บน Positive Weight Edge เท่านั้น

Time Complexity: O((E + V) log V)

ด้านล่างนี้ก็โค้ดของผู้เขียนจากตรงนี้

public class DijkstraAlgorithms {

  // Single Source Shortest Path algorithms - Only Positive Weight
  // Faster than Bellman-Ford
  public int[] dijkstrasAlgorithms(int start, int[][][] edges) {
    // edge[][][]: 0,1 edge relation | 2 weight
    // graph => edge list
    int n = edges.length;
    PriorityQueue<Vertex> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

    int[] shortestPath = new int[n];
    Arrays.fill(shortestPath, Integer.MAX_VALUE);
    boolean[] done = new boolean[n];
    shortestPath[start] = 0;
    pq.add(new Vertex(start, 0));
    while (!pq.isEmpty()) {
      Vertex node = pq.poll();
      for (int[] edge : edges[node.label]) {
        int u = node.label;
        int v = edge[0];
        int w = edge[1];
        // Edge relaxation
        if (!done[v] && shortestPath[u] + w < shortestPath[v]) {
          shortestPath[v] = shortestPath[u] + w;
          pq.add(new Vertex(v, shortestPath[v]));
        }
      }
      done[node.label] = true;
    }

    // Turn to -1, because starting point can't reach that label
    for (int i = 0; i < n; i++) {
      if (shortestPath[i] == Integer.MAX_VALUE) {
        shortestPath[i] = -1;
      }
    }
    return shortestPath;
  }
}

อันนี้ไว้อ่านเพิ่มเติม

Dijkstra's Algorithm

Bellman-Ford’s Algorithm

หนึ่งใน Single Source Shortest Path (SSSP) algorithm ในการหาระยะทางที่สั้นที่สุดจาก Vertex สู่ Vertex เช่นกันกับ Dijkstra’s algorithm แต่ทว่า Bellman-Ford’s algorithm จะสามารถรองรับกับ Negative edge weights ได้ แต่ Dijkstra’s algorithm ไม่สามารถทำได้ แต่ช้ากว่าเยอะเลยล่ะ

หลักการคือ ทำวนไปอย่างงั้นอ่ะ N-1 รอบ โดยที่ N คือจำนวนของ Vertices ที่มี ทำไปจนกว่า Weight ในแต่ละรอบไม่เปลี่ยน ด้านล่างนี้ก็โค้ดของผู้เขียนจากตรงนี้

แล้วถ้าเกิดว่า N-1 รอบ แล้วมันยังเปลี่ยนอยู่ล่ะ อ่อ ช่างมันเรื่อง Shortest Path ละงั้น เราเจอ Negative Weight Cycle แล้ว คือในแต่ละรอบ มันลบอยู่นั่นล่ะ ไม่เจอละทางที่สั้นที่สุด

• ถ้าภายใน N-1 รอบ Weight result ไม่เปลี่ยน => เจอ Shortest Path
• ถ้าครบ N-1 รอบ Weight result เปลี่ยนไปเรื่อย => เจอ Negative Weight Cycle

Time Complexity: O(V * E)

public class BellmanFordAlgorithms {

  // Single Source Shortest Path algorithms - Handle negative weight
  // But if guarantee all the weight are positive => prefer to use Dijsktra for faster
  public BellmanFordResult bellmanFordAlgorithm(List<Edge> edges, int N, int src) {
    int[] dist = new int[N];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    boolean isHaveUpdate = false;

    // Bellman-Ford
    // ทำไปเรื่อย ๆ ด้วย Loop ใหญ่ N - 1 รอบ หรือจนรอบนั้น ๆ ไม่มีการ relaxation อีกแล้ว
    for (int i = 0; i < N - 1; i++) {
      for (Edge e : edges) {
        if (dist[e.u] + e.weight < dist[e.v]) {
          dist[e.v] = dist[e.u] + e.weight;
          isHaveUpdate = true;
        }
      }
      if (!isHaveUpdate) {
        return new BellmanFordResult(dist, false);
      }
    }
    // If it updated until N - 1
    // we should check negative weight cycle
    // if we do optional round and update => We found NEGATIVE WEIGHT CYCLE
    for (Edge e : edges) {
      if (dist[e.u] + e.weight < dist[e.v]) {
        Arrays.fill(dist, Integer.MAX_VALUE);
      }
    }
    return new BellmanFordResult(dist, true);
  }

  public static class BellmanFordResult {

    public int[] dist;
    public boolean isFoundNegativeWeightCycle;

    public BellmanFordResult(int[] dist, boolean isFoundNegativeWeightCycle) {
      this.dist = dist;
      this.isFoundNegativeWeightCycle = isFoundNegativeWeightCycle;
    }
  }
}

อันนี้ไว้อ่านเพิ่มเติม

Bellman Ford's Algorithm

Disjoint Set (Union Find)

Disjoint Set (หรือเรียกอีกอย่างว่า Union Find) เป็นโครงสร้างข้อมูลที่ใช้ Keep track partition ของ element ให้เป็นชุดย่อย ๆ ที่แยกจากกัน มักใช้เพื่อหา connected components ใน graph (กราฟมันเชื่อมกันรึเปล่า)

Operations ที่ใช้งานหลัก ๆ คือ

• union(x, y) ใช้ในการรวม subset ที่มี element x, y อยู่ให้รวมกัน
• find(x) ใช้ในการหา root ของ subset ที่มี element x อยู่

ตามชื่อมันเลยใช่มั้ยล่ะ Union-Find 5555555 ด้านล่างก็จะเป็นการ Implementation ของ Union-Find ตัวอย่างโค้ดผมใน GitHub

package common.unionfind;

public class UnionFindNumArr implements UnionFind<Integer> {

  public int[] parent;
  public int[] rank;
  public int size;

  public UnionFindNumArr(int size) {
    this.size = size;
    this.parent = new int[size];
    this.rank = new int[size];
    for (int i = 0; i < size; i++) {
      this.parent[i] = i;
      this.rank[i] = 0;
    }
  }

  @Override
  public boolean union(Integer x, Integer y) {
    int rootX = this.find(x);
    int rootY = this.find(y);
    if (rootX != rootY) {
      int rankX = this.rank[rootX];
      int rankY = this.rank[rootY];
      if (rankX > rankY) {
        this.rank[rootY] = rootX;
      } else if (rankX < rankY) {
        this.rank[rootX] = rootY;
      } else {
        this.rank[rootX] = rootY;
        this.rank[rootY]++;
      }
      return true;
    }
    return false;
  }

  @Override
  public Integer find(Integer x) {
    if (this.parent[x] == x) {
      return x;
    }
    // Path compression
    return this.parent[x] = this.find(this.parent[x]);
  }
}

แล้วถ้าเกิดว่ามันไม่ใช่ตัวเลขล่ะ เราจะทำยังไง โอเค ใช้ Array ไม่ได้ล่ะ เอาให้ Dynamic หน่อยละกัน ผมเลือกใช้ HashTable แทน ตัวอย่างโค้ดผมใน GitHub

package common.unionfind;

import java.util.HashMap;
import java.util.Map;

public class UnionFindMap<T> implements UnionFind<T> {

  public Map<T, T> parent;
  public Map<T, Integer> rank;

  public UnionFindMap() {
    this.parent = new HashMap<>();
    this.rank = new HashMap<>();
  }

  private void preRequisiteCheck(T e) {
    this.parent.putIfAbsent(e, e);
    this.rank.putIfAbsent(e, 0);
  }

  @Override
  public boolean union(T x, T y) {
    this.preRequisiteCheck(x);
    this.preRequisiteCheck(y);

    T rootX = this.find(x);
    T rootY = this.find(y);

    if (rootX != rootY) {
      int rankX = this.rank.get(x);
      int rankY = this.rank.get(y);
      if (rankX > rankY) {
        this.parent.put(y, x);
      } else if (rankX < rankY) {
        this.parent.put(x, y);
      } else {
        this.parent.put(x, y);
        this.rank.put(rootY, rankY + 1);
      }
      return true;
    }
    return false;
  }

  @Override
  public T find(T x) {
    // Path compression
    if (this.parent.get(x) != x) {
      this.parent.put(x, find(this.parent.get(x)));
    }
    return this.parent.get(x);
  }
}

และตัวอย่างที่จะนำมาเสนอคือ Leetcode 547. Number of Provinces ในโจทย์มีกี่จังหวัด ถ้าให้ connected relation มา 😳

public class NumberOfProvinces_547 {
    public int findCircleNum(int[][] isConnected) {
        int size = isConnected.length;
        UnionFind uf = new UnionFind(size);
        for (int a = 0; a < size; a++) {
            for (int b = 0; b < size; b++) {
                if (isConnected[a][b] == 1) {
                    uf.union(a, b);
                }
            }
        }
        Set<Integer> provinces = new HashSet<>();
        for (int i = 0; i < size; i++) {
            provinces.add(uf.find(i));
        }
        return provinces.size();
    }

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

        UnionFind(int universe) {
            parent = new int[universe];
            rank = new int[universe];
            for (int i = 0; i < universe; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public void union(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x != y) {
                if (rank[x] > rank[y]) {
                    parent[y] = x;
                } else if (rank[y] > rank[x]) {
                    parent[x] = y;
                } else {
                    parent[x] = y;
                    rank[y] += 1;
                }
            }
        }

        public int find(int a) {
            if (parent[a] == a) {
                return a;
            }
            return parent[a] = find(parent[a]);
        }
    }
}

บทนี้เป็นบทที่สนุกมั้ยครับทุกท่าน ผมนี่ตาล้าเลย 5555 หวังว่าทุกคนจะได้รับประโยชน์และได้อะไรไปจากบทความนี้ไม่มากก็น้อยนะครับ ถ้าตรงไหนที่มันลึกเกินไปสำหรับ Non-Tech ก็ขออภัยด้วยนะครับ เพราะผมก็เหมือนบันทึกและรื้อฟื้นตัวเองเหมือนกัน 🙇‍♂️

ไว้เจอกันใหม่บทความต่อไปของซีรีย์ครับ สวัสดีครับ ขอให้ทุกคนมีความสุขครับ ✌️

FB ไว้ตอบปัญหา: Thanaphoom Babparn
FB Page ไว้ตอบปัญหา & แชร์ไปเรื่อย: TP Coder
LinkedIn: Thanaphoom Babparn
Linktree: https://linktr.ee/tpbabparn