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

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

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

গ্রাফ থিওরি নিয়ে কিছু আষাঢ়ে গল্প !

গ্রাফ থিওরি !

স্কুল কলেগজে আমার দেখা সবচেয়ে বিরক্তিকর জিনিস হইলো গ্রাফ :P 

না, এই গ্রাফ ঠিক সেই গ্রাফ না ! তআহলে এটা কি? কেন দরকার? 

আচ্ছা ধরুন আপনি প্রথম রাস্তায় বাস ছেড়েছেন, ধরুন আপনি ময়মনসিংহ থেকে বাগেরহাট এ বাসটি চালাবেন,

এর মাঝে প্রায় ২০-৩০ টি জেলা আছে, আমরা ধরে নিলাম এর মাঝে ২০টি জেলা আছে, এখন সব জেলা থেকে সব জেলার রাস্তা ও নেই। এখন আপনি চাইবেন যে সব জেলায় যাওয়া যাবে তার মধ্যে যেখানে যাত্রী বেশি পাওয়া যাবে সেই জেলাগুলোতে যাবেন, পাশাপাশি এটাও মাথায় রাখবেন যেন বেশি ঘুরে না যেতে হয় ।

এখন আপনি এই ২০টি জেলার সবগুলো দিয়ে  কি করে যাওয়া যায় তা চেক করে দেখবেন, এদের মধ্যে আবে খেয়াল রাখবেন কোথায় কোথায় যাওয়ার রাস্তা নেই , এবং  যাত্রী কোথায় বেশি পাওয়া যাবে, এবং সব শেষে অবশ্যই  যেন যতটা সম্ভব কম ঘুরে যেন যেতে হয়, যাতে আপনার তেল খরচ বেশি না হয় ! 

চিন্তায় পরে গেলেন? 

আচ্ছা, আপনাকে সাহায্য করতে আছে অসাধারণ ১টি অ্যালগরিদম ! আপনি শুধু গ্রাফ থিওরি ভালভাবে জানবেন, এর পর শুধু ১টা কোড  করতে হবে, ব্যাস ! 

আজ আমরা কথা বলবো সেই গ্রাফ থিওরি নিয়ে ।

ছোট বেলায় অনেকেই আলিফ লায়লা দেখেছেন, ধরূন গুপ্তধন লুকিয়ে আছে কোন গোলক ধাঁধার মাঝে, আপনি আর জলদস্যু তার পিছনে চলেছেন, কে আগে পৌঁছাবে? অবশ্যই আপনি, কারণ আপনি জানেন গ্রাফ থিওরি ! 

আসুন দেখি উপরের ২টি সমস্যা কি করে গ্রাফ থিওরি দিয়ে সমাধান করা যায় ! 

প্রথমেই লক্ষ্য করি গ্রাফ কি ? কি কি দিয়ে ১টি গ্রাফ গঠিত হয় ?

বাসের রুট দিয়েই ব্যাখ্যা করি, এখন ১টি গ্রাফে থাকে কিছু নোড, আর বিভিন্ন নোড এর মধ্যে কিছু পথ ! 

আমাদের প্রথম সমস্যায় যে ২০টি জেলা আছে তা হল নোড, আর রাস্তাগুলো হলো সেই পথ !

দেখানোর সুবিধার জন্য ৪টি জেলা দিয়ে দেখাচ্ছি । আপনি ময়মনসিংহ থেকে ঢাকা আসতে চান, তো দেখতেই পাচ্ছেন সরাসরি কোন রাস্তা নেই, কাজেই আপনাকে হয় টাঙ্গাইল নতুবা গাজীপুর ঘুরে আসতে হবে । 

এখন আপনি কি করবেন  ধরুন আপনাকে শুধু দূরত্বের ব্যাপারটা মাথায় রাখতে হবে, মানে সবচেয়ে কম দূরত্ব অতিক্রম করে কি করে ঢাকা আসা যাবে, এর জন্য আমরা কিছু দূরত্ব ধরে নিতে পারি ! 

ছবিতে আমরা কিছু দূরত্ব ধরে নিয়েছি ! 

ময়মনসিংহ থেকে যাত্রা শুরু ! 

এডিট ভালো করতে পারি নি বলে দুঃখিত । যাই হোক , এখন আমরা এখান থেকে টাঙ্গাইল ও গাজিপুর যেতে পারি। 

টাঙ্গাইল যেতে ৫০ কি মি, আর গাজীপুর যেতে ৩০ কি মি, তাই আপাতত গাজীপুর যাওয়াই ভালো ! 

এখন গাজীপুর থেকে ঢাকা যাওয়ার সরাসরি পথ আছে, একই ভাবে টাঙ্গাইল থেকেও আছে। 

1. ময়মনসিংহ - গাজীপুর - ঢাকা = (৩০ + ২৭ ) = ৫৭ কি মি। 
2. ময়মনসিংহ - টাঙ্গাইল - ঢাকা = (৫০ + ১৫) = ৬৫ কি মি

তো আপাতত দেখতেই পাচ্ছি ২য় মাধ্যমেই যাওয়া ভালো ! কিন্তু আমার হাতে আরো কিছু পথ আছে যেগুলো আমরা দেখি নি ! সেটি হল টাঙ্গাইল ও গাজীপুরের মাঝে ১০ কি মি ১টি পথ আছে, 

  3.  ময়মনসিংহ - গাজীপুর-টাঙ্গাইল - ঢাকা = (৩০ + ১০ + ১৫ ) = ৫৫ কি মি ।
  4.  ময়মনসিংহ -- টাঙ্গাইল -গাজীপুর-- ঢাকা = (৫০ + ১০ + ২৭) = ৮৭ কি মি ।

এখন আমরা সবগুলো সম্ভাব্য পথ দেখে ফেলেছি ! এদের মধ্যে এখন খুব সহজেই আমরা সবচেয়ে কম দূরত্বের পথ বের করতে পারি । উপরে দেখতেই পাচ্ছি ৩য় উপায়ে অর্থাৎ ময়মনসিংহ - গাজীপুর- টাঙ্গাইল - ঢাকা  এই পথে গেলে আমরা সবচেয়ে সহজে এবং কম দূরত্ব অতিক্রম করে ঢাকা যেতে পারব ।

এই পথ বের করতে আমাকে সবগুলো জেলা এবং সবগুলো পথ ঘুরে দেখতে হয়েছে, ৪টি জেলা বলে আমাদের কাছে অনেক সহজ মনে হয়েছে, কিন্তু যদি শহর ৪০ টি হত, বা ৪০০ টি হত, অথবা ৪০০০টি হত, তখন? তখন এই কাজটি ই করে দিবে গ্রাফ  এর কিছু অ্যালগরিদম, গ্রাফ পরিভ্রমন করতে সবচেয়ে জনপ্রিয় ও ব্যবহৃত এলগরিদম হল ডি এফ এস (ডেপ্ত ফার্স্ট সার্চ) ও বি এফ এস ( ব্রেডথ ফার্স্ট সার্চ ) । 
আর এদের মাঝে সরটেস্ট পথ বের করতে আছে অয়ারসাল ও ডায়াস্ট্রা অ্যালগরিদম ! 

এগুলো নিয়ে পরে আলোচনা করবো। প্রথমে দেখব কি করে এই গ্রাফকে কম্পিউটার মেমরীতে ইনপুট দেয়া যায়  ! 

এর জন্য সবচেয়ে সহজ পদ্ধতি হল অ্যাডজাসেন্সি ম্যাট্রিক্স ! 

                        ময়মনসিংহ    টাঙ্গাইল       গাজীপুর      ঢাকা

ময়মনসিংহ          ০                 ১                  ১               ০

টাঙ্গাইল               ১                 ০                  ১               ১             

গাজীপুর              ১                  ১                 ০                ১

ঢাকা                   ০                  ১                  ১               ০

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

এবার দেখব অয়েটেড ম্যাট্রিক্স, যাতে পথ থাকলে পথের দূরত্ব সহ দেখাবে !! 

                        ময়মনসিংহ    টাঙ্গাইল       গাজীপুর      ঢাকা

ময়মনসিংহ          ০                 ৫০                ৩০            ০
টাঙ্গাইল              ৫০                 ০                ১০             ১৫             
গাজীপুর             ৩০               ১০                 ০              ২৭
ঢাকা                   ০                 ১৫               ২৭               ০

আজ এ পর্যন্তই থাক, এর পরে আমরা দেখব কি করে গ্রাফ ট্র্যাভারস করা যায় ! খুব চমৎকার ২টি অ্যালগরিদম এর সাথে পরিচিত হব । ডি এফ এস (ডেপ্ত ফার্স্ট সার্চ) ও বি এফ এস ( ব্রেডথ ফার্স্ট সার্চ ) । 
সবার জন্য শুভকামনা ।

পরবর্তী পোস্ট 

সব টপিক এর উপর কিছু গুরুত্বপূর্ণ এলগরিদম !

Mathematics:

1. Prime finding(sieve)
2. Prime factorization
3. GCD, LCM
4. Factorial
5. Fibonacci
6. Counting, Permutation, combination
7. Exponentiation
8. Modular Arithmetic
9. Euclid, Extended euclid

Data Structure:

1. Stack
2. Queue
3. Priority Queue
4. Linked list
5. Heap
6. Hash table
7. Disjoint Set, Union Find
8. Binary Search Tree
9. Trie, Suffix Array
10. Segmented Tree,Range minimum Query
11. Binary Indexed Tree(BIT)
12. Heavy light Decomposition

Sorting:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Quick Sort
5. Merge Sort
6. Counting Sort
7. Radix Sort
8. Bucket Sort
9. Heap Sort
10. Searching:
11. Linear Search
12. Binary Search
13. Ternary Search
14. Map, HashMap

Dynamic Programming

1. Rod Cutting
2. Maximum Sum (1D, 2D)
3. Coin Change
4. Longest Common Subsequence
5. Longest Increasing subsequence, Longest Decreasing Subsequence
6. Matrix Chain multiplication
7. Edit Distance
8. Knapsack problem, 0-1 Knapsack
9. Bitmask DP
10. Traveling Salesman problem

Greedy Algorithm:

1. Activity selection/Task scheduling problem
2. Huffman coding

Graph Theory:

1. Graph Representation(matrix, list/vector)
2. Breadth First Search(BFS)
3. Depth First Search(DFS)
4. Topological Sort
5. Strongly Connected Component(SCC)
6. Minimum Spanning Tree(kruskal, prim)
7. All pair's shortest path(Floyd Warshall)
8. Djkastra algorithm
9. Bellman Ford Algorithm
10. Directed Acyclic Graph
11. Bipartite Matching
12. Max-Flow, Min-cost max-flow
13. Cayley's Theorem
14. Articulation Point, Bridge
15. Euler tour/path
16. Hamiltonian Cycle
17. Stable Marriage problem
18. Chinese Postman problem
19. Number Theory:
20. Josephus Problem
21. Farey Sequence
22. Euler's phi
23. Catalan numbers
24. Burnside's lemma/circular permutation
25. Modular inverse
26. Probability
27. Chinese Remainder Theorem
28. Gaussian Elmination method
29. Dilworth's Theorem
30. Matrix Exponentiation
31. Determinant of a matrix
32. RSA public key crypto System
33. Computational Geometry:
34. Pick's Theorem
35. Convex hull
36. Line Intersection
37. Point in a polygon
38. Area of a polygon
39. Line Sweeping
40. Polygon intersection
41. Closest Pair

Game Theory:

1. Take Away game
2. Nim
3. Sprague-grundy Number

String

1. Naive String matching 
2. Rabin karp Algo
3. Finite Automata
4. Knuth-Marris-Pratt Algo
5. Manacher's Algo
6. Aho korasick's Algo
7. Boyer-Moore algo

Others:

Recursion

C++ Standard Template Library(STL)
Backtracking
Hungarian Algorithm

আউলা পোস্ট

কি করব ঠিক জানি না,

আদৌ কিছু করবো কিনা তাও বলতে পারছি না। 

প্রোগ্রামিং নিয়ে কিছু লিখবো ভেবে খুললাম ,

মনে যখন যা আসবে, লিখবো। 

যা ভালো লাগবে লিখবো। 

নিজের জন্য শুভকামনা :)