校园导游程序 用无向图表示校园的景点 存放景点名称 路径等信息.doc

校园导游程序 用无向图表示校园的景点 存放景点名称 路径等信息.doc

《校园导游程序 用无向图表示校园的景点 存放景点名称 路径等信息.doc》由会员分享，可在线阅读，更多相关《校园导游程序 用无向图表示校园的景点 存放景点名称 路径等信息.doc（4页珍藏版）》请在冰点文库上搜索。

#include

constintn=4; //n表示校园图中顶点个数

constinte=5; //e表示校园图中路径

boolvisited[n+1]; 

#definemax32767

classgraph

{

public:

 intarcs[n+1][n+1]; //领结矩阵

 inta[n+1][n+1];   //距离

 intpath[n+1][n+1]; //景点

 voidfloyd（graph&t,constintn）;

 voidpicture（）;

 voidcreatp（graph&t）;

 voidbfs（grapht）;

};

voidgraph:

:

picture（）

{

 cout<<"   ******校园导游图******"<

 cout<<"以下是学校的景点"<

 cout<<"  ***************************"<

 cout<<"  * 1.校园门口  2.图书管 *"<

 cout<<"  *                        *"<

 cout<<"  * 3.饭堂      4.教学楼 *"<

 cout<<"  ***************************"<

 cout<<"以下是学校的路径图"<

 cout<<"    3"<

 cout<<"   1*---------*2 "<

 cout<<"    |       /|"<

 cout<<"    |      /|"<

 cout<<"    |     / |"<

 cout<<"   4|   9/  |5 "<

 cout<<"    |   /   |"<

 cout<<"    |  /    |"<

 cout<<"    | /     |"<

 cout<<"    |/      |"<

 cout<<"   3*---------*4  "<

 cout<<"    2"<

 cout<<"下面是景点与景点之间的距离和介绍：

";

 cout<<"1.校园门口--》2.图书管  距离为：

3"<

 cout<<"1.校园门口--》3.饭堂    距离为：

4"<

 cout<<"2.图书管  --》4.教学楼  距离为：

4"<

 cout<<"2.图书管  --》3.饭堂    距离为：

9"<

 cout<<"3.饭堂    --》4.教学楼  距离为：

5"<

 //校园图

}

voidgraph:

:

creatp（graph&t）

{

 inti,j;

 for（i=1;i<=n;i++）

 for（j=1;j<=n;j++）

  if（i==j）t.arcs[i][j]=0; //景点一样则距离为0

  elset.arcs[i][j]=max; //i不等于j时

   t.arcs[1][2]=3;

  t.arcs[2][1]=3;

  t.arcs[2][4]=5;

  t.arcs[4][2]=5;

  t.arcs[3][1]=4;

  t.arcs[1][3]=4;

  t.arcs[3][2]=9;

  t.arcs[2][3]=9;

  t.arcs[3][4]=2;

  t.arcs[4][3]=2

   //把景点跟距离用一个二围数组存储下来

}

voidgraph:

:

floyd（graph&t,constintn）

{

  for（inti=1;i<=n;i++）

  for（intj=1;j<=n;j++）

  {

   t.a[i][j]=t.arcs[i][j]; //把距离付值给a.[i][j]

   if（（i!

=j）&&（a[i][j]

    t.path[i][j]=i;

   elset.path[i][j]=0;

  }

  for（intk=1;k<=n;k++）

  {

   for（i=1;i<=n;i++）

   for（intj=1;j<=n;j++）

    if（t.a[i][k]+t.a[k][j]

    {

     t.a[i][j]=t.a[i][k]+t.a[k][j];

     t.path[i][j]=t.path[k][j];

    }

  }

}

voidgraph:

:

bfs（grapht） //从顶点i出发实现广度搜索搜索n

{

 intj,i;           //f，r分别为队列头，尾指针

 charch;

 cout<<"请输入一个你想去的地方:

";

 cin>>i;

 while（i<=4）

 {

 //cout<

 //for（i;i<=n;i++）

  if（i==1）cout<<"这里就是你要去的地方拉!

!

"<

  else

  {

  for（j=1;j<=n;j++）

  {

   if（i!

=j）

   {

    cout<<"距离为"<

 ";

    intnext=t.path[i][j];

    cout<

    while（next!

=i）

    {

     cout<<"--"<

     next=t.path[i][next];

    }

    cout<<"--"<

   }

  }

  cout<<"等我推荐一条最佳路径供你返回吧（y/n）:

";

  }

  cin>>ch;

  if（ch=='y'）

  {

   if（i==2）cout<<"2--4--3--1"<

   if（i==3）cout<<"3--2--1或者3--4--2--1"<

   if（i==4）cout<<"如果你想去四景点我们会带你游览学校全景：

1--2--4--3--1"<

   cout<<"你还想去别的地方吗?

（y/n）";

   cin>>ch;

     if（ch=='y'）{cout<<"请输入一个你想去的地方:

"; cin>>i;}

     if（ch!

='y'） 

   {

    cout<<"         *****退出程序*****"<

    cout<<"            欢迎下次再来"<

    break;

   }

  }

  else

  {

   break;

  }

 }

}

voidmain（）

{

 grapht;

 t.picture（）;

 t.creatp（t）;

 t.floyd（t,n）;

 t.bfs（t）;

}