Leet code

Min Cost to Connect All Points

Ref: https://leetcode.com/problems/min-cost-to-connect-all-points/description/

คุณมีชุดข้อมูล points ซึ่งเป็นพิกัดของจุดต่างๆ บนระนาบ 2 มิติ โดย points[i] = [xi, yi] ค่าใช้จ่ายในการเชื่อมต่อจุดสองจุด [xi, yi] และ [xj, yj] คือระยะทางแมนฮัตตันระหว่างจุดทั้งสอง: |xi - xj| + |yi - yj|
ภารกิจของคุณคือ หาค่าใช้จ่ายต่ำสุดในการเชื่อมต่อทุกจุดให้ถึงกัน โดยที่ จุดทุกจุดจะถือว่าเชื่อมต่อถึงกัน ก็ต่อเมื่อมีเส้นทางเดียว (simple path) ระหว่างจุดสองจุดใดๆ
**ตัวอย่าง (ตาม leet code): **

points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
ผลลัพธ์: 20

คำอธิบาย:

เราสามารถเชื่อมต่อจุดต่างๆ ดังนี้
(0,0) -- (2,2) -- (5,2) -- (7,0) -- (3,10)
ค่าใช้จ่ายรวม = 2 + 3 + 2 + 10 + 3 = 20

โจทย์นี้สามารถแก้ไขได้โดยใช้แนวคิด Minimum Spanning Tree (MST) ซึ่งมีสองอัลกอริทึมหลักที่เหมาะสม ได้แก่ อัลกอริทึมของ Kruskal และอัลกอริทึมของ Prim
อัลกอริทึมของ Kruskal:

1. สร้างเส้นเชื่อม (Edge Creation): สร้างเส้นเชื่อมที่เป็นไปได้ทั้งหมดระหว่างจุดต่างๆ และคำนวณระยะทางแมนฮัตตันของแต่ละเส้น
2. เรียงลำดับเส้นเชื่อม (Sorting Edges): เรียงลำดับเส้นเชื่อมทั้งหมดตามน้ำหนัก (ระยะทาง) จากน้อยไปมาก
3. Union-Find: ใช้วิธี Union-Find เพื่อเพิ่มเส้นเชื่อมเข้าไปใน MST โดยไม่ให้เกิดวงวน
4. เพิ่มเส้นเชื่อม (Adding Edges): เพิ่มเส้นเชื่อมทีละเส้นจากรายการที่เรียงลำดับแล้วเข้าไปใน MST จนกว่าจุดทั้งหมดจะเชื่อมต่อกัน

อธิบายเพิ่มเติม:

• Minimum Spanning Tree (MST): คือต้นไม้ที่เชื่อมต่อจุดทั้งหมดในกราฟ โดยมีผลรวมของน้ำหนักเส้นเชื่อมน้อยที่สุด
• Union-Find: เป็นโครงสร้างข้อมูลที่ใช้ตรวจสอบว่าจุดสองจุดอยู่ในกลุ่มเดียวกันหรือไม่ และรวมกลุ่มเข้าด้วยกันได้อย่างมีประสิทธิภาพ

นี่คือ code c++ ของ solution ข้อนี้

class Solution {
public:
  struct Edge {
    int src, dest, weight;
  };

  struct Subset {
    int parent, rank;
  };

  int find(vector<Subset> &subsets, int i) {
    if (subsets[i].parent != i) {
      subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
  }

  void unionSubsets(vector<Subset> &subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank) {
      subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
      subsets[yroot].parent = xroot;
    } else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  int minCostConnectPoints(vector<vector<int>> &points) {
    int n = points.size();
    vector<Edge> edges;

    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        int weight =
            abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
        edges.push_back({i, j, weight});
      }
    }

    sort(edges.begin(), edges.end(),
         [](Edge a, Edge b) { return a.weight < b.weight; });

    vector<Subset> subsets(n);
    for (int v = 0; v < n; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }

    int result = 0;
    for (Edge &edge : edges) {
      int x = find(subsets, edge.src);
      int y = find(subsets, edge.dest);

      if (x != y) {
        result += edge.weight;
        unionSubsets(subsets, x, y);
      }
    }

    return result;
  }
};

คำอธิบาย:

• เริ่มต้น (Initialization): สร้างกราฟและเส้นเชื่อมทั้งหมด พร้อมคำนวณระยะทาง
• เรียงลำดับ (Sorting): เรียงลำดับเส้นเชื่อมตามน้ำหนักจากน้อยไปมาก
• Union-Find: ใช้ Union-Find เพื่อตรวจสอบว่าการเพิ่มเส้นเชื่อมแต่ละครั้งจะไม่ทำให้เกิดวงวนในกราฟ
• ผลลัพธ์ (Result): เมื่อทำครบทุกขั้นตอน จะได้เส้นเชื่อมทั้งหมดที่ประกอบเป็น MST และค่าใช้จ่ายรวมในการเชื่อมต่อจุดทั้งหมด

สรุป:
การใช้อัลกอริทึมของ Kruskal ช่วยให้เราสามารถคำนวณค่าใช้จ่ายต่ำสุดในการเชื่อมต่อจุดทั้งหมดได้อย่างมีประสิทธิภาพ

Network Delay Time

Ref: https://leetcode.com/problems/network-delay-time/description/
คุณมีเครือข่ายที่มีจุด (node) จำนวน n จุด โดยแต่ละจุดมีหมายเลขกำกับตั้งแต่ 1 ถึง n และมีรายการ times ซึ่งบอกเวลาเดินทางระหว่างจุดต่างๆ ในรูปแบบของเส้นเชื่อมมีทิศทาง (directed edge) โดย times[i] = (ui, vi, wi) หมายถึงว่ามีเส้นเชื่อมจากจุด ui ไปยังจุด vi ที่ใช้เวลาเดินทาง wi หน่วยเวลา
สัญญาณถูกส่งออกไปจากจุด k จุดใดจุดหนึ่ง เป้าหมายคือหาเวลาที่น้อยที่สุดที่ใช้ในการส่งสัญญาณไปถึงทุกๆ จุดในเครือข่าย ถ้าไม่สามารถส่งสัญญาณไปถึงทุกจุดได้ ให้คืนค่า -1
ตัวอย่าง:

n = 5, times = [[2,1,1],[2,3,1],[3,4,1]], k = 2
ผลลัพธ์: 2

คำอธิบาย: สัญญาณเริ่มต้นที่จุด 2 จากนั้นใช้เวลา 1 หน่วยเวลาไปยังจุด 1 และ 3 และใช้เวลาอีก 1 หน่วยเวลาไปยังจุด 4 รวมเป็น 2 หน่วยเวลาในการส่งสัญญาณไปถึงทุกจุด
Solution
ในการแก้ปัญหานี้ เราต้องหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้น k ไปยังจุดอื่นๆ ทั้งหมดในเครือข่าย นี่เป็นปัญหาการหาเส้นทางที่สั้นที่สุดแบบคลาสสิก ซึ่งสามารถแก้ไขได้อย่างมีประสิทธิภาพโดยใช้อัลกอริทึมของ Dijkstra
วิธีการ: อัลกอริทึมของ Dijkstra

1. เริ่มต้นโครงสร้างข้อมูล:

• ใช้ adjacency list เพื่อแสดงกราฟ (adjacency list คือวิธีการเก็บข้อมูลกราฟโดยเก็บรายชื่อจุดที่เชื่อมต่อกับจุดนั้นๆ)
• ใช้ priority queue (คิวลำดับความสำคัญ) เพื่อให้สามารถเลือกจุดที่มีระยะทางที่รู้จักน้อยที่สุดได้ตลอดเวลา
• ใช้ distance array (อาร์เรย์เก็บระยะทาง) เพื่อติดตามระยะทางที่สั้นที่สุดที่รู้จักไปยังแต่ละจุด

2. ขั้นตอนของอัลกอริทึม:

• กำหนดระยะทางไปยังจุดเริ่มต้น k เป็น 0 และจุดอื่นๆ ทั้งหมดเป็น infinity (ระยะอนันต์)
• ใส่จุดเริ่มต้น k เข้าไปใน priority queue
• ทำซ้ำจนกว่า priority queue จะว่าง:
  • ดึงจุดที่มีระยะทางน้อยที่สุดออกมาจาก priority queue
  • สำหรับแต่ละจุดที่เชื่อมต่อกับจุดที่ดึงออกมา ให้ปรับปรุงระยะทางถ้าพบเส้นทางที่สั้นกว่า และใส่ระยะทางที่ปรับปรุงแล้วเข้าไปใน priority queue
• หลังจากประมวลผลทุกจุดแล้ว ค่ามากที่สุดใน distance array จะแสดงถึงเวลาที่สัญญาณใช้ในการไปถึงจุดที่ไกลที่สุด ถ้ายังมีจุดใดที่ถูกตั้งค่าเป็น infinity ให้คืนค่า -1

#include <limits.h>
#include <queue>
#include <vector>

using namespace std;

class Solution {
public:
  int networkDelayTime(vector<vector<int>> &times, int n, int k) {
    // Create an adjacency list
    vector<vector<pair<int, int>>> adj(n + 1);
    for (const auto &time : times) {
      int u = time[0], v = time[1], w = time[2];
      adj[u].emplace_back(v, w);
    }

    // Min-heap priority queue to store (distance, node)
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pq;
    pq.emplace(0, k);

    // Distance array to store the shortest distance to each node
    vector<int> dist(n + 1, INT_MAX);
    dist[k] = 0;

    while (!pq.empty()) {
      auto [currDist, u] = pq.top();
      pq.pop();

      if (currDist > dist[u])
        continue; // Ignore if we have already found a shorter way

      for (const auto &[v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
          dist[v] = dist[u] + w;
          pq.emplace(dist[v], v);
        }
      }
    }

    // Find the maximum distance to any node
    int maxDist = 0;
    for (int i = 1; i <= n; ++i) {
      if (dist[i] == INT_MAX)
        return -1; // If any node is unreachable
      maxDist = max(maxDist, dist[i]);
    }

    return maxDist;
  }
};

คำอธิบาย:

• adjacency list ใช้ในการจัดเก็บข้อมูลโครงสร้างของกราฟ
• priority queue ช่วยให้เราสามารถดึงจุด (node) ที่มีระยะทางน้อยที่สุดออกมาได้อย่างมีประสิทธิภาพ
• distance array ใช้ในการติดตามระยะทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังแต่ละจุด
• อัลกอริทึมจะทำการประมวลผลแต่ละจุดซ้ำๆ โดยปรับปรุงเส้นทางที่สั้นที่สุดไปยังจุดที่อยู่ติดกัน

วิธีนี้ช่วยให้เราสามารถหาเส้นทางที่สั้นที่สุดไปยังทุกจุดในเครือข่าย โดยมีประสิทธิภาพในการทำงานเป็น 𝑂((𝑉+𝐸)log⁡𝑉) ซึ่ง V คือจำนวนจุด และ E คือจำนวนเส้นเชื่อม

สรุป

สิ่งที่เราเรียนรู้เรื่อง graph ไปทั้งหมดมีตั้งแต่

1. Representation of Graphs:
   • Adjacency Matrix: ใช้เพื่อเก็บข้อมูลเกี่ยวกับการเชื่อมต่อของกราฟในรูปแบบของเมทริกซ์ ใช้พื้นที่ 𝑂(𝑉2)O(V2) และมีประโยชน์เมื่อกราฟมีการเชื่อมต่อหนาแน่น (dense graph).
   • Adjacency List: ใช้เก็บข้อมูลการเชื่อมต่อของกราฟในรูปแบบของลิสต์ ใช้พื้นที่ 𝑂(𝑉+𝐸)O(V+E) และมีประสิทธิภาพดีกว่าในกราฟที่มีการเชื่อมต่อเบาบาง (sparse graph).
2. Traversal Algorithms:
   • Depth-First Search (DFS): ใช้ในการสำรวจกราฟโดยการลึกเข้าไปในเส้นทางหนึ่งก่อน ใช้สำหรับการค้นหาวงจร (cycle detection) และการค้นหาเส้นทาง (path finding).
   • Breadth-First Search (BFS): ใช้ในการสำรวจกราฟโดยการค้นหาทั้งหมดในระดับเดียวกันก่อน ใช้ในการค้นหาเส้นทางที่สั้นที่สุดในกราฟที่ทุกขอบมีน้ำหนักเท่ากัน (unweighted graph).
3. Shortest Path Algorithms:
   • Dijkstra’s Algorithm: ใช้ในการหาค่าเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักไม่เป็นลบ ใช้โครงสร้างข้อมูล Priority Queue เพื่อเพิ่มประสิทธิภาพ.
   • Bellman-Ford Algorithm: ใช้ในการหาค่าเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักเป็นลบได้ และสามารถตรวจจับวงจรน้ำหนักลบ (negative weight cycle) ได้.
   • Floyd-Warshall Algorithm: ใช้ในการหาค่าเส้นทางที่สั้นที่สุดระหว่างทุกคู่ของจุดในกราฟ ใช้ Dynamic Programming.
4. Minimum Spanning Tree (MST) Algorithms:
   • Prim’s Algorithm: สร้าง MST โดยการเลือกเส้นเชื่อมที่น้ำหนักน้อยที่สุดที่เชื่อมกับต้นไม้ที่สร้างไปแล้ว ใช้ Priority Queue เพื่อเพิ่มประสิทธิภาพ.
   • Kruskal’s Algorithm: สร้าง MST โดยการเรียงลำดับเส้นเชื่อมทั้งหมดตามน้ำหนักและเพิ่มเส้นเชื่อมที่น้ำหนักน้อยที่สุดเข้าไปในต้นไม้ครอบคลุม โดยใช้ Union-Find เพื่อจัดการกับการรวมกันของจุดที่เชื่อมต่อ.

เหตุผลที่ควรศึกษา Graph Algorithms

1. ความเข้าใจและการแก้ปัญหาที่ซับซ้อน: การศึกษา Graph Algorithms ช่วยให้เราเข้าใจโครงสร้างและการทำงานของปัญหาต่างๆ ที่สามารถแทนด้วยกราฟ เช่น เครือข่ายคอมพิวเตอร์, ระบบขนส่ง, และการวิเคราะห์เครือข่ายสังคม.
2. การประยุกต์ใช้ในวิศวกรรมและวิทยาศาสตร์ข้อมูล: Graph Algorithms ถูกใช้ในการออกแบบและวิเคราะห์เครือข่ายต่างๆ ในวิศวกรรม และการค้นหาและวิเคราะห์ข้อมูลในวิทยาศาสตร์ข้อมูล เช่น การค้นหาการเชื่อมต่อในฐานข้อมูล, การวิเคราะห์โครงสร้างของเครือข่ายสังคม, และการคำนวณเส้นทางที่เหมาะสมในระบบขนส่ง.
3. พื้นฐานของการพัฒนาและวิจัยในคอมพิวเตอร์: Graph Algorithms เป็นพื้นฐานในการพัฒนาอัลกอริทึมที่ซับซ้อนและการวิจัยในสาขาคอมพิวเตอร์. ความรู้ในด้านนี้ช่วยให้สามารถสร้างและปรับปรุงอัลกอริทึมที่มีประสิทธิภาพสูงขึ้นได้.
4. การแก้ปัญหาจริงในโลกธุรกิจและอุตสาหกรรม: ปัญหาหลายอย่างในโลกธุรกิจและอุตสาหกรรมสามารถแทนด้วยกราฟ เช่น การวางแผนเส้นทางการขนส่งสินค้า, การจัดการโครงสร้างพื้นฐาน, และการวิเคราะห์ข้อมูลการเงิน.

สรุป
การศึกษา Graph Algorithms เป็นสิ่งสำคัญในการพัฒนาทักษะการแก้ปัญหาที่ซับซ้อนและการประยุกต์ใช้ในหลายๆ ด้านของวิศวกรรม, วิทยาศาสตร์ข้อมูล, และการวิจัยในคอมพิวเตอร์.