C语言用栈实现无向图邻接矩阵广度优先遍历(是的,广度。不是深度)目前已经写了如下代码,如图初步的构想是:用数组或结构体记录每个顶点所在层数,从顶点1开始遍历,栈空代表某顶点下一层的邻接顶点已全部输出。这个构想对吗?不对的话,有没有什么方法实现?还是说只能用两个栈做成一个队列?
//定义邻接矩阵
typedef struct {
int Edges[MAX][MAX];//邻接矩阵
int vexnum;//当前顶点个数
}MGraph;
//邻接矩阵函数
int CreatMGraph(MGraph &G)//从文件读取并输出邻接矩阵
{
FILE *fp;
if((fp=fopen("graph.txt","r"))==NULL)
{
printf("文件打开失败\n");
return 0;
}
fscanf(fp,"%d",&G.vexnum);
int i,j;
for(i=1;i<=G.vexnum;i++)
{
for(j=1;j<=G.vexnum;j++)
fscanf(fp,"%d",&G.Edges[i][j]);
}
fclose(fp);
//输出边矩阵
printf("创建无向图G1邻接矩阵如下:\n");
printf("G1顶点个数%d\n",G.vexnum);
for(i=1;i<=G.vexnum;i++)
{
for(j=1;j<=G.vexnum;j++)
{
printf("%d ",G.Edges[i][j]);
}
printf("\n");
}
return 1;
}
int FirstAdjvex(MGraph G,int i)//寻找邻接矩阵顶点i的第一个邻接顶点
{
int k;
for(k=1;k<=G.vexnum;k++)//遍历第i行的各列
{
if(G.Edges[i][k]==1)
return k;//找到第一个邻接顶点
}
return 0;//若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}
int NextAdjvex(MGraph G,int i,int j)//寻找邻接矩阵顶点i继其邻接点j后的第一个邻接点
{
int k;
for(k=j+1;k<=G.vexnum;k++)//遍历第i行的各列
{
if(G.Edges[i][k]==1)
return k;//找到第一个邻接顶点
}
return 0;//若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}
void StackBFStraverse(MGraph G)//利用栈进行广度优先遍历并判断连通性
{
printf("G1栈广度优先遍历序列如下\n");
int i,j,k,count=0;Sqstack S;int visited[MAX];
for(i=1;i<=G.vexnum;++i)
visited[i]=0;
InitStack(S);
while(层数是1)
{
k=1;
printf("%d",1);
for(k=;k;k=)
{
}
}
printf("\n");
if(count==1) printf("G1是连通图\n");
else printf("G1不是连通图,联通分量%d个\n",count);
}
供参考:队列广度优先遍历
void SqueueBFStraverse(MGraph G)//利用队列进行广度优先遍历并判断连通性
{
printf("G1队列广度优先遍历如下\n");
int i,j,k,count=0;Squeue Q;int visited[MAX];
for(i=1;i<=G.vexnum;++i)
visited[i]=0;
InitQueue(Q);
for(i=1;i<=G.vexnum;++i)
{
if(!visited[i])
{
visited[i]=1;
count++;
printf("%d",i);
Enqueue(Q,i);
while(!QueueEmpty(Q))
{
Dequeue(Q,j);//出队的队头元素设为j
for(k=FirstAdjvex(G,j);k;k=NextAdjvex(G,j,k))
{
if(!visited[k])
{
visited[k]=1;
printf("%d",k);
Enqueue(Q,k);
}
}
}
}
}
printf("\n");
if(count==1) printf("G1是连通图\n");
else printf("G1不是连通图,连通分量%d个\n",count);
}
邻接矩阵文件
8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0
自定义栈的头文件
#include <stdio.h>
#include <stdlib.h>
#define MAX 11
typedef struct{
int data[MAX];//栈中元素
int top;//栈顶指针
}Sqstack;
int InitStack(Sqstack &S)
{
S.top=-1;//数组下标从0开始,空栈顶指针指向栈底部-1
return 1;
}
int StackEmpty(Sqstack &S)
{
if(S.top==-1) return 1;
else return 0;
}
int Push(Sqstack &S,int e)//进栈
{
if(S.top==MAX-1) return 0;
S.top++;
S.data[S.top]=e;
return 1;
}
int Pop(Sqstack &S,int &e)//出栈
{
if(S.top==-1) return 0;
e=S.data[S.top];
S.top--;
return 1;
}
int GetTop(Sqstack S,int &e)//取栈顶元素
{
if(S.top==-1) return 0;
e=S.data[S.top];
return 1;
}