ডেটা স্ট্রাকচারের একটি ডিগ্রাফে গভীরতা-প্রথম অনুসন্ধান

গ্রাফের জন্য গভীরতার প্রথম অনুসন্ধান একই রকম৷ কিন্তু ডিগ্রাফ বা নির্দেশিত গ্রাফের জন্য, আমরা কয়েক ধরনের প্রান্ত খুঁজে পেতে পারি। ডিএফএস অ্যালগরিদম একটি গাছ গঠন করে যার নাম ডিএফএস ট্রি। −

• ট্রি এজ (T) - যে প্রান্তগুলি DFS গাছে উপস্থিত থাকে

• ফরোয়ার্ড এজ (F) − গাছের প্রান্তের একটি সেটের সমান্তরাল। (ছোট DFS নম্বর থেকে বড় DFS নম্বর, এবং বড় DFS সমাপ্তি নম্বর থেকে ছোট DFS সমাপ্তি নম্বর)

• ব্যাকওয়ার্ড এজ (B) − বড় ডিএফএস নম্বর থেকে ছোট ডিএফএস নম্বর এবং ছোট ডিএফএস সমাপ্তি নম্বর থেকে বড় ডিএফএস সমাপ্তি নম্বর।

• ক্রস এজ (C) − বড় DFS নম্বর থেকে ছোট DFS নম্বর, এবং বড় DFS সমাপ্তি নম্বর থেকে ছোট DFS সমাপ্তি নম্বর৷

ধরুন আমাদের নিচের মত একটি গ্রাফ আছে −

এখন আমরা A কে প্রাথমিক ভার্টেক্স হিসাবে গ্রহণ করে DFS সম্পাদন করব এবং DFS নম্বর এবং DFS সমাপ্তি সংখ্যা রাখব। তাই গাছটি দেখতে নিচের মত হবে -

সুতরাং DFS ট্রাভার্সাল হল A, B, F, D, G, C, E

গাছের প্রান্তগুলি হল − T ={(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}

ফরোয়ার্ড প্রান্তগুলি হল − F ={(A, G)}

পিছনের প্রান্তগুলি হল − B ={(G, B)}

ক্রস প্রান্তগুলি হল −C ={(G, D)}