Question

C语言实现图的广度优先搜索遍历算法

非递归的...

Answer 1

先写个大题思路，楼主先自己想想，想不出来的话，2天后给代码。

queue<node> q;
q.push(start);
bool canVisit[][];
node cur;
while(!q.empty()){
cur = q.top();
q.pop();
foreach(node is connected by cur){
if(canVisit[node.x][node.y])
{
printf("访问结点(%d,%d)",node.x,node.y);
canVisit[node.x][node.y]=false;
q.push(node);
}
}
}

追问

同学，我急用的，两天后就不需要了...，谢啦...

追答

#include
#include
#include
#include

using std::queue;//队列懒得自己写了，C++之，楼主有兴趣可以自己实现

#define MN 10000
#define ME 100000
/*链式前向星*/
int n,e;//结点数，边数
int box[MN];
struct
{
int pre;//前向对应的edge数组下标
int to;//对应要去的结点
}edge[ME];
int len;
void iniPreLinkList()
{
memset(box,-1,sizeof(box));
len=0;
}
void addDirectedEdge(int from,int to)
{
edge[len].to = to;
edge[len].pre = box[from];
box[from] = len;
len++;
}
void printList()
{
int address;
int i;
for(i=0;i%d",edge[address].to);
}
printf("\n");
}
}
/*链式前向星*/
int canVisit[MN];
void visit(int address)//访问结点，可根据情况，修改box结点域的结构
{
printf("访问结点%d\n",edge[address].to);
}
void bfs(int start)
{
memset(canVisit,1,sizeof(canVisit));
queue q;
q.push(start);
int cur;
int address;
printf("开始宽搜了哦~~~\n");
visit(start);
canVisit[start]=0;
while(!q.empty())
{
cur = q.front();
q.pop();
for(address=box[cur];address!=-1;address = edge[address].pre)
{
if(canVisit[edge[address].to])
{
visit(address);
canVisit[edge[address].to] = 0;//标记，访问过的不再访问
q.push(edge[address].to);//新访问的结束
}
}
}
printf("遍历完成\n");
}
int main()
{
int i;
int from,to;
while(~scanf("%d%d",&n,&e))//输入结点数，边数
{
iniPreLinkList();
for(i=0;i<e;i++)
{
scanf("%d%d",&from,&to);//输入边
addDirectedEdge(from,to);
}
printf("刚才构造的邻接链表为：\n");
printList();
printf("\n");
bfs(0);
}
return 0;
}
/*
4 4
0 1
1 2
0 2
1 3
*/

Answer 2

...