// Abstract queue class
template <class Elem> class Queue { public:
// Reinitialize the queue. The user is responsible for // reclaiming the storage used by the stack elements. virtual void clear() = 0;
// Place an element at the rear of the queue. Return // true if successful, false if not (if queue is full). virtual bool enqueue(const Elem&) = 0;
// Remove the element at the front of the queue. Return // true if succesful, false if queue is empty.
// The element removed is returned in the first parameter. virtual bool dequeue(Elem&) = 0; // Remove Elem from front // Return in first parameter a copy of the front element. // Return true if succesful, false if queue is empty. virtual bool frontValue(Elem&) const = 0; // Return the number of elements in the queue. virtual int length() const = 0; };
// Array-based queue implementation
template <class Elem> class AQueue: public Queue<Elem> { private:
int size; // Maximum size of queue int front; // Index of front element int rear; // Index of rear element
Elem *listArray; // Array holding queue elements public:
AQueue(int sz =DefaultListSize) { // Constructor
// Make list array one position larger for empty slot size = sz+1;
rear = 0; front = 1; listArray = new Elem[size]; }
~AQueue() { delete [] listArray; } // Destructor void clear() { front = rear; } bool enqueue(const Elem& it) {
if (((rear+2) % size) == front) return false; // Full rear = (rear+1) % size; // Circular increment listArray[rear] = it; return true;
}
bool dequeue(Elem& it) {
if (length() == 0) return false; // Empty
深度优先搜索和广度优先搜索算法实现
it = listArray[front];
front = (front+1) % size; // Circular increment return true; }
bool frontValue(Elem& it) const { if (length() == 0) return false; // Empty it = listArray[front]; return true; }
virtual int length() const
{ return ((rear+size) - front + 1) % size; } };
void PreVisit(Graph* G, int v) {
cout << "PreVisit vertex " << v << "\n"; }
void PostVisit(Graph* G, int v) {
cout << "PostVisit vertex " << v << "\n"; }
void DFS(Graph* G, int v) { // Depth first search PreVisit(G, v); // Take appropriate action G->setMark(v, VISITED);
for (int w=G->first(v); w<G->n(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED)
DFS(G, w); PostVisit(G, v); // Take appropriate action }
void BFS(Graph* G, int start, Queue<int>* Q) { int v, w;
Q->enqueue(start); // Initialize Q G->setMark(start, VISITED);
while (Q->length() != 0) { // Process all vertices on Q Q->dequeue(v);
PreVisit(G, v); // Take appropriate action for (w=G->first(v); w<G->n(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) { G->setMark(w, VISITED);
Q->enqueue(w); }
PostVisit(G, v); // Take appropriate action
深度优先搜索和广度优先搜索算法实现
}
}
// Test Depth First Search and Breadth First Search int main(int argc,char *argv[]){
Graph* g=new Graphm(6);// Initialize a graphm g int chance; g->setEdge(0,2,1); g->setEdge(2,0,1); g->setEdge(2,1,1); g->setEdge(1,2,1); g->setEdge(1,5,1); g->setEdge(5,1,1); g->setEdge(2,5,1); g->setEdge(5,2,1); g->setEdge(3,5,1); g->setEdge(5,3,1); g->setEdge(2,3,1); g->setEdge(3,2,1); g->setEdge(4,5,1); g->setEdge(5,4,1);
g->setEdge(0,4,1); g->setEdge(4,0,1);
cout<<"enter the number "<<endl<<"1 to do the Depth First Search "<<endl <<"2 to do Breadth First Search"<<endl; cin>>chance; if( chance == 1){
cout<<"the Depth First Search is"<<endl; DFS(g,0); }
else if(chance== 2){
AQueue<int>* q=new AQueue<int>(6); // Initialize q cout<<"the Breadth First Search is"<<endl; BFS(g,0,q); }
else {
cout<<"you enter the wrong number"<<endl; } return 0; }
六、运行结果:
深度优先搜索和广度优先搜索算法实现
七、实验运行情况分析.
算法: 图和队列都是使用的数组实现的,但用邻接矩阵实现图的时候要注意, void setEdge(int v1, int v2, int wgt) 中在图的实例化的时候wgt为0是表示的是 int1和int2没有连通,但在用邻接表实现图的时候wgt为1表示这条边上的权是1; 图和队列使用的数组实现,虽然代码短些但是增大了使用的空间.
深度优先搜索和广度优先搜索花费的时间都是样的,定点数的平方.