C++ এ ফ্লো নেটওয়ার্কে ন্যূনতম s-t কাট খুঁজুন

ধরুন আমাদের নিম্নলিখিত ফ্লো নেটওয়ার্ক আছে। যেমনটি আমরা জানি একটি s-t কাট হল এমন একটি কাট যার জন্য সোর্স s নোড এবং একটি সিঙ্ক টি নোড বিভিন্ন উপসেটে থাকা প্রয়োজন এবং এতে উৎস সেট থেকে সিঙ্কের দিকে যাওয়া প্রান্তগুলি অন্তর্ভুক্ত রয়েছে। এখানে একটি s-t কাটের ক্ষমতা কাট-সেটের প্রতিটি প্রান্তের ক্ষমতার যোগফল দ্বারা উপস্থাপিত হয়। এখানে আমাদের প্রদত্ত নেটওয়ার্কের ন্যূনতম ক্ষমতা s-t কাট খুঁজে বের করতে হবে। এখানে প্রত্যাশিত আউটপুট হল ন্যূনতম কাটের সমস্ত প্রান্ত।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে [(1,3), (4,3), (4,5)]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• নোড =6

• একটি ফাংশন সংজ্ঞায়িত করুন bfs(), এটি গ্রাফ, src, সিঙ্ক, অ্যারে সমান,

• আকারের একটি বিন্যাস সংজ্ঞায়িত করুন - নোডস। এবং 0

  দিয়ে পূরণ করুন

• এক সারি কিউ সংজ্ঞায়িত করুন

• que এ src ঢোকান

• vis[src] :=true এবং par[src] :=-1

• যখন (que খালি নয়), −

  করুন

  • u1 :=que এর প্রথম উপাদান

  • que

    থেকে উপাদান মুছুন

  • শুরু করার জন্য v1 :=0, যখন v1

    • যদি vis[v1] মিথ্যা হয় এবং গ্রাফ[u1, v1]> 0 হয়, তাহলে −

      • que এ v1 ঢোকান

      • par[v1] :=u1

      • vis[v1] :=সত্য

• প্রত্যাবর্তন সত্য যখন ভিস [সিঙ্ক] সত্য হয়

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি গ্রাফ, src, অ্যারে ভিস,

• vis[src] :=সত্য

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি গ্রাফ[src, i] অ-শূন্য হয় এবং vis[i] মিথ্যা হয়, তাহলে −

    • dfs(গ্রাফ, i, vis)

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• একটি অ্যারে temp_graph সংজ্ঞায়িত করুন এবং এতে গ্রাফ অনুলিপি করুন

• আকারের একটি অ্যারের সমতুল্য সংজ্ঞায়িত করুন:নোডস৷

  ৷

• যখন bfs(temp_graph, src, sink, par) সত্য, do −

  • path_flow :=inf

  • ইনিশিয়ালাইজ করার জন্য v :=সিঙ্ক, যখন v src-এর সমান নয়, আপডেট করুন v:=par[v], do −

    • u :=par[v]

    • পথ_প্রবাহ :=সর্বনিম্ন পথ_প্রবাহ এবং টেম্প_গ্রাফ[u, v]

  • ইনিশিয়ালাইজ করার জন্য v :=সিঙ্ক, যখন v src-এর সমান নয়, আপডেট করুন v:=par[v], do −

    • u :=par[v]

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

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

• আকারের একটি বিন্যাস সংজ্ঞায়িত করুন - নোডস। এবং মিথ্যা দিয়ে পূরণ করুন

• dfs(temp_graph, src, vis)

• আরম্ভ করার জন্য i :=0, যখন i − NODES, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

• j শুরু করার জন্য :=0, যখন j − NODES, আপডেট করুন (j 1 দ্বারা বাড়ান), করবেন −

  • যদি vis[i] অ-শূন্য হয় এবং vis[j] মিথ্যা হয় এবং গ্রাফ[i, j] অ-শূন্য হয়, তাহলে −

    • প্রদর্শন (i, j) প্রান্ত হিসাবে

  • ফেরত

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include নেমস্পেস std ব্যবহার করে;#NODES 6int bfs(int গ্রাফ[NODES][NODES], int src, int sink, int par[]) { bool vis[NODES]; memset(vis, 0, sizeof(vis)); সারি  que; que.push(src); vis[src] =সত্য; par[src] =-1; যখন (!que.empty()) { int u1 =que.front(); que.pop(); জন্য (int v1=0; v1 0) { que.push(v1); par[v1] =u1; vis[v1] =সত্য; } } } রিটার্ন (ভিস[সিঙ্ক] ==সত্য);}অকার্যকর dfs(int গ্রাফ[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)