思想：图G是不带权的无向连通图。一条边的长度计为1，因此，求带顶点u和顶点v的最短的路径即求顶点u和顶点v的边数最少的顶点序列。利用广度优先遍历算法，从u出发进行广度遍历，类似于从顶点u出发一层一层地向外扩展，当第一次找到顶点v时队列中便包括了从顶点u到顶点v近期的路径，如图所看到的，再利用队列输出最路径（逆路径），所以设计成非循环队列。
相应算法例如以下：
typedef struct
{
int data;//顶点编号
int parent;//前一个顶点的位置
} QUEUE;//非循环队列类型
void ShortPath(AGraph *G,int u, int v)
{
//输出从顶点u到顶点v的最短逆路径
ArcNode *p;
int w,i;
QUEUE qu[MAXV];//非循环队列
int front=-1,rear=-1;//队列头尾指针
int visited[MAXV];
for(i=0;i<G->n;i++)//訪问标志设置初值0
visited[i]=0;
rear++;
qu[rear].data=u;//顶点u进队
qu[rear].parent=-1;
visited[u]=1;
while(front<=rear)//队列不为空时循环
{
front++;
w=qu[front].data;//出队顶点w
if(w==v)//找到v时输出路径之逆并退出
{
i=front;//通过队列输出逆路径
while(qu[i].parent!=-1)
{
printf("%2d",qu[i].data);
i=qu[i].parent;
}
printf("%2d\n",qu[i].data);
break;
}
p=G->adjlist[w].firstarc;//找到w的第一邻接点
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
visited[p->adjvex]=1;
rear++;//将w的未訪问过的邻接点进队
qu[rear].data=p->adjvex;
qu[rear].parent=front;
}
p=p->nextarc;
}
}
}
如图所看到的，求顶点0到3的最短逆路径的结果例如以下：
邻接表：
【0】：1->4->^
【1】：0->2->3->^
【2】：1->2->^
【3】：1->2->^
【4】：0->2->^
顶点0到顶点3的最短逆路径：3 1 0
