ফোর্ড ফুলকারসন অ্যালগরিদম

ফোর্ড-ফুলকারসন অ্যালগরিদমটি একটি প্রদত্ত গ্রাফে শুরুর শীর্ষ থেকে সিঙ্ক শীর্ষে সর্বাধিক প্রবাহ সনাক্ত করতে ব্যবহৃত হয়৷ এই গ্রাফে, প্রতিটি প্রান্তের ক্ষমতা আছে। উৎস এবং সিঙ্ক নামে দুটি শীর্ষবিন্দু প্রদান করা হয়েছে। উৎস শিরোনামের সমস্ত বহির্মুখী প্রান্ত আছে, কোন অভ্যন্তরীণ প্রান্ত নেই, এবং সিঙ্কের সমস্ত অভ্যন্তরীণ প্রান্ত থাকবে কোন বহির্মুখী প্রান্ত।

কিছু সীমাবদ্ধতা আছে:

• একটি প্রান্তে প্রবাহ সেই গ্রাফের প্রদত্ত ক্ষমতা অতিক্রম করে না।
• আগত প্রবাহ এবং বহির্গামী প্রবাহ প্রতিটি প্রান্তের জন্য সমান হবে, উৎস এবং সিঙ্ক ছাড়া।

ইনপুট এবং আউটপুট

ইনপুট:সংলগ্ন ম্যাট্রিক্স:0 10 0 10 0 00 0 4 2 8 00 0 0 0 0 100 0 0 0 9 00 0 0 6 0 0 0 100 0 0 0 0 0 আউটপুট:সর্বাধিক প্রবাহ হল  
অ্যালগরিদম
 

 bfs (ভার্ট, স্টার্ট, সিঙ্ক) 
 

 ইনপুট: শীর্ষবিন্দু তালিকা, স্টার্ট নোড এবং সিঙ্ক নোড।
 

 আউটপুট -  যখন সিঙ্ক পরিদর্শন করা হয় তখন সত্য৷
৷ 
প্রাথমিকভাবে সমস্ত নোডকে দেখা না যাওয়া অবস্থায় সূচনা হিসাবে চিহ্নিত করুন সূচনা নোডের পূর্বসূরি হিসাবে φ কিউতে সূচনা সন্নিবেশ করান যখন qu খালি না থাকে, সারি থেকে উপাদান মুছে ফেলুন এবং সকল শীর্ষবিন্দুর জন্য u শীর্ষবিন্দুতে সেট করুন i, অবশিষ্ট গ্রাফ, করুন যদি u এবং i সংযুক্ত থাকে, এবং i unvisited হয়, তারপর সারিতে i যোগ করুন i is u মার্ক i যেমন পরিদর্শন করা হয়েছে সম্পন্ন হয়েছে সত্য রিটার্ন করুন যদি সিঙ্কের শীর্ষস্থান পরিদর্শন করা হয় শেষ
 

 ফোর্ডফুলকারসন (ভার্ট, সোর্স, সিঙ্ক) 
 

 ইনপুট: শীর্ষবিন্দু তালিকা, উৎস শীর্ষবিন্দু, এবং সিঙ্ক শীর্ষবিন্দু।
 

 আউটপুট -  শুরু থেকে ডুবে যাওয়া পর্যন্ত সর্বাধিক প্রবাহ।
 
একটি অবশিষ্ট গ্রাফ তৈরি করা শুরু করুন এবং bfs(vert, source, sink) সত্য হলে প্রদত্ত গ্রাফটি কপি করুন, pathFlow করুন :=∞ v :=sink vertex যখন v ≠ start vertex, do u :=v pathFlow এর পূর্বসূরী :=ন্যূনতম পাথফ্লো এবং রেসিডুয়ালগ্রাফ[u, v] v :=v এর পূর্বসূরী v সম্পন্ন v :=সিঙ্ক vertex যখন v ≠ স্টার্ট vertex, do u :=v residualGraph[u,v] এর পূর্বসূরী :=অবশিষ্ট গ্রাফ[u,v ] – pathFlow residualGraph[v,u] :=residualGraph[v,u] – pathFlow v :=v সম্পন্ন maFlow এর পূর্বসূরী :=maxFlow + pathFlow সম্পন্ন হয়েছে রিটার্ন maxFlowEnd
 
উদাহরণ
 
#include#include#define NODE 6 ব্যবহার করে namespace std;typedef struct node { int val; int state; // অবস্থা int pred; //পূর্ববর্তী}নোড;int ন্যূনতম(int a, int b) { রিটার্ন (a que; for(i =0; i 0 &&vert[i].state ==0) { que.push(vert[i]); vert[i].pred =u.val; vert[i].state =1; } } } রিটার্ন (vert[sink.val].state ==1);}int fordFulkerson(নোড *ভার্ট, নোড সোর্স, নোড সিঙ্ক) { int maxFlow =0; int u, v; for(int i =0; i 
আউটপুট
 
সর্বোচ্চ প্রবাহ হল:19