গ্রাফ ট্র্যাভারসিং ( ডি এফ এস অ্যালগরিদম )

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

1. ডাইরেক্টেড গ্রাফ 
2. অ্যাডজাসেনসি লিস্ট

আগেরবার আমরা দেখেছি যে ২টা জেলা এর মধ্যে যদি ১টা রাস্তা থাকে, তবে আপনি ১ম জেলা থেকে ২য় জেলায় যেতে যেমন পারবেন, তেমনি ২য় জেলা থেকে প্রথম জেলায় আসতেও পারবেন। আজকের কন্সেপ্ট টা নতুন, তা হল এমন ঘটনাও ঘটতে পারে যে সেটা ওয়ান ওয়ে রোড। কাজেই যাওয়ার ১টা ডিরেকশন থাকবে। ব্যাপারটাকে সহজভাবে বুঝতে মনে করুন রাস্তায় কাজ চলছে, তো টু ওয়ে রাস্তার ১দিক বন্ধ করে দিয়া হয়েছে, আরেকদিক খোলা আছে। কাজেই আপনি প্রথম জেলা থেকে ২য় জেলায় যেতে পারবেন, কিন্তু অই রাস্তা ধরে ২য় জেলা থেকে প্রথম জেলায় আসতে পারবেন না, আপনাকে বিকল্প রাস্তা দেখতে হবে। এই ঘটনাকেই বলবো ডাইরেক্টেড গ্রাফ, ঠিক আগের ঘটনা, শুধু নতুন করে আপনাকে ওয়ান ওয়ে রাস্তার কথা চিন্তা করতে হবে।

ডাইরেক্টেড গ্রাফ

উপরের গ্রাফটিকে লক্ষ্য করুন, আপনি A থেকে B তে যেতে পারবেন, কিন্তু B থেকে A তে আসতে পারবেন না, একই ভাবে B থেকে C, D তে যেতে পারবেন, কিন্তু তা থেকে B তে ফেরত আসতে পারবেন না। এটাই ডাইরেক্টেড গ্রাফ।

এবার লক্ষ্য করি অ্যাডজাসেন্সি লিস্ট এর দিকে !  এতা দেখোবে ১টা নোড থেকে কোথায় কোথায় যাওয়া যায় !
A থেকে যাওয়া যায় শুধু  B তে
B থেকে যাওয়া যায় C ,D তে
C থেকে কোথাও যাওয়া যায় না
D থেকে যাওয়া যায়  A , C তে!!!
এই গ্রাফটির জন্য এখন অ্যাডজাসেন্সি লিস্ট দেখব

A --- B

B ---C , D
C --
D --- A , C

এবার ধারণা দিবো স্ট্যাক এর উপর, পরে স্ট্যাক আর কিউ এর উপর বিষদ আলোচনা করবো । স্ট্যাক হল কতগুলো উপাদান বা ডাটা এর ১টি লিস্ট, যেখানে যে সবার শেষে প্রবেশ করে, সে সবার আগে বের হয়ে যায় !!!!!!!!!!!!!!
মাথার উপর দিয়ে গেলো?? খুব সহজ ১টা উদাহরন দেই,  লোকাল বাসে  চরেছেন? বাসে হেল্পার যাত্রি তোলে। যে আগে বাসে ওঠে, তাকে একদম পিছনে পাঠিয়ে দেয়া হয়, আর যে পরে ওঠে সে গেইট এর পাশেই থাকে।
ফলে যে পরে ওঠে সে আগে  নামার সুযোগ পায় ! স্ট্যাক ও ঠিক তাই, যে পরে লিস্ট এ প্রবেশ করবে সে আগে বের হয়ে যাবে, আর যে আগে প্রবেশ করবে, সে সবার শেষে বের হবে। একে বলা হয় LIFO (Last In First Out ) !
বিস্তারিত জানতে এই পেজটি দেখতে পারেন। স্ট্যাক

এতক্ষণ আমরা যা দেখলাম তার সবকিছু শিখার উদ্দেশ্য ছিল ডি এফ এস বুঝা । এবার দেখা যাক কিভাবে ডি এফ এস কাজ করে এবং তা দিয়ে কি করে গ্রাফ ট্র্যাভারস করা যায় ।

উপরের ছবিতে যে ডাইরেক্টেড গ্রাফ দেখেছি তা পরিভ্রমন করা শুরু করলাম A থেকে !
যাকে পরিভ্রমন করবো তাকে স্ট্যাক এ রাখব।

স্ট্যাক  ঃ  A

যেহেতু A একাই স্ট্যাক এ আছে, কাজেই তাকে প্রিন্ট করে দেয়া হবে, তারপর A কে স্ট্যাক থেকে বের করে দেয়া হবে এবং অ্যাডজাসেন্সি লিস্ট থেকে A থেকে যে সব নোড এ যাওয়া যায়, অর্থাৎ যারা A এর অ্যাডজাসেন্ট, তাদেরকে স্ট্যাক এ পুস করবো, অর্থাৎ প্রবেশ করাবো !
অ্যাডজাসেন্সি লিস্ট এ দেখতে পাচ্ছি A এর অ্যাডজাসেন্ট হল শুধু B

প্রিন্ট  ঃ A
স্ট্যাক  ঃ B

এবার ও যেহেতু B একাই স্ট্যাক এ আছে, তাই B কে প্রিন্ট করে দেয়া হবে এবং B এর অ্যাডাজাসেন্ট C, D কে স্ট্যাক এ প্রবেশ করানো হবে।
প্রিন্ট  ঃ B
স্ট্যাক  ঃ C, D
স্ট্যাক এ এখন ২টি ডাটা রয়েছে। যেহেতু D পরে প্রবেশ করেছে, তাই D আগে বের হবে। এখন D এর  অ্যাডজাসেন্ট A এবং C যা ইতিমধ্যে স্ট্যাক এ প্রবেশ করেছে, তাই এগুলো আর স্ট্যাক এ নেয়া যাবে না।

প্রিন্ট  ঃ D
স্ট্যাক  ঃ C

এখন C এর ও কোন অ্যাডজাসেন্ট নেই, কাজেই C কে স্ট্যাক থেকে বের করে প্রিন্ট করে দিতে হবে এবং স্ট্যাকটি খালি হয়ে যাবে।
আর স্ট্যাক টি খালি হলেই বুঝতে হবে গ্রাফটি ট্র্যাভারসিং শেষ হয়েছে :)

প্রিন্ট  ঃ C
স্ট্যাক  ঃ

এবার লক্ষ্য করি কী কী প্রিন্ট করা হয়েছে !
A  B  D  C
আমাদের গ্রাফ এ এই কয়টি নোড ই ছিলো , এভাবেই ডি এফ এস অ্যালগরিদম এর মধ্যমে সবগুলো নোড এ পরিভ্রমণ করা সম্ভব ।

 এবার দেখি আমাদের উপরের চিত্রের গ্রাফ এর জন্য অ্যা ডজাসেন্সি ম্যাট্রিক্স কেমন হবে !


       A       B       C       D

A     0        1        0        0

B     0        0        1         1

C     0        0        0         0

D      1       0        1         0