graph traversal का अर्थ है ग्राफ के प्रत्येक node को visit करना। यहाँ पर हम दो प्रकार के traversal की बात करेंगे। जो कि निम्नलिखित है:-
1. BFS (breadth first search)
2. DFS (depth first search)
1. BFS (breadth first search)
BFS ग्राफ डेटा स्ट्रक्चर को travers तथा search करने की एक अल्गोरिथम है। इसका प्रयोग ग्राफ में shortest path को ढूँढने तथा puzzle गेम्स को solve करने के लिए किया जाता है। डेटा स्ट्रक्चर में, BFS को implement करने के लिए queue का प्रयोग किया जाता है। BFS में nodes को breadth wise (चौड़ाई से) visit किया जाता है।
BFS में पहले किसी भी एक node को visit किया जाता है तथा उसके बाद उसके adjacent (नजदीक) के नोड्स को visit किया जाता है। इसके बाद इन adjacent नोड के भी सभी adjacent node को विजिट किया जाता है। और यह प्रक्रिया तब तक चलती है जब तक कि सभी nodes को विजिट नहीं कर लिया जाता है।
BFS Algorithm
इसकी अल्गोरिथम को निम्नलिखित उदहारण के द्वारा समझते है। माना कि हमारे पास निम्नलिखित ग्राफ है जिसे हमें traverse करना है।
स्टेप 1. queue को initialize किया जाता है।
स्टेप 2. सबसे पहले हम node A (शुरूआती नोड) को विजिट करते है और इसे visited मार्क करते है।
स्टेप 3. इसके बाद हम A के adjacent nodes को देखते है. इसके adjacent नोड्स B, C तथा D है। इस चित्र में हम सबसे पहले B को विजिट करते है और उसे queue में रखते है।
स्टेप 4. इसके बाद हम नोड A के adjacent node C को विजिट करते है और उसे queue में रखते है।
स्टेप 5. इसके बाद A के अंतिम adjacent नोड D को विजिट करते है और उसे queue में रखते है।
स्टेप 6. इसके बाद में A के कोई adjacent नोड नहीं बचे इसलिए हम B को queue से निकालते है और उसके adjacent को search करते है।
स्टेप 7. नोड B का adjacent नोड E है तो हम E को विजिट करते है और उसे queue में रखते है।
अब हमारे पास विजिट करने के लिए कोई भी नोड बही बचा है परन्तु हमें सभी nodes को queue से निकालना होगा। और जब queue खाली हो जायेगा तो प्रोग्राम समाप्त हो जायेगा।