我已经用C++编写了深度优先搜索(DFS)算法的迭代实现。它生成正确的访问顺序作为输出。算法是这样的:
- 使用false值初始化visited[]数组
- 将第一个顶点推入堆栈
- 从堆栈中弹出元素并将其分配给变量v
- 如果v未被访问(visited[v]==false),则打印v并将其设置为visited
- 将v的每个未访问的邻居推入堆栈(首先是最大值)
- 重复3-5,直到堆叠为空
我遇到的问题是在GraphUtilities类的DFS迭代方法中确定合适的Stack大小。我的老师说它必须存储为数组。我可以使用(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
输出:
4 0 1 3 5 2
如果在visited
数组旁边使用n
大小的额外addedToStack
标志数组,您可能会更高兴。因此,如果要将顶点添加到堆栈,则不会访问它,而是将其添加到堆栈中。没有必要再次将其添加到堆栈中。每次要向堆栈中添加顶点时,请选中addedToStack标志。最终,每个顶点在堆栈中出现的次数不会超过一次,堆栈大小最多为n。