C语言：求不带权无向连通图 G 中从顶点 u 到顶点 v 的一条最短路径算法

题目

假设图 G 采用邻接表存储，设计一个算法，求不带权无向连通图 G 中从
顶到 u 到顶点 v 的一条最短路径。

分析

图 G 是不带权的无向连通图，一条边的长度计为 1,因此求顶点 u 和顶点 v 的最短即求距离顶点 u 到顶点 v 的最少顶点序列。利用广度优先遍历算法，从 u 出发进行广度遍历，类似于从顶点 u 出发一层一层地向外扩展，当第一次找到顶点 v 时队列中便包含了从顶点 u 到顶点 v 地最短路径。

代码

由于要利用队列找出路径，所以要设计成非环形队列，其类型声明如下：

typedef struct
{
	int data; //顶点编号
	int parent; //前一个顶点的位置
}QUERE; //非环形队列类型
算法图下：
void ShortPath(AdjGraph *G, int u, int v)
{ //输出从顶点 u 到顶点 v 的最短逆路径
	ArcNode *p; int w,i;
	QUERE qu[MAXV];
	int front = -1, rear = -1; //初始化队列
	int visited[MAXV]; //设置访问标记数组
	for(i = 0; i<G.vexnum; i++)
		visited[i] = 0; //初始化标记访问数组
	rear++;
	qu[rear].data = u; //顶点 u 入队
	visited[u] = 1;
	while(front!=rear)
	{
		front++;
		w = qu[front].data;
		if(w == v)
		{
			i = front;
			while(qu[i].parent != -1)
			{
				printf("%2d", qu[i].data);
				i = qu[i].parent;
			}
		printf("%2d\n", qu[i].data);
		return;
		}
		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; //寻找 w 的下一个邻接点
		}
	}
}