Iterative डीएफएस बनाम रिकर्सिव डीएफएस और विभिन्न तत्वों के आदेश

Question

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

template <typename E, typename N> 
void Graph<E, N>::IterativeDFS(Node n) 
{ 
    Stack<Node> stack; 

    stack.Push(n); 

    while(!stack.IsEmpty()) 
    { 
     Node u = stack.Read(); 

     stack.Pop(); 

     if(!IsMarked(u)) 
     { 
      std::cout << ReadNode(u) << " "; 

      MarkVisited(u); 

      NodeList adjnodes = Adjacent(u); 

      NodeList::position pos = adjnodes.FirstPosition(); 

      while(!adjnodes.End(pos)) 
      { 
       stack.Push(adjnodes.ReadList(pos)); 

       pos = adjnodes.NextPosition(pos); 
      } 
     } 
    } 

:

void Graph<E, N>::DFS(Node n) 
{ 
    std::cout << ReadNode(n) << " "; 

    MarkVisited(n); 

    NodeList adjnodes = Adjacent(n); 

    NodeList::position pos = adjnodes.FirstPosition(); 

    while(!adjnodes.End(pos)) 
    { 
     Node adj = adjnodes.ReadList(pos); 

     if(!IsMarked(adj)) 
      DFS(adj); 

     pos = adjnodes.NextPosition(pos); 
    } 
} 

तो मैं एक ढेर का उपयोग कर एक सतत डीएफएस एल्गोरिथ्म लिखा है मेरी समस्या यह है कि एक ग्राफ में, उदाहरण के लिए, मैं तीन नोड्स 'ए', 'बी', 'सी' आर्क्स ('ए', 'बी') और ('ए', 'सी') के साथ दर्ज करता हूं मेरा आउटपुट है:

'ए', 'बी', 'सी' रिकर्सिव डीएफएस संस्करण के साथ , और:

'ए', 'सी', 'बी' पुनरावर्तक डीएफएस एक के साथ।

मुझे वही आदेश कैसे मिल सकता है? क्या मुझसे कुछ गलत हो रही है?

धन्यवाद!

Answer 1

दोनों मान्य डीएफएस एल्गोरिदम हैं। एक डीएफएस निर्दिष्ट नहीं करता कि आप कौन सा नोड पहले देखते हैं। यह महत्वपूर्ण नहीं है क्योंकि किनारों के बीच क्रम परिभाषित नहीं किया गया है [याद रखें: किनारों आमतौर पर एक सेट होते हैं]। अंतर प्रत्येक नोड के बच्चों को संभालने के तरीके के कारण होता है।

पुनरावृत्ति दृष्टिकोण में: आप पहले सभी तत्वों ढेर में डालने - और फिर ढेर के सिर [जो पिछले नोड डाला है] संभाल - इस प्रकार प्रथम नोड आप को संभाल अंतिम संतान है ।

रिकर्सिव दृष्टिकोण: जब आप इसे देखते हैं तो आप प्रत्येक नोड को संभालते हैं। इस प्रकार आपके द्वारा संभाला जाने वाला पहला नोड पहला बच्चा है।

पुनरावृत्ति डीएफएस पुनरावर्ती एक के रूप में एक ही परिणाम उपज करें - आप की जरूरत उलटे क्रम [प्रत्येक नोड के लिए, अपने पिछले बच्चे पहले अपने पहले बच्चे पिछले डालें और]

Answer 2

में ढेर करने के लिए तत्वों को जोड़ने

नीचे एडजेंसी मैट्रिक्स के लिए सी # में नमूना कोड (ऊपर @amit उत्तर के अनुसार) है।

using System; 
using System.Collections.Generic; 

namespace GraphAdjMatrixDemo 
{ 
    public class Program 
    { 
     public static void Main(string[] args) 
     { 
      // 0 1 2 3 4 5 6 
      int[,] matrix = {  {0, 1, 1, 0, 0, 0, 0}, 
            {1, 0, 0, 1, 1, 1, 0}, 
            {1, 0, 0, 0, 0, 0, 1}, 
            {0, 1, 0, 0, 0, 0, 1}, 
            {0, 1, 0, 0, 0, 0, 1}, 
            {0, 1, 0, 0, 0, 0 ,0}, 
            {0, 0, 1, 1, 1, 0, 0} }; 

      bool[] visitMatrix = new bool[matrix.GetLength(0)]; 
      Program ghDemo = new Program(); 

      for (int lpRCnt = 0; lpRCnt < matrix.GetLength(0); lpRCnt++) 
      { 
       for (int lpCCnt = 0; lpCCnt < matrix.GetLength(1); lpCCnt++) 
       { 
        Console.Write(string.Format(" {0} ", matrix[lpRCnt, lpCCnt])); 
       } 
       Console.WriteLine(); 
      } 

      Console.Write("\nDFS Recursive : "); 
      ghDemo.DftRecursive(matrix, visitMatrix, 0); 
      Console.Write("\nDFS Iterative : "); 
      ghDemo.DftIterative(matrix, 0); 

      Console.Read(); 
     } 

     //==================================================================================================================================== 

     public void DftRecursive(int[,] srcMatrix, bool[] visitMatrix, int vertex) 
     { 
      visitMatrix[vertex] = true; 
      Console.Write(vertex + " "); 

      for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++) 
      { 
       if (visitMatrix[neighbour] == false && srcMatrix[vertex, neighbour] == 1) 
       { 
        DftRecursive(srcMatrix, visitMatrix, neighbour); 
       } 
      } 
     } 

     public void DftIterative(int[,] srcMatrix, int srcVertex) 
     { 
      bool[] visited = new bool[srcMatrix.GetLength(0)]; 

      Stack<int> vertexStack = new Stack<int>(); 
      vertexStack.Push(srcVertex); 

      while (vertexStack.Count > 0) 
      { 
       int vertex = vertexStack.Pop(); 

       if (visited[vertex]) 
        continue; 

       Console.Write(vertex + " "); 
       visited[vertex] = true; 

       for (int neighbour = srcMatrix.GetLength(0) - 1; neighbour >= 0; neighbour--) 
       //for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++) 
       { 
        if (srcMatrix[vertex, neighbour] == 1 && visited[neighbour] == false) 
        { 
         vertexStack.Push(neighbour); 
        } 
       } 
      } 
     } 
    } 
}