ค้นหา st cut ขั้นต่ำในเครือข่ายโฟลว์ใน C++

สมมติว่าเรามีเครือข่ายโฟลว์ต่อไปนี้ ดังที่เราทราบ st cut เป็นการตัดที่ต้องใช้โหนดต้นทางและโหนด sink t ในชุดย่อยที่แตกต่างกัน และรวมถึงขอบที่ไปจากชุดต้นทางไปยังฝั่งซิงก์ ในที่นี้ ความจุของการตัดแบบ s-t จะแสดงด้วยผลรวมของความจุขอบแต่ละอันในชุดตัด ที่นี่เราต้องค้นหาความจุขั้นต่ำของเครือข่ายที่กำหนด ผลลัพธ์ที่คาดหวังคือขอบของการตัดขั้นต่ำทั้งหมด

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น [(1,3), (4,3), (4,5)]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• โหนด =6

• กำหนดฟังก์ชัน bfs() ซึ่งจะใช้ graph, src, sink, array par

• กำหนดขนาดของอาร์เรย์ vis - NODES และเติม 0

• กำหนดหนึ่งคิว que

• แทรก src ลงใน que

• vis[src] :=true และ par[src] :=-1

• ในขณะที่ (que ไม่ว่างเปล่า) ทำ -

  • u1 :=องค์ประกอบแรกของ que

  • ลบองค์ประกอบออกจาก que

  • สำหรับการเริ่มต้น v1 :=0 เมื่อ v1

    • ถ้า vis[v1] เป็นเท็จ และ graph[u1, v1]> 0 แล้ว −

      • แทรก v1 ลงใน que

      • พาร์[v1] :=u1

      • vis[v1] :=true

• คืนค่า true เมื่อ vis[sink] เป็นจริง

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ graph, src, array vis,

• vis[src] :=จริง

• สำหรับการเริ่มต้น i :=0, เมื่อ i

  • ถ้ากราฟ[src, i] ไม่ใช่ศูนย์และ vis[i] เป็นเท็จ ดังนั้น −

    • dfs(กราฟ, i, vis)

• จากวิธีหลัก ให้ทำดังนี้ −

• กำหนดอาร์เรย์ temp_graph และคัดลอกกราฟลงไป

• กำหนดขนาดพาร์ของอาร์เรย์:NODES

• ในขณะที่ bfs(temp_graph, src, sink, par) เป็นจริง ให้ทำ -

  • path_flow :=inf

  • สำหรับการเริ่มต้น v :=sink เมื่อ v ไม่เท่ากับ src ให้อัปเดต v:=par[v] ทำ -

    • คุณ :=พาร์[v]

    • path_flow :=ขั้นต่ำของ path_flow และ temp_graph[u, v]

  • สำหรับการเริ่มต้น v :=sink เมื่อ v ไม่เท่ากับ src ให้อัปเดต v:=par[v] ทำ -

    • คุณ :=พาร์[v]

    • temp_graph[u, v] :=temp_graph[u, v] - path_flow

    • temp_graph[v, u] :=temp_graph[v, u] + path_flow

• กำหนดขนาดของอาร์เรย์ vis - NODES และเติมเท็จ

• dfs(temp_graph, src, vis)

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน − NODES ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

• สำหรับการเริ่มต้น j :=0 เมื่อ j − NODES ให้อัปเดต (เพิ่ม j ขึ้น 1) ทำ −

  • ถ้า vis[i] ไม่ใช่ศูนย์ และ vis[j] เป็นเท็จ และ graph[i j] ไม่ใช่ศูนย์ ดังนั้น −

    • แสดง (i, j) เป็นขอบ

  • กลับ

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;#define NODES 6int bfs (กราฟ int [NODES][NODES], int src, int sink, int par []) { bool vis [NODES]; memset(vis, 0, sizeof(vis)); คิว  คิว; que.push(src); vis[src] =จริง; พาร์[src] =-1; ในขณะที่ (!que.empty()) { int u1 =que.front(); que.pop(); สำหรับ (int v1=0; v1 0) { que.push(v1); พาร์[v1] =u1; vis[v1] =จริง; } } } return (vis[sink] ==true);} void dfs(int graph[NODES][NODES], int src, bool vis[]) { vis[src] =true; สำหรับ (int i =0; i  
อินพุต
 <ก่อน>{{0, 17, 14, 0, 0, 0},{0, 0, 11, 13, 0, 0},{0, 5, 0, 0, 15, 0},{0, 0 , 9, 0, 0, 21{0, 0, 0, 8, 0, 5},{0, 0, 0, 0, 0, 0}};

ผลลัพธ์

(1, 3)(4, 3)(4, 5)