利用链式前向星在无权图中实现寻找两点最短路径

最近参加了中兴捧月的比赛，特地挑了道图算法的题来做。经过几天的学习和思考，利用广度搜索来解决“无权图两点最短路径”，存储结构上，用链式前向星处理“稀疏图”能达到一个较低的时间复杂度。

那么什么是链式前向星呢？ 其实它是一种邻接表的数组实现方式，使用它，既能减少代码的复杂度，也能在一定的条件下节省存储空间，下面我们先学习一下这种数据存储结构（下面的课件摘自：http://malash.me/200910/linked-forward-star/）

由上可见，链式前向星其实模拟了指针的过程，这样实现起来比邻接链表要更为简单，编写效率可以说是相当高。

利用链式前向星，可以快速有效地解决诸如：SPFA，图的遍历等等问题。

接下来下面我们可以先来看看题目：

解决思路如下：

首先我们来解决如何定义一个图：

typedef struct EDGE
{
int to;
//边上的节点
int next;
//下一个节点
int weight; //权重
}EDGE;
typedef struct GRAPH
{
int *vertex;
//顶点集
EDGE *edge;
//边集
int index;
//下标值
int vertexSize; //顶点个数
int edgeSize;
//边个数
int *pre;
//前一个访问对象
int *visited;
//遍历过的点
}GRAPH;

然后我们如何构建一个无权图呢？只需要将边插入两个顶点中就好了（与邻接链表是一样）

void graphInsertE(GRAPH *g, int u, int v, int w)
{
int index = g->index;
g->edge[index].to = v;
g->edge[index].next = g->vertex[u];
g->edge[index].weight = w;
g->vertex[u] = index++;
g->index = index;
}

如何去搜寻图中最短的路径呢？其实就是去做一个广度搜索，如果遇到了我们要找的节点，就停止搜索就好了

/*******************************************************
* Function Name: BFSSearch
* Purpose: 使用广度优先找寻最短路径
* Params :
*
@GRAPH *g 图指针
*
@int s 源节点
*
@int d 目标节点
*******************************************************/
void BFSSearch(GRAPH *g, int s, int d)
{
//初始化一个队列
QUEUE *q = initQueue(g->vertexSize);
int qfront, temp;
int flag = TRUE, i;
//从源节点开始找寻
g->visited[s] = 1;
in(q, s);
//直到找到目标节点或者队列为空才停止
while(flag && !isQueueEmpty(*q))
{
out(q, &qfront);
for(i = g->vertex[qfront];flag && i;i = g->edge[i].next)
{
if(g->edge[i].weight == 1)
{
temp = g->edge[i].to;
if(!g->visited[temp])
{
in(q, temp);
g->pre[temp] = qfront;
g->visited[temp] = 1;
}
if(temp == d)
{
flag = FALSE;
}
}
}
}
//释放队列
destroyQueue(&q);
}

好了，大概的讲解就到这里，如果说大家想要了解更多的话，源代码就在附件中，可以自己下载调试