टी

Question

पर पथों की संख्या को खोजने के लिए टॉपोलॉजिकल सॉर्ट मुझे एक ओ (| वी | + | ई |) एल्गोरिदम विकसित करना है जो कि एक निर्देशित विश्वकोश ग्राफ (डीएजी) में, पथों की संख्या निर्धारित करता है ग्राफ के प्रत्येक वर्टेक्स टी (टी आउट-डिग्री 0 के साथ एक नोड है)। मैं इस प्रकार डीएफएस के संशोधन का विकास किया है:

DFS(G,t): 
    for each vertex u ∈ V do 
     color(u) = WHITE 
     paths_to_t(u) = 0 
    for each vertex u ∈ V do 
     if color(u) == WHITE then 
      DFS-Visit(u,t) 

DFS-Visit(u,t): 
    color(u) = GREY 
    for each v ∈ neighbors(u) do 
     if v == t then 
      paths_to_t(u) = paths_to_t(u) + 1 
     else then 
      if color(v) == WHITE then 
       DFS-Visit(v) 
      paths_to_t(u) = paths_to_t(u) + paths_to_t(v) 
    color(u) = BLACK 

लेकिन मुझे यकीन है कि अगर यह एल्गोरिथ्म संस्थानिक तरह से संबंधित है नहीं कर रहा हूँ या मैं देखने की एक अन्य बिंदु के साथ अपने काम के पुनर्गठन चाहिए।

Answer 1

यह इस प्रकार के रूप में गतिशील प्रोग्रामिंग और संस्थानिक तरह उपयोग किया जा सकता:

Topological sort the vertices, let the ordered vertices be v1,v2,...,vn 
create new array of size t, let it be arr 
init: arr[t] = 1 
for i from t-1 to 1 (descending, inclusive): 
    arr[i] = 0 
    for each edge (v_i,v_j) such that i < j <= t: 
     arr[i] += arr[j] 

जब आप [1,t] में प्रत्येक i के लिए किया जाता है,, arr[i]vi से रास्तों की संख्या बताने वाले vt को

अब

, उपर्युक्त दावा साबित करना आसान है (आपके एल्गोरिदम की तुलना में, जो मुझे नहीं पता कि यह सही है और इसे कैसे साबित किया जाए), यह प्रेरण द्वारा किया जाता है:

बेस:arr[t] == 1, और वास्तव में टी से टी, खाली एक से एक ही रास्ता है।
हाइपोथीसिस: दावा रेंज m < k <= t
सबूत में प्रत्येक k के लिए सच है: हम दिखाने के लिए दावा m के लिए सही है की जरूरत है।
चलो vm: (v_m,v_i) से प्रत्येक किनारे पर देखें।
इस प्रकार, v_m से vt से शुरू होने वाले पथों की संख्या (v_m,v_i) इस किनारे का उपयोग करती है। बिल्कुल arr[i] (प्रेरण परिकल्पना) है। v_m से किनारों की सभी संभावनाओं को सारांशित करते हुए, हमें v_m से v_t तक पथों की कुल संख्या देता है - और यह वही है जो एल्गोरिदम करता है।
इस प्रकार, arr[m] = #paths from v_m to v_t

QED

समय जटिलता:
पहला कदम (सांस्थितिक तरह) O(V+E) लेता है।
लूप एक बार सभी किनारों को फिर से चालू करता है, और सभी शीर्ष एक बार, इसलिए यह O(V+E) भी है।
यह हमें O(V+E)