กราฟ (Graph)

# 1. การแทนค่ากราฟ การแทนค่ากราฟเป็นแนวคิดพื้นฐานในวิทยาการคอมพิวเตอร์ กราฟ $G$ นิยามว่าเป็นคู่ $(V, E)$ โดยที่: - $V$ คือเซตของจุด (vertices) - $E$ คือเซตของขอบ (edges) ขอบในกราฟอาจมีทิศทางหรือไม่มีทิศทาง และอาจมีน้ำหนักประกอบอยู่ด้วย การเลือกวิธีการแทนค่าที่เหมาะสมมีความสำคัญต่อประสิทธิภาพของอัลกอริทึมที่นำไปใช้กับกราฟ > **หมายเหตุ:** > โจทย์ส่วนใหญ่กำหนด index เป็นเลข 1 ถึง n แต่ตามปกติแล้ว array หรือ vector ขนาด n จะรองรับได้แค่เลข 0 ถึง n-1 เท่านั้น มีวิธีแก้ปัญหาสองแบบคือ > - เมื่อ input ต้องการให้จัดการกับข้อมูล ณ ตำแหน่ง x ก็ให้เลื่อนมาจัดการกับตำแหน่ง x-1 ใน array จริง ๆ แทน > - กำหนดขนาดของ array เป็น n+1 เพื่อที่จะได้ใช้ตำแหน่ง n ได้ ส่วนตำแหน่ง 0 เราจะไม่พิจารณาเลย ## 1.1 เมทริกซ์ความสัมพันธ์ (Adjacency Matrix) ### นิยาม เมทริกซ์ความสัมพันธ์สำหรับกราฟที่มี $N$ จุด คือเมทริกซ์ขนาด $N \times N$ โดยที่แต่ละองค์ประกอบ $a_{ij}$ แสดงถึงการมีอยู่ของขอบจากจุด $i$ ไปยังจุด $j$ โดยมีเงื่อนไขดังนี้: - $a_{ij} = 1$ ถ้ามีขอบจาก $i$ ไป $j$ - $a_{ij} = 0$ หากไม่มีขอบ ในกราฟที่ไม่มีทิศทาง เมทริกซ์จะเป็นแบบสมมาตร คือ $a_{ij} = a_{ji}$ #### ตัวอย่าง ![Screenshot 2025-03-15 at 19.17.30](https://hackmd.io/_uploads/B1oble7nkl.png) สำหรับกราฟที่มีจุด $V = \{1, 2, 3, 4\}$ และขอบ $E = \{(1,2), (2,3), (2,4),(3,4), (4,1)\}$ เมทริกซ์ความสัมพันธ์จะเป็น: ![Screenshot 2025-03-15 at 19.19.27](https://hackmd.io/_uploads/BkEvxlX3kg.png) โดยเมทริกซ์สามารถสร้างได้ด้วย ```cpp int adj[5][5]; adj[1][2] = 1; adj[2][3] = 1; adj[2][4] = 1; adj[3][4] = 1; adj[4][1] = 1; ``` ### การแทนค่ากราฟแบบมีน้ำหนัก (Weighted Graph Representation) ในกราฟที่มีน้ำหนัก (weighted graph) การแทนค่าด้วยเมทริกซ์ความสัมพันธ์ สามารถปรับขยายได้โดยให้เมทริกซ์บรรจุน้ำหนักของขอบ (edge weight) ในตำแหน่งที่มีขอบอยู่ แทนที่จะเป็นเพียงค่า 1 หรือ 0 ดังนี้: - ถ้ามีขอบจาก $v_i$ ไปยัง $v_j$ ที่มีน้ำหนัก $w$ ให้กำหนดค่า $a_{ij} = w$ - ถ้าไม่มีขอบระหว่าง $v_i$ กับ $v_j$ ให้กำหนดค่า $a_{ij} = \infty$ (หรือใช้ค่าพิเศษอื่น ๆ แทนการไม่มีขอบ) - สำหรับกราฟที่ไม่มีทิศทาง เมทริกซ์จะมีความสมมาตร คือ $a_{ij} = a_{ji}$ และโดยทั่วไปจะกำหนดให้ $a_{ii} = 0$ สำหรับทุก $i$ เพราะระยะทางจากจุดหนึ่งไปยังตัวมันเองเท่ากับ 0 พิจารณากราฟที่มีจุดและมีขอบดังนี้: ![Screenshot 2025-03-15 at 19.27.44](https://hackmd.io/_uploads/rJWUfeQhyl.png) เมทริกซ์ความสัมพันธ์สำหรับกราฟนี้จะเป็น: ![Screenshot 2025-03-15 at 19.25.50](https://hackmd.io/_uploads/B1m1flXnJx.png) โดยเมทริกซ์สามารถสร้างได้ด้วย ```cpp int adj[5][5]; adj[1][2] = 5; adj[2][3] = 7; adj[2][4] = 6; adj[3][4] = 5; adj[4][1] = 2; ``` ### ข้อดีและข้อเสีย - **ข้อดี:** - เข้าใจง่ายและเหมาะสำหรับการตรวจสอบการมีอยู่ของขอบระหว่างจุดสองจุดในเวลา $O(1)$ - **ข้อเสีย:** - ใช้พื้นที่ $O(N^2)$ ซึ่งไม่เหมาะกับกราฟที่มีจุดจำนวนมากแต่มีขอบน้อย (sparse graph) --- ## 1.2 รายชื่อเพื่อนบ้าน (Adjacency List) ### นิยาม การแทนค่าด้วยรายชื่อเพื่อนบ้านคือการเก็บข้อมูลของแต่ละจุด $v$ โดยมีลิสต์ที่บรรจุจุดที่เชื่อมต่อกับ $v$ โดยสามารถสร้างได้ด้วย ```cpp vector<int> adj[N]; ``` #### ตัวอย่าง ![Screenshot 2025-03-15 at 19.38.42](https://hackmd.io/_uploads/Bk81Sl73ye.png) สำหรับกราฟเดียวกัน $V = \{1, 2, 3, 4\}$ และขอบ $E = \{(1,2), (2,3), (2,4),(3,4), (4,1)\}$ รายชื่อเพื่อนบ้านจะเป็น: - $L(1) = \{2\}$ - $L(2) = \{3, 4\}$ - $L(3) = \{4\}$ - $L(4) = \{1\}$ **ตัวอย่างโค้ดในภาษา C++:** ```cpp vector<int> adj[5]; // สำหรับ 4 จุด ไม่สนใจจุดยอด 0 adj[1].push_back(2); adj[2].push_back(3); adj[2].push_back(4); adj[3].push_back(4); adj[4].push_back(1); ``` หากประมวลผลกราฟที่ไม่มีทิศทางจะต้องใส่เพื่อนบ้านทั้งสองทิศทาง เช่น หากมีขอบ $(1, 2)$ ```cpp adj[1].push_back(2); adj[2].push_back(1); ``` ### การแทนค่ากราฟแบบมีน้ำหนัก การแทนค่ากราฟแบบมีน้ำหนักสามารถทำได้โดยเก็บค่าเพื่อนบ้านเป็น `pair<int, int>` ซึ่งแสดงถึงเพือนบ้านและน้ำหนัก ```cpp vector<pair<int,int>> adj[N]; ``` #### ตัวอย่าง ![Screenshot 2025-03-15 at 19.27.44](https://hackmd.io/_uploads/ByDiLg7hke.png) สามารถสร้างได้โดย ```cpp vector<pair<int,int>> adj[5]; adj[1].push_back({2,5}); adj[2].push_back({3,7}); adj[2].push_back({4,6}); adj[3].push_back({4,5}); adj[4].push_back({1,2}); ``` ### การเข้ถึงเพื่อนบ้านทำได้ง่ายโดย ```cpp for (auto u : adj[s]) { // process node u } ``` ### ข้อดีและข้อเสีย - **ข้อดี:** - ใช้พื้นที่ $O(N + M)$ เมื่อ $M$ คือจำนวนขอบ - เหมาะสำหรับการเข้าถึงเพื่อนบ้านของจุดหนึ่ง ๆ ได้อย่างรวดเร็ว - **ข้อเสีย:** - การตรวจสอบว่ามีขอบระหว่างจุด $u$ กับ $v$ อาจต้องใช้เวลา $O(\text{degree}(u))$ ในกรณีที่แย่ที่สุด --- ## 1.3 รายชื่อขอบ (Edge List) ### นิยาม รายชื่อขอบคือการแทนค่ากราฟโดยการเก็บรายการของขอบแต่ละอัน ซึ่งแต่ละขอบจะถูกแทนด้วย: - คู่ $(u, v)$ สำหรับกราฟที่ไม่มีน้ำหนัก - หรือทริปเปิล $(u, v, w)$ สำหรับกราฟที่มีน้ำหนัก #### ตัวอย่าง ![Screenshot 2025-03-15 at 19.38.42](https://hackmd.io/_uploads/Bk81Sl73ye.png) ```cpp vector<pair<int,int>> edges; edges.push_back({1,2}); edges.push_back({2,3}); edges.push_back({2,4}); edges.push_back({3,4}); edges.push_back({4,1}); ``` #### ตัวอย่าง ![Screenshot 2025-03-15 at 19.27.44](https://hackmd.io/_uploads/ByDiLg7hke.png) สามารถสร้างได้โดย ```cpp vector<tuple<int,int,int>> edges; edges.push_back({1,2,5}); edges.push_back({2,3,7}); edges.push_back({2,4,6}); edges.push_back({3,4,5}); edges.push_back({4,1,2}); ``` ### ข้อดีและข้อเสีย - **ข้อดี:** - การแทนค่าเรียบง่ายและตรงไปตรงมา - เหมาะสำหรับอัลกอริทึมที่ต้องเรียงลำดับขอบ เช่น Kruskal’s MST - **ข้อเสีย:** - ไม่เหมาะสำหรับการตรวจสอบว่ามีขอบระหว่างจุดสองจุดในเวลาเร็ว - การเข้าถึงเพื่อนบ้านของจุดหนึ่งต้องสแกนรายชื่อขอบทั้งหมด ## สรุป การเลือกวิธีการแทนค่ากราฟขึ้นอยู่กับลักษณะของกราฟและปัญหาที่ต้องแก้: - **เมทริกซ์ความสัมพันธ์** เหมาะสำหรับกราฟที่หนาแน่นและต้องการตรวจสอบขอบได้ในเวลา $O(1)$ - **รายชื่อเพื่อนบ้าน** เหมาะสำหรับกราฟที่มีขอบน้อย (sparse graph) ด้วยการใช้พื้นที่ $O(N + M)$ - **รายชื่อขอบ** มีความเรียบง่ายและเหมาะสำหรับอัลกอริทึมที่ต้องประมวลผลขอบทั้งหมด เช่น Kruskal’s MST - https://visualgo.net/en/graphds --- # 2. Graph Traversal อัลกอริทึมกราฟพื้นฐานที่สำคัญสองแบบ ได้แก่ การค้นหาด้วยความลึก (Depth-First Search, DFS) และการค้นหาด้วยความกว้าง (Breadth-First Search, BFS) โดยทั้งสองอัลกอริทึมจะได้รับจุดเริ่มต้นในกราฟ และทำการเยี่ยมชมทุกโหนดที่สามารถเข้าถึงได้จากจุดเริ่มต้นนั้น ความแตกต่างระหว่างอัลกอริทึมทั้งสองอยู่ที่ลำดับในการเยี่ยมชมโหนดแต่ละตัว ## 2.1 การค้นหาด้วยความลึกก่อน (Depth-First Search, DFS) การค้นหาด้วยความลึกก่อน (Depth-first search, DFS) เป็นเทคนิคการท่องกราฟที่ตรงไปตรงมา โดยอัลกอริทึมจะเริ่มต้นจากโหนดเริ่มต้นหนึ่ง แล้วดำเนินการไปยังโหนดอื่น ๆ ที่สามารถเข้าถึงได้จากโหนดเริ่มต้นผ่านทางขอบของกราฟ DFS จะติดตามเส้นทางเดียวในกราฟตราบเท่าที่ยังพบโหนดใหม่ เมื่อไม่สามารถค้นพบโหนดใหม่ได้แล้ว จะย้อนกลับไปยังโหนดก่อนหน้าและเริ่มสำรวจส่วนอื่น ๆ ของกราฟ อัลกอริทึมนี้จะจดจำโหนดที่เยี่ยมชมแล้ว เพื่อให้แน่ใจว่าแต่ละโหนดจะถูกประมวลผลเพียงครั้งเดียว ### การเขียน DFS การค้นหาด้วยความลึกก่อน สามารถเขียนได้อย่างสะดวกโดยใช้การเรียกซ้ำ (recursive) โดยจะเริ่มต้นการค้นหาด้วยความลึกจากโหนดที่กำหนด ```cpp= vector<int> adj[N]; bool visited[N]; //ตั้งค่าเริ่มต้นเป็น false void dfs(int s) { if (visited[s]) return; visited[s] = true; // process node s for (auto u: adj[s]) { dfs(u); } } ``` ## 2.1 การค้นหาด้วยความกว้างก่อน (Breadth-First Search,BFS) การค้นหาด้วยความกว้างก่อน (Breadth-first search, BFS) จะเข้าถึงโหนดต่าง ๆ ตามลำดับที่เพิ่มขึ้นของระยะห่างจากโหนดเริ่มต้น ด้วยเหตุนี้เราสามารถคำนวณระยะห่างจากโหนดเริ่มต้นไปยังโหนดอื่น ๆ ด้วยการใช้ BFS ### การเขียน BFS โดยทั่วไปแล้วเราจะใช้คิวในการจัดการโหนดที่ยังรอการประมวลผล สำหรับ BFS ซึ่งในแต่ละขั้นตอนจะประมวลผลโหนดที่อยู่ด้านหน้าของคิว จากนั้นจึงเพิ่มโหนดที่ยังไม่เยี่ยมชมที่อยู่ติดกันลงไปในท้ายคิว ```cpp= queue<int> q; bool visited[N]; int distance[N]; visited[x] = true; distance[x] = 0; q.push(x); while (!q.empty()) { int s = q.front(); q.pop(); // process node s for (auto u : adj[s]) { if (visited[u]) continue; visited[u] = true; distance[u] = distance[s]+1; q.push(u); } } ``` ## 2.3 การประยุกต์ใช้งาน Graph Traversal ### 2.3.1 การตรวจับ Cycle ใน Undirected Graph ด้วย DFS ในการตรวจจับ Cycle ในกราฟที่ไม่มีทิศทางโดยใช้ DFS จะทำการเข้าถึงโหนดตามเส้นทางหนึ่งอย่างต่อเนื่องจนกว่าจะไม่สามารถค้นพบโหนดใหม่ได้ ระหว่างทางจะบันทึกโหนดที่เยี่ยมชมแล้วไว้ในอาร์เรย์ visited เพื่อป้องกันการประมวลผลซ้ำ อีกทั้งยังต้องบันทึกข้อมูลของโหนดพ่อแม่ (parent) สำหรับแต่ละโหนดในเส้นทาง เพื่อให้สามารถแยกแยะระหว่างการกลับมาผ่าน edge เดิม (ซึ่งไม่ถือว่าเป็น cycle) กับการพบโหนดที่เคยเยี่ยมชมในเส้นทาง DFS ปัจจุบัน (ซึ่งหมายความว่ามี cycle เกิดขึ้น) ![Screenshot 2025-03-15 at 23.20.26](https://hackmd.io/_uploads/rJLkKQXn1e.png) **ข้อสังเกต** - การเก็บข้อมูล parent: เนื่องจากในกราฟไม่มีทิศทาง โหนด $u$ อาจเชื่อมกับโหนด $v$ และในระหว่างการ DFS อาจมีการเดินทางจาก $u$ ไป $v$ แล้วกลับจาก $v$ ไป $u$ ผ่าน edge เดิมได้ ดังนั้นจึงต้องบันทึกข้อมูล parent เพื่อไม่ให้เกิดการนับซ้ำ - การตรวจสอบทุกส่วนของกราฟ: เนื่องจากกราฟอาจประกอบด้วยหลายส่วน (disconnected components) จึงต้องทำการเรียก DFS สำหรับโหนดที่ยังไม่ถูกเยี่ยมชม เพื่อให้แน่ใจว่าได้ตรวจจับ cycle ครบทุกส่วนของกราฟ **ตัวอย่างโปรแกรม** ```cpp= // กำหนดขนาดสูงสุดของกราฟ const int N = 1001; bool visited[N]; // อาร์เรย์สำหรับบันทึกว่าโหนดถูกเยี่ยมชมแล้วหรือไม่ // ฟังก์ชัน DFS สำหรับตรวจจับ cycle // u คือโหนดปัจจุบัน, p คือ parent ของ u ในเส้นทาง DFS bool dfs(int u, int p) { // ถ้าโหนด u ถูกเยี่ยมชมแล้วในเส้นทาง DFS ปัจจุบัน // หมายความว่าได้เจอ cycle แล้ว if (visited[u]) return true; visited[u] = true; // วนรอบโหนดที่อยู่ติดกับ u for (int v : G[u]) { // ข้ามโหนดที่เป็น parent ของ u เพื่อป้องกันการนับ edge เดิมซ้ำ if (v == p) continue; // ถ้า DFS จากโหนด v พบ cycle ให้ return true ทันที if (dfs(v, u)) return true; } return false; // หากวนรอบทุกโหนดแล้วไม่พบ cycle } // ใน main function: bool found_cycle = false; for (int u = 1; u <= n; ++u) { // ตรวจสอบทุกโหนดในกราฟ เพราะกราฟอาจไม่เชื่อมต่อกันทั้งหมด if (!visited[u]) { if (dfs(u, -1)) { // ใช้ -1 เป็น parent ของโหนดเริ่มต้น found_cycle = true; break; } } } if (found_cycle) cout << "มี cycle" << "\n"; else cout << "ไม่มี cycle" << "\n"; ``` ### 2.3.2 การตรวจับ Cycle ใน Directed Graph ด้วย DFS การตรวจจับ cycle ในกราฟที่มีทิศทางด้วย DFS จำเป็นต้องใช้ตัวแปรสีแทนการใช้แค่ visited array เนื่องจากปัญหาการประมวลผลที่เกิดจากการเยี่ยมชมในรอบของ DFS ที่ต่างกัน โดยจะกำหนดสถานะของแต่ละโหนดด้วยสีดังนี้: - สีขาว (color 0): โหนดยังไม่ได้ถูกเยี่ยมชมเลย - สีเทา (color 1): โหนดถูกเยี่ยมชมแล้วและกำลังอยู่ในกระบวนการ DFS (อยู่ใน recursion stack) - สีดำ (color 2): โหนดถูกเยี่ยมชมแล้วและได้ทำการประมวลผลลูกของมันครบถ้วนแล้ว **กระบวนการทำงาน** - ในตอนแรก ทุกโหนดจะถูกกำหนดเป็นสีขาว (ค่าเริ่มต้นเป็น 0) - เมื่อเริ่มต้น DFS จากโหนดหนึ่ง เราจะเปลี่ยนสถานะของโหนดนั้นเป็นสีเทา (1) เพื่อบอกว่าโหนดนั้นกำลังอยู่ในกระบวนการ DFS - จากนั้นจะทำการเยี่ยมชมโหนดที่ติดกัน ถ้าเจอโหนดใดที่อยู่ในสถานะสีเทา (gray) หมายความว่าโหนดนั้นกำลังอยู่ใน stack อยู่แล้ว นั่นคือเราได้พบ cycle - หลังจากเยี่ยมชมและประมวลผลลูกของโหนดครบแล้ว เราจะเปลี่ยนสถานะของโหนดนั้นเป็นสีดำ (2) เพื่อบ่งบอกว่าโหนดนั้นได้รับการประมวลผลอย่างสมบูรณ์แล้ว **เหตุผลของการใช้ 3 สี** ยกตัวอย่างกราฟ `2->1->3` ในกรณีนี้ หากเราใช้เพียง visited array ในการตรวจจับ cycle โดยเริ่ม DFS จาก node 1 ก่อน เราจะทำให้ `visited[1] = true` และ `visited[3] = true` ซึ่งหมายความว่าเมื่อภายหลังเราเริ่ม DFS จาก node 2 แล้วจะพบว่า node 1 ถูก visited ไปแล้ว ทำให้ดูเหมือนว่าเกิด cycle ขึ้น (เพราะเจอ node 1 ที่เคยเยี่ยมชมแล้ว) แต่ความจริงแล้วในกราฟนี้ไม่มี cycle เกิดขึ้น เนื่องจากการเยี่ยมชม node 1 ในรอบ DFS จาก node 2 นั้นเป็นการเยี่ยมชมในบริบทของ DFS รอบใหม่ ไม่ใช่ใน DFS เดียวกัน **ตัวอย่างโปรแกรม** ```cpp= const int N = 1001; int color[N]; // เริ่มต้นทุกโหนดเป็นสีขาว (0) // ฟังก์ชัน DFS สำหรับตรวจจับ cycle ใน directed graph // u คือโหนดปัจจุบัน // คืนค่า true ถ้าพบ cycle, false ถ้าไม่พบ bool dfs(int u) { // หากโหนด u อยู่ในสถานะสีเทา (gray) หมายความว่าอยู่ใน recursion stack แล้ว // พบ cycle แล้ว if (color[u] == 1) return true; // หากโหนด u อยู่ในสถานะสีดำ (black) หมายความว่าได้ประมวลผลครบแล้วในรอบก่อนหน้า if (color[u] == 2) return false; // เปลี่ยนสถานะของ u เป็นสีเทา เพื่อบอกว่าเริ่ม DFS จาก u แล้ว color[u] = 1; // เยี่ยมชมโหนดที่ติดกับ u for (int v : G[u]) { if (dfs(v)) return true; } // เมื่อประมวลผลลูกครบแล้ว เปลี่ยนสถานะของ u เป็นสีดำ color[u] = 2; return false; } // ใน main function เราจะทำการเรียก DFS สำหรับทุกโหนดที่ยังไม่ได้ประมวลผล for (int u = 1; u <= n; ++u) { if (color[u] == 0) { if (dfs(u)) { // พบ cycle cout << "พบ cycle" << "\n"; break; } } } ``` ### 2.3.3 การนับจำนวน Component ในกราฟที่ไม่มีทิศทางด้วย DFS การคำนวณจำนวนของ connected components หรือกลุ่มของโหนดที่เชื่อมต่อกันในกราฟที่ไม่มีทิศทาง (undirected graph) สามารถทำได้โดยการใช้ DFS เพื่อระบุโหนดที่ถูกเยี่ยมชมแล้ว จากนั้นนับจำนวนครั้งที่ต้องเริ่มต้น DFS ใหม่ในกราฟ ซึ่งแต่ละครั้งจะครอบคลุม component หนึ่ง ![Screenshot 2025-03-15 at 23.20.57](https://hackmd.io/_uploads/HkHSt7Q2ke.png) **ตัวอย่างโปรแกรม** ```cpp= bool visited[N]; // กำหนดให้ทุกตำแหน่งเป็น false ตั้งแต่เริ่มต้น // ฟังก์ชัน DFS สำหรับมาร์คโหนดที่เชื่อมต่อกันใน component เดียวกัน void dfs(int u) { if (visited[u]) return; visited[u] = true; for (auto v : G[u]) dfs(v); } // ใน main: int component = 0; for (int u = 1; u <= n; ++u) { if (!visited[u]) { ++component; dfs(u); // DFS เพื่อมาร์คโหนดทั้งหมดใน component นี้ } } ``` > **หมายเหตุ:** > การนับจำนวน Component ในกราฟที่มีทิศทางสามารถแบ่งออกเป็นสองแบบหลัก: > - Strongly Connected Components (SCC): นั่นคือ ชุดของโหนดที่ในแต่ละคู่ของโหนดในชุดนั้น สามารถเข้าถึงกันและกันได้โดยใช้ทางเดินที่มีทิศทาง (directed path) สามารถทำได้ด้วยอัลกอริทึมอย่าง Kosaraju’s หรือ Tarjan’s Algorithm > - Weakly Connected Components: หากละเว้นทิศทางของ edge แล้วมองกราฟเป็นแบบไม่มีทิศทาง (undirected graph) การนับ connected component ในกราฟที่ได้จะเป็นการนับ weakly connected components วิธีนี้สามารถทำได้โดยการใช้ DFS หรือ BFS เหมือนกับกราฟไม่มีทิศทาง ### 2.3.4 การหาเส้นทางสั้นสุดในกราฟที่ไม่มีน้ำหนักด้วย BFS เนื่องจากกราฟที่ไม่มีน้ำหนัก ทุก edge มีค่าเท่ากัน (มักถือว่ามีค่าเป็น 1) การใช้ Breadth-first Search (BFS) จะเป็นวิธีที่เหมาะสมในการหาเส้นทางที่สั้นสุดระหว่างโหนดสองตัว เนื่องจาก BFS จะทำการเยี่ยมชมโหนดโดยเรียงลำดับตามระดับความลึกจากโหนดเริ่มต้น (level by level) **ตัวอย่างโปรแกรม** ```cpp= #include <algorithm> #include <iostream> #include <queue> #include <vector> using namespace std; const int N = 1000; // กำหนดขนาดสูงสุดของโหนดในกราฟ vector<int> G[N]; // กราฟที่เก็บในรูปแบบรายชื่อเพื่อนบ้าน int level[N]; // อาร์เรย์เก็บระดับ (ระยะทาง) จากโหนดเริ่มต้น int shortest_path(int start, int target) { // กำหนดค่าเริ่มต้นให้กับทุกตำแหน่งใน level เป็น -1 (ยังไม่เยี่ยมชม) fill(level, level + N, -1); queue<int> Q; level[start] = 0; Q.push(start); while (!Q.empty()) { int u = Q.front(); Q.pop(); // ถ้าเจอโหนดเป้าหมาย ให้คืนค่าระยะทางของโหนดนั้น if (u == target) return level[u]; // เยี่ยมชมโหนดที่เชื่อมต่อกับ u for (int v : G[u]) { // ถ้าโหนด v ยังไม่ถูกเยี่ยมชม if (level[v] == -1) { level[v] = level[u] + 1; Q.push(v); } } } // ถ้าไม่พบเส้นทางให้คืนค่า -1 return -1; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // ตัวอย่างการอ่านกราฟและเรียกใช้ฟังก์ชัน shortest_path int n, m; cin >> n >> m; for (int i = 0; i < m; i++){ int u, v; cin >> u >> v; // สมมุติว่ากราฟไม่มีทิศทาง G[u].push_back(v); G[v].push_back(u); } int start, target; cin >> start >> target; int distance = shortest_path(start, target); if (distance != -1) cout << "ระยะทางจาก " << start << " ถึง " << target << " = " << distance << "\n"; else cout << "ไม่มีเส้นทางจาก " << start << " ถึง " << target << "\n"; return 0; } ``` ### 2.3.5 เพื่อตรวจสอบ Bipartite Graph หรือ 2-coloring graph ด้วย DFS **นิยามของ Bipartite Graph:** กราฟจะเป็น Bipartite Graph ก็ต่อเมื่อสามารถแบ่งชุดของโหนดออกเป็นสองกลุ่ม (สองสี) โดยที่ไม่มีขอบเชื่อมระหว่างโหนดในกลุ่มเดียวกัน กล่าวคือ ทุกขอบจะเชื่อมระหว่างโหนดในกลุ่มที่ต่างกัน โดยกำหนด - ค่า 0 หมายถึงยังไม่ได้ระบายสี - ค่า 1 หมายถึงระบายด้วยสีแรก - ค่า 2 หมายถึงระบายด้วยสีที่สอง **กระบวนการ** เมื่อเริ่มต้น DFS จากโหนดหนึ่ง เราจะระบายสีโหนดนั้นด้วยสีที่กำหนด (เช่นสี 1) แล้วทำการ DFS ไปยังโหนดที่ติดกัน โดยสลับสีให้กับโหนดที่เชื่อมต่อกัน - หากเจอโหนดที่เคยระบายสีแล้วและสีที่ระบายไม่ตรงกับสีที่คาดหวัง (จากการสลับสี) ให้สรุปว่าไม่เป็น Bipartite Graph - หากทุกการระบายสีสำเร็จโดยไม่มีความขัดแย้ง แสดงว่าโครงสร้างกราฟในส่วนที่ DFS เดียวกันนั้นเป็น Bipartite ![Screenshot 2025-03-15 at 23.19.35](https://hackmd.io/_uploads/Hk2idXX3yx.png) **ตัวอย่างโปรแกรม** ```cpp= const int N = 1001; int color[N]; // เริ่มต้นทุกโหนดเป็น 0 (ยังไม่ได้ระบายสี) // สมมุติว่า G เป็นกราฟที่เก็บในรูปแบบของ adjacency list // ฟังก์ชัน DFS เพื่อทดลองระบายสีโหนด u ด้วยสี c // คืนค่า true ถ้าสามารถระบายสีได้โดยไม่มีความขัดแย้ง (ยังอาจเป็น bipartite graph) // คืนค่า false ถ้าพบความขัดแย้งในการระบายสี bool dfs(int u, int c) { if (color[u] != 0) { // ถ้าโหนด u เคยถูกระบายสีแล้ว // สีที่ระบายไว้ต้องตรงกับสีที่คาดหวัง หากไม่ตรงกัน แสดงว่ามีความขัดแย้ง return (color[u] == c); } // ระบายสีโหนด u ด้วยสี c color[u] = c; // เยี่ยมชมโหนดที่เชื่อมต่อกับ u และสลับสีให้กับโหนดลูก for (auto v : G[u]) { // หากการระบายสีสำหรับโหนด v ไม่สำเร็จ ให้ return false ทันที if (!dfs(v, (c == 1 ? 2 : 1))) return false; } return true; } int main() { // สมมุติว่า n คือจำนวนโหนดและ G เป็น adjacency list ของกราฟ int n; // ... (อ่านข้อมูลกราฟเข้ามาและกำหนดค่าใน G) // ตั้งค่าเริ่มต้นให้กับ color ทุกโหนดเป็น 0 (ยังไม่ได้ระบายสี) for (int i = 1; i <= n; i++) { color[i] = 0; } bool isBipartite = true; // เรียก DFS สำหรับทุกโหนดที่ยังไม่ได้ระบายสี for (int u = 1; u <= n; u++) { if (color[u] == 0) { // ยังไม่ได้ระบายสี หมายความว่าสำหรับ component นี้ยังไม่ถูกตรวจสอบ if (!dfs(u, 1)) { // เริ่มระบายสีด้วยสี 1 isBipartite = false; break; } } } if (isBipartite) cout << "กราฟเป็น Bipartite Graph" << "\n"; else cout << "กราฟไม่เป็น Bipartite Graph" << "\n"; return 0; } ``` > **หมายเหตุ:** > - เนื่องจากกราฟอาจแยกออกเป็นส่วน ๆ (disconnected components) จึงต้องเรียก DFS สำหรับทุกโหนดที่ยังไม่ได้ระบายสี เพื่อให้แน่ใจว่าทุกส่วนของกราฟได้รับการตรวจสอบ > - การตรวจสอบว่าโหนดในกราฟสามารถระบายสีด้วย k สีโดยที่โหนดที่เชื่อมต่อกันไม่มีสีเดียวกันนั้นเป็นเรื่องที่ซับซ้อนมาก แม้ในกรณีที่ k=3 ก็ยังไม่มีอัลกอริทึมที่มีประสิทธิภาพสำหรับแก้ปัญหานี้ เนื่องจากปัญหาดังกล่าวเป็น NP-hard. ## ตัวอย่างโจทย์ - https://programming.in.th/tasks/1031 - https://programming.in.th/tasks/1057 - https://programming.in.th/tasks/1061 - https://programming.in.th/tasks/1063 - https://programming.in.th/tasks/1085 - https://programming.in.th/tasks/1160 - https://programming.in.th/tasks/1161 # 3. Shortest Paths Algorithms การหาเส้นทางสั้นสุด (Shortest Path) ในกราฟเป็นปัญหาพื้นฐานที่พบได้ในงานด้านการวิเคราะห์และออกแบบเครือข่าย โดยมีวัตถุประสงค์เพื่อค้นหาเส้นทางที่ใช้ค่าใช้จ่ายหรือระยะทางน้อยที่สุดระหว่างโหนดต้นทางและโหนดปลายทาง โดยมีอัลกอริทึมหลายแบบที่สามารถแก้ปัญหานี้ได้ ซึ่งแต่ละแบบมีข้อดีข้อเสียแตกต่างกันไป **Dijkstra’s Algorithm:** ใช้สำหรับกราฟที่มี edge weight เป็นค่าบวกเท่านั้น โดยอัลกอริทึมจะทำงานโดยเริ่มจากโหนดต้นทางและค่อย ๆ อัปเดตระยะทางไปยังโหนดอื่น ๆ โดยใช้ priority queue เพื่อเลือกโหนดที่มีระยะทางน้อยที่สุดในแต่ละขั้นตอน มีความซับซ้อนในแง่ของเวลา $O((m + n) \log(n))$ **Bellman-Ford Algorithm:** ใช้สำหรับกราฟที่อาจมี edge ที่มี negative weight ได้ โดยอัลกอริทึมนี้จะทำการปรับค่าเส้นทางสั้นสุดโดยพิจารณา edge ทั้งหมดซ้ำ ๆ ไม่เกิน n−1 รอบ แต่มีความซับซ้อนในแง่ของเวลา $O(nm)$  **Floyd-Warshall Algorithm:** ใช้สำหรับคำนวณ All-Pair Shortest Path ได้อย่างง่ายดายเพียงไม่กี่บรรทัด แต่มีความซับซ้อนในแง่เวลาที่ $O(n^3)$ จึงเหมาะกับกราฟขนาดเล็กเท่านั้น ## 3.1 Dijkstra’s Algorithm **กระบวนการทำงาน** 1. การกำหนดค่าเริ่มต้น: กำหนดให้ระยะทาง (distance) จากโหนดเริ่มต้นไปยังทุกโหนดในกราฟเป็นค่าอนันต์ (infinity) ยกเว้นโหนดเริ่มต้นที่มีค่าเป็น 0 จากนั้นนำโหนดเริ่มต้นใส่ลงในคิว (priority queue) 2. การเลือกโหนด: ในแต่ละขั้นตอน นำโหนดที่มีค่า distance ต่ำที่สุดออกจากคิว (ซึ่งทำให้เราได้โหนดที่อยู่ใกล้โหนดเริ่มต้นที่สุดในขณะนั้น) 3. การปรับปรุงค่า: สำหรับโหนดที่เลือกออกมา ให้พิจารณาเพื่อนบ้านทั้งหมด (โดยดูจากข้อมูลใน Adjacency List) และปรับปรุงค่า distance ของเพื่อนบ้านเหล่านั้นโดยการบวกค่า edge weight เข้าไป ถ้าการปรับปรุงนี้ทำให้ค่า distance ของเพื่อนบ้านลดลง ให้ update ค่า distance และนำเพื่อนบ้านนั้นใส่ลงในคิว 4. การสิ้นสุดการทำงาน: กระบวนการดำเนินต่อไปจนกว่าคิวจะว่าง หรือจนกว่าจะพบโหนดเป้าหมาย **ข้อสังเกต** - อัลกอริทึมนี้มีประสิทธิภาพในการหาเส้นทางสั้นสุดในกราฟที่มี edge weight เป็นค่าบวก โดยมีความซับซ้อน $O((m+n)\log(n))$ - ควรระวังว่า Dijkstra’s Algorithm ไม่สามารถใช้งานกับกราฟที่มี edge ที่มี negative weight ได้ ![Screenshot 2025-03-15 at 23.57.25](https://hackmd.io/_uploads/rJlcWNQ31g.png) จากกราฟข้างต้นเส้นทางสั้นสุดจากโหนด 1 ไปยังโหนด 4 ที่แท้จริงคือ 1 → 3 → 4 โดยมีความยาวรวมเท่ากับ 1 อย่างไรก็ตาม Dijkstra’s algorithm พบเส้นทาง 1 → 2 → 4 โดยเลือก edge ที่มีน้ำหนักน้อยที่สุด โดยอัลกอริทึมนี้ไม่ได้พิจารณาว่าในเส้นทางอีกเส้นหนึ่ง น้ำหนัก −5 ชดเชยน้ำหนักสูง 6 ที่ผ่านมา ทำให้ไม่พบเส้นทางที่สั้นสุดตามที่ควรเป็นในกรณีที่มี edge มีค่า negative weight - กราฟถูกเก็บในรูปแบบ Adjacency List โดยใช้โครงสร้างข้อมูล `vector<pair<int, int>> G[N]` ซึ่งในแต่ละสมาชิกของ G[u] จะเป็นคู่ (v, w) โดยที่: - v คือหมายเลขของโหนดปลายทาง - w คือความยาว (น้ำหนัก) ของ edge จาก u ไป v - ใช้ Priority Queue (min-heap) ในการเลือกโหนดที่มี distance ต่ำที่สุด ซึ่งใน C++ สามารถใช้ `priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>` หรือจะกำหนดให้ค่า weight เป็นค่าลบเพื่อเปลี่ยนจาก max เป็น min priority queue ได้ - https://visualgo.net/en/sssp?slide=7 **ตัวอย่างโปรแกรม** ```cpp= #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int INF = 1e9; // กำหนดค่า infinity ที่เหมาะสม const int N = 1001; // สมมุติว่า N คือจำนวนสูงสุดของโหนด (ใช้ 1-based indexing) vector<pair<int, int>> G[N]; // โครงสร้างเก็บกราฟในรูปแบบ Adjacency List // ตัวอย่าง: ใน G[u], pair<int,int> เก็บ (v, w) คือโหนดปลายทางและน้ำหนักของ edge int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; // รับข้อมูลกราฟ for (int i = 0; i < m; i++){ int u, v, w; cin >> u >> v >> w; G[u].push_back({v, w}); // หากเป็นกราฟไม่มีทิศทาง ให้เพิ่มอีกด้าน: // G[v].push_back({u, w}); } int start, target; cin >> start >> target; // เตรียมอาร์เรย์เก็บระยะทางจากโหนด start vector<int> dist(n+1, INF); vector<bool> visited(n+1, false); // ใช้ priority_queue ในรูปแบบ min-heap typedef pair<int, int> pii; priority_queue<pii, vector<pii>, greater<pii>> Q; dist[start] = 0; Q.push({0, start}); while (!Q.empty()){ int u = Q.top().second; int d = Q.top().first; Q.pop(); // หากโหนด u ถูกเยี่ยมชมไปแล้ว ให้ข้ามไป if (visited[u]) continue; visited[u] = true; // หากเจอโหนดเป้าหมาย ให้หยุดและแสดงผล if (u == target) { cout << "ระยะทางจาก " << start << " ถึง " << target << " = " << dist[target] << "\n"; break; } // ปรับปรุงค่า distance ของเพื่อนบ้านที่เชื่อมต่อกับ u for (auto vw : G[u]){ int v = vw.first; int w = vw.second; if (!visited[v] && d + w < dist[v]){ dist[v] = d + w; Q.push({dist[v], v}); } } } // หากไม่เจอโหนดเป้าหมาย if (!visited[target]) cout << "ไม่พบเส้นทางจาก " << start << " ถึง " << target << "\n"; return 0; } ``` ## 3.2 Bellman-Ford Algorithm Bellman-Ford Algorithm มีไว้เพื่อหาเส้นทางสั้นสุดจากโหนดเริ่มต้นไปยังโหนดอื่น ๆ ในกราฟ โดยสามารถจัดการกับกราฟที่มี edge weight ที่เป็นค่าลบได้ **กระบวนการทำงาน** 1. กำหนดค่าเริ่มต้น: นิยามให้ `dist[v]` เป็นระยะทางสั้นสุดจากโหนดเริ่มต้นไปยังโหนด `v` โดยตั้งค่า `dist[v] = INF` สำหรับทุก `v` ยกเว้นโหนดเริ่มต้นที่กำหนดให้ `dist[start] = 0` 2. การปรับปรุงค่า: ทำการพิจารณา edge แต่ละ edge `(u, v, w)` ในกราฟ โดยเปรียบเทียบระยะทางที่ได้จากสองเส้นทางว่าเส้นทางใหม่ที่มาจากการเดินทางจาก `u` แล้วตามด้วย `edge (u, v)` ซึ่งมีค่า `dist[u] + w` ถ้า `dist[u] + w < dist[v]` ให้ปรับปรุงค่า `dist[v]` ด้วยค่าใหม่คือ `dist[u] + w` 3. ทำซ้ำ: ทำขั้นตอนที่ 2 ซ้ำกันทั้งหมดไม่เกิน $n-1$ รอบ (โดยที่ $n$ คือจำนวนโหนด) เนื่องจากเส้นทางสั้นสุดจากโหนดเริ่มต้นไปยังโหนดใด ๆ จะผ่าน edge ไม่เกิน $n-1$ เส้น หากหลังจากรอบที่ n-1 ยังพบการเปลี่ยนแปลงค่า dist[v] อยู่ แสดงว่ากราฟมี negative cycle (cycle ที่น้ำหนักรวมติดลบ) อยู่ **ข้อสังเกต** - อัลกอริทึมนี้จะต้องพิจารณา edge ซ้ำทั้งหมดไม่เกิน n-1 รอบ เพราะ path จาก node เริ่มต้นไปยัง node ใด ๆ ที่เป็นเส้นทางสั้นสุด ย่อมผ่านเส้นไม่เกิน n-1 เส้น ดังนั้นอัลกอริทึมนี้จะทำงานในเวลา $O(mn)$ - กราฟถูกเก็บในรูปแบบ Edge list โดยใช้โครงสร้างข้อมูล `vector<Edge> edges;` และ `struct Edge { int u, v, w; };` ซึ่งในแต่ละสมาชิกของ edge จะเป็นคู่ลำดับ (u, v, w) โดยที่: - u คือหมายเลขของโหนดต้นทาง - v คือหมายเลขของโหนดปลายทาง - w คือความยาว (น้ำหนัก) ของ edge จาก u ไป v - ในกรณีที่กราฟมี negative cycle (cycle ที่มี weight รวมติดลบ) algorithm อาจจะไม่จบการทำงาน ดังนั้นให้นับจำนวนรอบที่พิจารณา edge ด้วย หากทำงานรอบที่ `n-1` แล้วยังพบว่ามีการเปลี่ยนแปลงค่า `dist[v]` ก็สามารถสรุปได้ว่ากราฟมี negative cycle - https://visualgo.net/en/sssp?slide=4 **ตัวอย่างโปรแกรม** ```cpp= #include <iostream> #include <vector> #include <limits> using namespace std; const int INF = numeric_limits<int>::max(); const int N = 1001; // สมมุติว่าโหนดมีค่า 1-based index // โครงสร้างสำหรับเก็บ edge struct Edge { int u, v, w; }; int main(){ int n, m; cin >> n >> m; vector<Edge> edges; // รับข้อมูลกราฟในรูปแบบ edge list for (int i = 0; i < m; i++){ int u, v, w; cin >> u >> v >> w; edges.push_back({u, v, w}); } int start; cin >> start; // เตรียม vector สำหรับเก็บระยะทาง จากโหนด start ไปยังทุกโหนด vector<int> dist(n+1, INF); dist[start] = 0; int count = 0; bool found_changes = false; bool neg_cycle = false; // ทำการปรับปรุงค่า edge ไม่เกิน n-1 รอบ do { found_changes = false; for (auto edge : edges) { int u = edge.u, v = edge.v, w = edge.w; if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; found_changes = true; } } ++count; // ถ้าหลังจากรอบที่ n-1 ยังพบการเปลี่ยนแปลงค่า if (count > n - 1 && found_changes) { neg_cycle = true; break; } } while (found_changes); if (neg_cycle) cout << "กราฟมี negative cycle" << "\n"; else { // แสดงผลระยะทางสั้นสุดจากโหนด start ไปยังโหนดอื่น ๆ for (int v = 1; v <= n; v++){ cout << "dist[" << v << "] = "; if (dist[v] == INF) cout << "INF"; else cout << dist[v]; cout << "\n"; } } return 0; } ``` ## 3.4 Floyd-Warshall Algorithm นิยามให้ `dist[u][v]` เป็นระยะทางสั้นสุดที่ทราบ ณ ตอนนั้น จากโหนด u ไปยังโหนด v - เริ่มแรก เราไม่ทราบระยะทางที่แท้จริงของคู่โหนดต่าง ๆ ทั้งหมด จึงกำหนดให้ทุกตำแหน่งใน dist เป็น ∞ ยกเว้นตำแหน่งที่ u=v ให้กำหนดเป็น 0 เพราะระยะทางจากโหนดไปยังตัวเองเท่ากับ 0 - เมื่อรับข้อมูล edge ในกราฟ (edge มีรูปแบบ (u,v,w)) ให้เซต `dist[u][v] = w` เนื่องจากตอนนี้เราทราบระยะทางโดยตรงของ edge นั้นแล้ว **กระบวนการทำงาน** จากนั้นเราใช้การลูป 3 ชั้น โดยมีตัวแปร $k$ $i$ และ $j$ ดังนี้: 1. สำหรับทุกโหนด `k` (พิจารณาเป็นโหนดกลาง) 2. สำหรับทุกโหนด `i` (เป็นโหนดเริ่มต้น) 3. สำหรับทุกโหนด `j` (เป็นโหนดปลายทาง) - เปรียบเทียบเส้นทางที่มีอยู่เดิม `dist[i][j]` กับการเดินทางผ่านโหนด `k` โดยกำหนด `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])` **ข้อสังเกต** - อัลกอริทึมนี้จะต้องพิจารณาโหนดทั้งหมดสามรอบจึงทำงานในเวลา $O(n^3)$ ซึ่งเหมาะสำหรับกราฟที่มีขนาดไม่ใหญ่มาก - กราฟถูกเก็บในรูปแบบ Adjacency Matrix โดยใช้โครงสร้างข้อมูล `int dist[N_MAX][N_MAX];` - สามารถใช้งานกับกราฟที่มี edge weight เป็นค่าลบได้ - การตรวจสอบ negative cycle สามารถทำได้โดยดูค่า `dist[u][u]` สำหรับทุกโหนด `u` หากมีค่า `dist[u][u]<0` แสดงว่ามี negative cycle อยู่ในกราฟ **ตัวอย่างโปรแกรม** ```cpp= #include <cstdio> #include <algorithm> using namespace std; const int INF = 1e9; const int N_MAX = 1001; int dist[N_MAX][N_MAX]; int main(){ int n, m; scanf("%d%d", &n, &m); // เซตค่าเริ่มต้นให้กับ dist: // ถ้า i == j ให้เป็น 0, ไม่เช่นนั้นให้เป็น INF for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i == j) dist[i][j] = 0; else dist[i][j] = INF; } } // รับข้อมูลกราฟ (edge list) for (int i = 0; i < m; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dist[u][v] = w; // หากเป็นกราฟไม่มีทิศทาง ให้ใช้: // dist[v][u] = w; } // Floyd-Warshall Algorithm for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } // ตรวจสอบ negative cycle โดยดู dist[u][u] ของทุกโหนด bool negativeCycle = false; for (int u = 1; u <= n; ++u) { if (dist[u][u] < 0) { negativeCycle = true; break; } } if (negativeCycle) printf("กราฟมี negative cycle\n"); else { // แสดงผลระยะทางสั้นสุดสำหรับทุกคู่โหนด for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (dist[i][j] == INF) printf("INF "); else printf("%d ", dist[i][j]); } printf("\n"); } } return 0; } ``` ## สรุป | อัลกอริทึม | ประเภทกราฟที่ใช้ได้ | ความซับซ้อน (Time Complexity) | ข้อดี | ข้อเสีย | |-------------------------------|-------------------------------------------------|------------------------------------------|----------------------------------------------------------------------|----------------------------------------------------------------| | **Dijkstra’s Algorithm** | กราฟที่มี edge weight เป็นบวกเท่านั้น | O((V + E) log V) หรือ O(E log V) | มีประสิทธิภาพสูงสำหรับกราฟ sparse<br>ใช้งานง่ายและมี implementation ที่ชัดเจน | ไม่รองรับ edge ที่มี negative weight | | **Bellman-Ford Algorithm** | กราฟที่มี edge weight เป็นบวกและลบได้ | O(V × E) | รองรับ negative weight ได้<br>สามารถตรวจจับ negative cycle ได้ | ช้ากว่า Dijkstra ในกราฟที่ไม่มี negative edges | | **Floyd-Warshall Algorithm** | หาค่า All-Pairs Shortest Path ในกราฟขนาดเล็ก | O(V³) | โค้ดสั้นและง่ายต่อการเข้าใจ<br>หาเส้นทางสั้นสุดระหว่างทุกคู่ของโหนดได้ | ใช้เวลามากเมื่อจำนวนโหนดมีมาก<br>ไม่เหมาะกับกราฟที่มี V สูงมาก | ## ตัวอย่างโจทย์ - https://programming.in.th/tasks/1111 - https://programming.in.th/tasks/1133 - https://programming.in.th/tasks/codecube_051  # อ้างอิง - https://cses.fi/book/book.pdf - https://github.com/tchomphoochan/toi14-tutorial/tree/master - https://visualgo.net/en - https://programming.in.th/¬