key09_3.cpp

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

//{ test09_3 }
#include"graph2.h"
   const int maxnum=30;
    //arr=array[1..maxnum] of integer;
	struct queue
	   {
	   int data[maxnum];
	   int front,rear;
	};

   int  v,i;
   boolean 	visited[maxnum];
   int path[maxnum];

   void  SetQueueNull(queue& q)
     { q.front=0;
       q.rear=0;
    }

   boolean  QueueEmpty(queue& q)
     {boolean QueueEmpty=boolean(q.front==q.rear);
      return QueueEmpty;
     }

   void EnQueue(queue& q,int x)
    {
	if (1+q.rear%(maxnum-1)==q.front)
	   Error("Queue Overflow ");
	 else
	   {  q.rear=1+q.rear%(maxnum-1);
	      q.data[q.rear]=x;
	   }
    }
   int  OutQueue(queue& q)
     {  int Outqueue;

       if (QueueEmpty(q) )
	 Error("No data in queue");
       else
	 { q.front=q.front+1;
	   Outqueue=q.data[q.front];
	 }
    return  Outqueue;
    }

   void Print_Path_To(int vi)
     {
	 if (vi!=0)
	    {
	      Print_Path_To(path[vi]);
	      if ( path[vi]!=0)
		      cout<<"-->";
		   cout<< vi;
	     }
      }

   void Print_All_Path()
   {int i;

	  for (i=1;i<=nodes(g);i++)
	    {
	    cout<<endl;
	    cout<<setw(2)<<i<<": ";
	    Print_Path_To(i);
	    }
   }
   void bfsfrom(int v)
   {int u,w,n;
    char ch;
    queue q;
    datagraph g1;
       path[v]=0;
       copy_all_vertex(g,g1,300,0);
       disp_graph("广度遍历生成树",g1);
       SetQueueNull(q);
       visite_gnode(g,v,1);
       visited[v]=true;
       EnQueue(q,v);
       while (! QueueEmpty(q) )
	  {
	     u=OutQueue(q);
	     w=firstadj(g,u);
	     while (w!=0)
	       {
		 if (!visited[w])
		   {
		       copy_edge(g,u,w,g1);
		       display_edge(g1,u,w);
		       visite_gnode(g,w,1);
		       visited[w]=true;
		       EnQueue(q,w);
		       path[w]=u;
		   }
		w=nextadj(g,u,w);
	      }
	   }
      }
      main()
      { 
     load_graph_file(g,"graphs\\bfs.grp");
	  for (i=1;i<=nodes(g);i++)
	     visited[i]=false;
	  display_graph("原　图",g);
	  window(1,1,80,20);
	  for (i=1;i<=nodes(g);i++)
	     path[i]=0;
	  bfsfrom(1);
	  Wait();
	  Print_All_Path();
	  Wait();
   }