数据结构与算法分析(2)

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; 图和队列使用的数组实现,虽然代码短些但是增大了使用的空间.

深度优先搜索和广度优先搜索花费的时间都是样的,定点数的平方.