1．  寻找经过结点最少的路径

 

【例

1

】

图

4

表示的是从城市

A

到城市

H

的交通图。从图中可以看出，从城市

A

到

城市

H

要经过若干个城市。现要找出一条经过城市最少的一条路线。

【算法分析】

看到这图很容易想到用邻接距阵来表示，

0

表示能走，

1

表示不能走。如图。

       

首先想到的是用队列的思想。

a

数组是存储扩展结点的队列，

a[i]

记录经过

的城市

,b[i]

记录前趋城市，这样就可以倒推出最短线路。具体过程如下：

（

1

）

将城市

A

入队，队首为

0

、队尾为

1

。

（

2

）将队首所指的城市所有可直通的城市入队（如果这个城市在队列中出现

过就不入队，可用一布尔数组

s[i]

来判断），将入队城市的前趋城市保存在

b[i]

中。然后将队首加

1

，得到新的队首城市。重复以上步骤，直到搜到城市

H

时，

搜索结束。利用

b[i]

可倒推出最少城市线路。

代码：

#include

#include

using namespace std;

int a[10][10];// 0 biao  shi ke zou

int n;

int dl[90];

int pre[10],flag[10];//0 biao shi mei zou

void input()

{

       scanf("%d",&n);

       for(int i=1;i<=n;++i)

         for(int j=1;j<=n;++j)

         scanf("%d",&a[i][j]);

}

void print(int d)

{

      

       if(pre[d]!=0)

       print(pre[d]);

       printf("%d->",d);

      

}

void BFS()

{

       int head=0,tail=0;

       ++tail;

       dl[tail]=1;

       pre[1]=0;

       flag[1]=1;//1 baio shi zou guo

       while(head

       {

              ++head;

              for(int i=1;i<=n;++i)

              {

                     if(!flag[i]&&!a[dl[head]][i])

                     {

                            flag[i]=1;

                            ++tail;

                            dl[tail]=i;

                            pre[i]=dl[head];//bian hao

                     }

                     if(dl[tail]==n)

                     {

                            print(pre[n]);

                            head=tail;

                            break;

                     }

              }

       }

}

int main()

{

       freopen("1.in","r",stdin);

       input();

       BFS();

       printf("%d",n);

       return 0;

}