[输入]
图的顶点个数N，图中顶点之间的关系及起点A和终点B
[输出]
若A到B无路径，则输出“There is no path” 否则输出A到B路径上个顶点
[存储结构]
图采用邻接矩阵的方式存储。
[算法的基本思想]
采用广度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,...,VAK, 访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,...,VA1M，再访问与VA2邻接顶点...，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。
#include<stdio.h>
int number //队列类型
typedef struct{
int q[20]
标签：
输入
上传时间：
2015-11-16
上传用户：ma1301115706
