data-structures
ग्राफ ट्रैवर्सल्स

परिचय

गहराई पहली खोज

एक ग्राफ के लिए डेप्थ फर्स्ट ट्रैवर्सल (या सर्च) एक पेड़ की डेप्थ फर्स्ट ट्रैवर्सल के समान है। यहां केवल एक ही पकड़ है, पेड़ों के विपरीत, ग्राफ़ में चक्र शामिल हो सकते हैं, इसलिए हम फिर से उसी नोड पर आ सकते हैं। एक बार से अधिक नोड को संसाधित करने से बचने के लिए, हम बूलियन विज़िट की गई सरणी का उपयोग करते हैं।

नीचे एल्गोरिथ्म डीएफएस का उपयोग करके ग्राफ ट्रैवर्सल के चरणों को प्रस्तुत करता है:

एल्गोरिथम डीएफएस (वी);

इनपुट : एक ग्राफ में एक शीर्ष v

आउटपुट : किनारों की "खोज" किनारों के रूप में लेबलिंग और "बैकअप"

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

पहले चौड़ाई खोजो

एल्गोरिथ्म BFS (G)

इनपुट ग्राफ जी

किनारों के आउटपुट लेबलिंग और जी के कोने के विभाजन

    for all u ∈ G.vertices()
        setLabel(u, UNEXPLORED)
    for all e ∈ G.edges()
    setLabel
    (e, UNEXPLORED)
    for all v ∈ G.vertices()
        if getLabel(v) = UNEXPLORED
            BFS(G, v)