实验4创建个图并输出图的深度优先和广度优先遍历结果.doc

文档介绍：实验报告
课程名称

数据结构
实验项目

创立一个图并输出图的深度优先
else
printf("%d",[i][j]);
printf("\n");
}
}
voidMatToList(MGraphg,ALGraph*&G)//将毗邻矩阵g变换为毗邻表G
{
inti,j;
intn=;
ArcNode*p;
G=(ALGraph*)malloc(sizeof(ALGraph));
for(i=0;i<n;i++)//给大的毗邻表中所有头结点的指针域副初值
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)//检查毗邻矩阵的每个元素
for(j=0;j<n;j++)
if([i][j]!=0)
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info=[i][j];
p->nextarc=G->adjlist[i].firstarc;//将*p连结到表后
G->adjlist[i].firstarc=p;
}
G->e=;
G->n=;
}
voidDispAdj(ALGraph*G)

//输出毗邻表
{
inti;
ArcNode*p;
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
if(p!=NULL)
printf("%d:",i);
while(p!=NULL)
{
printf("%d",p->adjvex);//输出弧的终点
p=p->nextarc;
}
printf("\n");
}
}
voidchange(intvisited[],ALGraph*G)//给全局变量visited赋初值
{
inti;
for(i=0;i<G->n;i++)
visited[i]=0;
}
voidListToMat(ALGraph*G,MGraphg)//将毗邻表变换为毗邻矩阵的形式
{
inti,j;
intn=G->n;
ArcNode*p;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
[i][j]=0;
for(i=0;i<n;i++)
{
p=G->adjlist[i].firstarc;
while(p!=NULL)
{
[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
=n;
=G->e;
}
voidDFS(ALGraph*G,intv)//递归深度优先遍历
{
ArcNode*p;
//change(visited,G);
visited[v]=1;//第一个点设为已被接见并输出，接着以他为主进行遍历
printf("%d",v);
p=G->adjlist[v].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc;
}
}
voidBFS(ALGraph*G,intv)
{
ArcNode*p;
intqueue[max],front=0,rear=0;//定义循环行列并初始化
intvisited[max];
intw,i;
for(i=0;i<G->n;i++)
visited[i]=0;
printf("%d",v);

//把输入的第

v个作为第一个广度遍历的节点，一直这样进
行下去
visited[v]=1;
rear=(rear+1)%max;
queue[rear]=v;

//把

v入队
while(front!=rear)

//行列不为空的时候