દ્વિસંગી વૃક્ષ માટે બી.એફ.એસ. વિરુદ્ધ ડીએફએસ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન ઇન્ફોસિસ MAQ ટીસીએસ
બ્રેડથ ફર્સ્ટ સર્ચ Thંડાઈ પ્રથમ શોધ થિયરી વૃક્ષ

બ્રેડથ ફર્સ્ટ સર્ચ (બી.એફ.એસ.)

શું આપણે પહેલાથી જ તે વિશે જાણીએ છીએ બીએફએસ ખરેખર શું છે? જો નહીં તો ખરાબ લાગે તેવું નથી, ફક્ત આખો લેખ વાંચો અને તેના પરના પાછલા લેખની મુલાકાત લો બ્રેડથ ફર્સ્ટ સર્ચ સારી સમજ માટે. બી.એફ.એસ એ એક લેવલ ઓર્ડર ટ્રાવર્સલ છે જેમાં આપણે બાઈનરી ટ્રીના ગાંઠોની દરેક સ્તરે ડાબેથી જમણે મુલાકાત લે છે.

ની મદદથી કતાર ડેટા સ્ટ્રક્ચર, અમને લેવલ ઓર્ડર ટ્રાવર્સલ લાગે છે. અમે રુટથી શરૂ કરીએ છીએ પછી અમે બીએફએસમાં રુટ દાખલ કરીએ છીએ અને કતારમાં તે નોડના બધા પડોશીઓને દાખલ કરીએ છીએ. તે પછી કતારમાંથી નોડ પ popપ કરો અને જો તે મુલાકાત ન લેવાય તો તેને બીએફએસમાં ઉમેરો અને કતારમાં તે બધા પાડોશી (અવેક્ષિત) ઉમેરો. જ્યાં સુધી કતારનું કદ નલ બરાબર ન હોય ત્યાં સુધી તેને પુનરાવર્તિત કરો.

Thંડાઈ પ્રથમ શોધ (ડીએફએસ)

શું આપણે ખરેખર ડીએફએસ શું છે તેનાથી પરિચિત છીએ? તમે અમારા અગાઉના લેખની મુલાકાત લઈ શકો છો Thંડાઈ પ્રથમ શોધ. બીટીનો ડીએફએસ એ ત્રણ પ્રકારનાં ટ્રversવર્સલ છે:

  1. પ્રી ઓર્ડર ટ્રalવર્સલ
  2. આંતરિક ક્રમિક
  3. પોસ્ટ ઓર્ડર ટ્રversવર્સલ

પ્રી ઓર્ડર ટ્રalવર્સલ

Algorithm:
Preorder(root):
Step:1 Print the data of the Node.
Step:2 Move to the left side of the node(traverse left-subtree).
Step:3 Move to the right side of the node(traverse right-subtree).

આંતરિક ક્રમિક

Algorithm: 
Inorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree).
Step:2 Print the data of the Node.  
Step:3 Move to the right side of the node(traverse right-subtree).

પોસ્ટ ઓર્ડર ટ્રversવર્સલ

Algorithm: 
Postorder(root):  
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Move to the right side of the node(traverse right-subtree).
Step:3 Print the data of the Node.

Dજો દ્વિસંગી વૃક્ષના બી.એફ.એસ. અને ડી.એફ.એસ. વચ્ચે

વપરાયેલ ડેટા સ્ટ્રક્ચરનો પ્રકાર

બી.એફ.એસ. માં આપણે a નો ઉપયોગ કરીએ છીએ કતાર ટાઇપ ડેટા સ્ટ્રક્ચર અને ડી.એફ.એસ. માં આપણે a સ્ટેક ટાઇપ ડેટા સ્ટ્રક્ચર.

અવકાશ જટિલતા

બી.એફ.એસ. માં આપણે સ્તરના તત્વો સંગ્રહવા માટે કતારનો ઉપયોગ કરીએ છીએ જેથી બી.એફ.એસ. માં વપરાયેલ મહત્તમ જગ્યા છે ઓ (ડબલ્યુ) જ્યાં ડબલ્યુ એ એક સ્તરમાં મહત્તમ તત્વ છે. ડીએફએસમાં આપણે સ્ટેકનો ઉપયોગ કરીએ છીએ અને ofંડાઈના ખ્યાલને અનુસરીએ છીએ. તેથી, મૂલ્યાંકન માટે ઝાડની મહત્તમ heightંચાઇ મહત્તમ જગ્યા લે છે. તેથી ડીએફએસની જગ્યા જટિલતા છે ઓ (એચ) જ્યાં H એ ઝાડની heightંચાઈ છે.

સમય જટિલતા

સમય બંને કેસોની જટિલતા ઓ (એન + ઇ) હશે જ્યાં એન બીટીમાં કુલ ગાંઠો સૂચવે છે અને ઇ બીટીમાં કુલ ધાર સૂચવે છે.

રુટ નોડની નજીકની નોડ શોધી રહ્યા છે

શ્રેષ્ઠ પરિણામ મેળવવા માટે, અમે BFS નો ઉપયોગ એવા પ્રકારનાં ગાંઠો શોધવા માટે કરીએ છીએ જે રુટ નોડની નજીક છે કારણ કે તે સ્તરના ક્રમમાં આડઅસરને અનુસરે છે.

રુટ નોડથી દૂર નોડ શોધી રહ્યા છે

શ્રેષ્ઠ પરિણામ મેળવવા માટે, અમે આ કિસ્સામાં ડીએફએસનો ઉપયોગ કરીએ છીએ કારણ કે તે depthંડાઈના ખ્યાલને અનુસરે છે.

જેનો અર્થ થાય છે

બીએફએસનો અર્થ બ્રેડથ-ફર્સ્ટ સર્ચ અને ડીએફએસ એટલે ડેપ્થ-ફર્સ્ટ સર્ચ.

વપરાયેલ ડેટા સ્ટ્રક્ચરનો પ્રકાર

બીએફએસએ કતાર પ્રકારનો ડેટા સ્ટ્રક્ચર અને ડીએફએસનો ઉપયોગ સ્ટેક પ્રકાર ડેટા સ્ટ્રક્ચરનો ઉપયોગ કર્યો.

મૂળભૂત

બી.એફ.એસ એ શિરોબિંદુ આધારિત અલ્ગોરિધમનો છે અને ડીએફએસ એ એજ-આધારિત અલ્ગોરિધમનો છે.

ઝડપ

બીએફએસ ડીએફએસ કરતા ધીમું છે.

સંદર્ભ

ઇન્ટરવ્યૂ પ્રશ્નો