微客导航 » 文章资讯 » C语言实现图的搜索算法示例

C语言实现图的搜索算法示例

2024-02-20 14:56:03 331

本文实例讲述了C语言实现图的搜索算法。分享给大家供大家参考，具体如下：

在游戏中，常常遇到路径规划问题，用到图的相关算法，我们以简单图来学习。

图通常有两种表示方式，矩阵和邻接表。矩阵表示简单，运算快，但当矩阵是稀疏矩阵的时候就存在空间浪费的问题，并且效率也会下降，而邻接表节约空间，并且由于边是连续访问，时间效率也比较高。在本文中，我们将以邻接表来表示图。

#include
#include
usingnamespacestd;
structSE{
intvIndex;
inttag;
SE*next;
};
structSMap{
SE*pE;
intnnode;
};
voidvisit(SE*se){
printf("%d\n",se->vIndex);
}
SMap*create_map(intmatrix[][6],intn){
SMap*pMap=newSMap();
pMap->nnode=n;
pMap->pE=newSE[n];
memset(pMap->pE,0,n*sizeof(SE));
for(inti=0;ipE[i].vIndex=i;
pMap->pE[i].tag=0;
SE*p=&pMap->pE[i];
for(intj=0;jnext=newSE();
p->next->vIndex=j;
p->next->tag=0;
p->next->next=NULL;
p=p->next;
}
}
}
returnpMap;
}
intBFS(SMap*pMap,intn){
queueq;
for(inti=0;ipE[i].tag==0){
q.push(&pMap->pE[i]);
while(!q.empty()){
SE*se=q.front();
q.pop();
if(pMap->pE[se->vIndex].tag==1){
continue;
}
visit(se);
pMap->pE[se->vIndex].tag=1;
SE*p=se;
while(p->next){
p=p->next;
if(pMap->pE[p->vIndex].tag==0){
q.push(p);
}
}
}
}
}
return0;
}
intDFS(SMap*pMap,intn){
stacks;
for(inti=0;ipE[i].tag==0){
s.push(&pMap->pE[i]);
while(!s.empty()){
SE*se=s.top();
s.pop();
if(pMap->pE[se->vIndex].tag==1){
continue;
}
visit(se);
pMap->pE[se->vIndex].tag=1;
SE*p=&pMap->pE[se->vIndex];
stacktmp;
while(p->next){
p=p->next;
if(pMap->pE[p->vIndex].tag==0){
tmp.push(p);
}
}
while(!tmp.empty()){
s.push(tmp.top());
tmp.pop();
}
}
}
}
return0;
}
intmain(){
intmap[6][6]={
{0,1,0,1,0,0},
{1,0,1,1,1,0},
{0,1,0,1,0,0},
{1,1,1,0,1,0},
{0,1,0,1,0,1},
{0,0,0,0,1,0}
};
SMap*smap=create_map(map,6);
//BFS(smap,6);
DFS(smap,6);
return0;
}

希望本文所述对大家C语言程序设计有所帮助。

返回顶部
3162201930
czq8825@qq.com

C语言实现图的搜索算法示例

热门推荐

随机推荐