ગ્રાફ સર્ચ અલ્ગોરિધમ એ ગ્રાફ પ્રોસેસિંગ અને માહિતી પુનઃપ્રાપ્તિના ક્ષેત્રમાં એક મૂળભૂત તકનીક છે. આ અલ્ગોરિધમ ચોક્કસ નિયમો અથવા શોધ અલ્ગોરિધમ્સના આધારે ગ્રાફમાં પાથ અથવા ઘટકો શોધવા માટે અમને સક્ષમ કરે છે.
તે કેવી રીતે કામ કરે છે
- ગ્રાફમાં ચોક્કસ શિરોબિંદુ(નોડ) થી પ્રારંભ કરો.
- ચોક્કસ નિયમોના આધારે શોધ પ્રક્રિયા કરો, જેમ કે ડેપ્થ-ફર્સ્ટ સર્ચ(DFS) અથવા બ્રેડથ-ફર્સ્ટ સર્ચ(BFS).
- લક્ષ્ય અથવા ઑબ્જેક્ટ શોધવા માટે ગ્રાફના શિરોબિંદુઓ અને કિનારીઓને પાર કરો.
- પાથ અથવા શોધ પરિણામો રેકોર્ડ કરો.
ઉદાહરણ
નીચેના ગ્રાફને ધ્યાનમાં લો:
અમે ડેપ્થ-ફર્સ્ટ સર્ચ(DFS) અલ્ગોરિધમનો ઉપયોગ કરીને આ ગ્રાફમાં શિરોબિંદુ A થી શિરોબિંદુ E સુધીનો માર્ગ શોધવા માંગીએ છીએ.
- શિરોબિંદુ A થી પ્રારંભ કરો.
- શિરોબિંદુ B પર જાઓ.
- શિરોબિંદુ C પર ચાલુ રાખો.
- C માં કોઈ પડોશીઓ નથી, શિરોબિંદુ B પર પાછા જાઓ.
- શિરોબિંદુ D પર જાઓ.
- શિરોબિંદુ A પર ચાલુ રાખો(જેમ કે D A સાથે જોડાયેલ છે).
- શિરોબિંદુ B પર જાઓ.
- શિરોબિંદુ C પર જાઓ.
- શિરોબિંદુ E પર જાઓ.
A થી E સુધીનો રસ્તો A -> B -> C -> E છે.
C++ માં ઉદાહરણ કોડ
આ ઉદાહરણમાં, અમે ગ્રાફમાં શિરોબિંદુ A થી શિરોબિંદુ E સુધીનો માર્ગ શોધવા માટે DFS અલ્ગોરિધમનો ઉપયોગ કરીએ છીએ. પરિણામ એ A થી E સુધીનો માર્ગ બનાવતા શિરોબિંદુઓનો ક્રમ હશે.