求一个广度优先算法的实例及其C语言程序（L-dequeue）

来源：百度知道 编辑：UC知道 时间：2024/06/14 09:32:37
L-dequeue算法是一种广度优先搜索算法，是图论学中求解最短路径问题的算法之一。由于采用的是遍历的搜索方式，所以一定能找到最优的路径解，即搜索成成功率为100%。
区别各种不同的广度优先遍历主要是在于区别分割待处理点S的策略。L-dequeue算法把待处理的点集组成一个两端插入、从一端取出的队列结构（Double-End-Queue），计算从一个节点到其它所有节点的最少费用路。

#include <stdio.h>
#define max 100
typedef struct anode
{
int adjvex; //边的终点位置
struct anode *nextarc;
}arcnode;

typedef struct node
{
int data;
arcnode *firstout;
}vnode;

typedef struct
{
vnode adjlist[max];
int n;
int e;
}Agraph;

static int visit[max];
//深度遍历
void DFS(Agraph &G,int v) //v为初始顶点编号
{
int k;
arcnode *p;
for(k=0;k<G.n;k++)
visit[k]=0;
printf("%d ",v);
p=G.adjlist[v].firstout;
while(p)
{
if(!visit[p->adjvex])
DFS(G,p->adjvex);
p=p->nextarc;
}
}

void BFS(Agraph &G,int v)
{
arcnode *p;
int q[max];
int front=0;
int rear=0;
int w,i;
for(i=0;i<G.n;i++)
visit[i]=0;
printf("%d ",v);
visit[v]=1;
rear=(rear+1)%max;
q[rear]=v;
while(f