নির্দেশিত গ্রাফে কনেক্টিভিটি

একটি গ্রাফের কনেক্টিভিটি চেক করতে, আমরা যেকোনো ট্রাভার্সাল অ্যালগরিদম ব্যবহার করে সব নোড ট্রাভার্স করার চেষ্টা করব। ট্রাভার্সাল শেষে, যদি কোনো নোড থাকে যা ভিজিটেড নয়, তবে গ্রাফটি কানেক্টেড নয়।

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

এই কেসে, ট্রাভার্সাল অ্যালগরিদম হলো রিকার্শিভ DFS ট্রাভার্সাল।

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

ইনপুট: একটি গ্রাফের এডজেসেন্সি ম্যাট্রিক্স 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 আউটপুট: The Graph is connected.

অ্যালগরিদম

traverse(u, visited)

ইনপুট: স্টার্ট নোড u এবং ভিজিটেড নোড যেটি মার্ক করে কোন নোড ভিজিটেড।

আউটপুট - সব কানেক্টেড ভার্টেক্স ট্রাভার্স করা।

শুরু
  u কে ভিজিটেড হিসেবে মার্ক করুন
  গ্রাফের সব ভার্টেক্স v, যদি u-এর সাথে আডজাসেন্ট থাকে, করুন
    যদি v ভিজিটেড না হয়, তবে
      traverse(v, visited)
    শেষ
শেষ

isConnected(graph)

ইনপুট: গ্রাফ।

আউটপুট: True যদি গ্রাফ কানেক্টেড হয়।

শুরু
  visited অ্যারে ডিফাইন করুন
  গ্রাফের সব ভার্টেক্স u-এর জন্য করুন
    সব নোড আনভিজিটেড করুন
    traverse(u, visited)
    যদি কোনো আনভিজিটেড নোড বাকি থাকে, তবে
      return false
  শেষ
  return true
শেষ

উদাহরণ

#include<iostream> #define NODE 5 using namespace std; int graph[NODE][NODE] = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0} }; void traverse(int u, bool visited[]) { visited[u] = true; //v কে ভিজিটেড মার্ক করুন for(int v = 0; v
আউটপুট
The Graph is connected.