Определение размера стека в алгоритме первого поиска (DFS) итерационной глубины

Question

Я написал итеративную реализацию алгоритма поиска первого уровня (DFS) в C++. Он производит правильный заказ на выход в качестве выхода. Алгоритм выглядит следующим образом:

1. Инициировать посещенный [] массив с ложными значениями.
2. Нажмите первую вершину в стек.
3. Поп-элемент из стека и назначить его переменной v.
4. Если v не был посещен (посещен [v] == false), напечатайте v и установите его как посетив.
5. Нажимайте на каждый не посещаемый соседний v в стек (наибольшее значение сначала).
6. Повторяйте 3-5 до тех пор, пока стек не будет пустым.

Проблема заключается в том, чтобы определить правильный размер стека в DFSIteratively методе класса GraphUtilities. Мой учитель заявил, что он должен храниться как массив. Я могу вычислить его размер, используя уравнение (n * n - 3 * n + 2)/2, где n - количество вершинных множеств, предполагая, что ни одна посещенная вершина никогда не попадает в стек и не отображается полный граф (самый плотный граф, пессимистический дело).

Можно определить размер стека для фактического графика, который, скорее всего, не будет полным графиком? Или, еще лучше, есть ли способ вытащить каждую вершину в стек только один раз? Я знаю, что рекурсивные реализации решают это ограничение, а также используют динамическую структуру данных как стек, но мой проект предполагает использование массива (образовательные цели, вот что мне сказали).

#include <iostream> 
#include <stdexcept> 
#include <list> 
#include <sstream> 
#include <fstream> 
#include <cstdlib> 
using namespace std; 

template <typename T> class Stack 
{ 
private: 
    int ptr; 
    T *stackArray; 
    int stackSize; 

public: 
    Stack(int n) 
    { 
     ptr = -1; 
     stackSize = n; 
     stackArray = new T[stackSize]; 
    } 

    ~Stack() 
    { 
     delete[] stackArray; 
    } 

    void push(T x) 
    { 
     if(ptr + 1 == stackSize) 
      throw length_error("Cannot push."); 

     stackArray[++ptr] = x; 
    } 

    T top() 
    { 
     if(ptr == -1) 
      throw length_error("Cannot pop."); 

     return stackArray[ptr]; 
    } 

    T pop() 
    { 
     T temp = top(); 
     ptr--; 

     return temp; 
    } 

    bool isEmpty() 
    { 
     if(ptr == -1) 
      return true; 

     return false; 
    } 
}; 

class Graph 
{ 
private: 
    int numberOfVertices; 
    list<int> *adjacencyList; 

public: 
    Graph(int n) 
    { 
     numberOfVertices = n; 
     adjacencyList = new list<int>[numberOfVertices]; 
    } 

    int getNumberOfVertices() 
    { 
     return numberOfVertices; 
    } 

    list<int>* getAdjacencyList(int v) 
    { 
     return &adjacencyList[v]; 
    } 

    list<int>* getAdjacencyList() 
    { 
     return adjacencyList; 
    } 

    ~Graph() 
    { 
     delete[] adjacencyList; 
    } 

    void addEdge(int v1, int v2) 
    { 
     adjacencyList[v1].push_back(v2); 
    } 
}; 

class GraphUtilities 
{ 
private: 
    bool *visited; 
    stringstream visitingOrder; 

public: 
    void DFSIteratively(Graph &g, int v) 
    { 

     int n = g.getNumberOfVertices(); 
     list<int> *adjacencyList = g.getAdjacencyList(); 
     visited = new bool[n]; 
     Stack<int> *s; 

     // Determine size of stack. 
     if(n == 1) 
      s = new Stack<int>(1); 
     else 
      s = new Stack<int>((n*n - 3*n + 2)/2); 

     for(int i = 0; i < n; i++) 
      visited[i] = false; 

     s -> push(v); 

     while(!(s -> isEmpty())) 
     { 
      v = s -> pop(); 

      if(!visited[v]) 
      { 
       visitingOrder << v << " "; 
       visited[v] = true; 

       for(list<int>::reverse_iterator i = adjacencyList[v].rbegin(); i != adjacencyList[v].rend(); ++i) 
        if(!(visited[*i])) 
         s -> push(*i); 
      } 
     } 
     cout << visitingOrder.str() << endl; 

     visitingOrder.clear(); 
     delete[] visited; 
     delete s; 
    } 
}; 

int main() 
{ 
    Graph graph(6); 
    GraphUtilities utilities; 

    graph.addEdge(0, 1); 
    graph.addEdge(0, 2); 
    graph.addEdge(0, 4); 
    graph.addEdge(1, 0); 
    graph.addEdge(1, 5); 
    graph.addEdge(2, 0); 
    graph.addEdge(2, 5); 
    graph.addEdge(3, 5); 
    graph.addEdge(4, 0); 
    graph.addEdge(5, 1); 
    graph.addEdge(5, 2); 
    graph.addEdge(5, 3); 

    utilities.DFSIteratively(graph, 4); 

    return 0; 
} 

Мой график (качество краски): http://i.imgur.com/pkGKNFo.jpg

Выход:

Answer 1

Вероятно, вы могли бы быть счастливее, если вы будете использовать дополнительные addedToStack массив флагов размера n рядом с вашим visited массив. Поэтому, если вы добавите вершину в стек, она не будет посещаться, а будет добавлена ​​в стек. Нет необходимости добавлять его в стек снова. Check addedToStack flag каждый раз, когда вы хотите добавить вершину в стек. В конце концов каждая вершина будет встречаться в стеке не более одного раза, а размер стека будет n максимум.