采用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的廣度優(yōu)先遍歷

課程設(shè)計(jì)題目九：圖的廣度優(yōu)先遍歷

基本要求：

采用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的廣度優(yōu)先遍歷。

（2）對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出；

（3）實(shí)現(xiàn)圖的廣度優(yōu)先遍歷*/

#include<>

#include<>

#include<>

#defineMAX_NUM20

intvisited[MAX_NUM]={0};

typedefintVertexType;

typedefenum{DG=1,UDG}GraphKind;

typedefstructArcNode

{

intadjvex;

intweight;

structArcNode*nextarc;

ArcNode*info;

}ArcNode;

typedefstructVNode

{

VertexTypedata;

ArcNode*firstarc;

}VNode,AdjList[MAX_NUM];

typedefstruct

{

AdjListvertices;

intvexnum,arcnum;

GraphKindkind;

}ALGraph;

voidPRIN(ALGraph&G);

voidCreat_adjgraph(ALGraph&G);

voidbfs(ALGraph&G,intv);

voidCreat_adjgraphDG(ALGraph&G);

voidCreat_adjgraphUDG(ALGraph&G);

voidCreat_adjgraph(ALGraph&G);

voidCreat_adjgraphDG(ALGraph&G)

{

inti,s,d;

ArcNode*p=NULL,*q=NULL;=DG;

printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");

scanf("%d%d",&,&;

for(i=0;i<;++i)

{

printf("第%d個(gè)頂點(diǎn)信息：",i+1);

scanf("%d",&[i].data);

[i].firstarc=NULL;}

for(i=0;i<;++i)

{

printf("第%d條邊的起始頂點(diǎn)編號(hào)和終止頂點(diǎn)編號(hào)：",i+1);

scanf("%d%d",&s,&d);

while(s<1||s>||d<1||d>

{

printf("編號(hào)超出范圍，重新輸入");

scanf("%d%d",&s,&d);}

s--;

d--;

p=new(ArcNode);

p->adjvex=d;

p->nextarc=[s].firstarc;

[s].firstarc=p;

}

}

voidCreat_adjgraphUDG(ALGraph&G)

{

inti,s,d;

ArcNode*p,*q;

=UDG;

printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");

scanf("%d%d",&,&;

for(i=0;i<;++i)

{

printf("第%d個(gè)頂點(diǎn)信息：",i+1);

scanf("%d",&[i].data);

[i].firstarc=NULL;}

for(i=0;i<;++i)

{

printf("第%d條邊的起始頂點(diǎn)編號(hào)和終止頂點(diǎn)編號(hào)：",i+1);

scanf("%d%d",&s,&d);

while(s<1||s>||d<1||d>

{

printf("編號(hào)超出范圍，重新輸入");

scanf("%d%d",&s,&d);}

s--;

d--;

p=new(ArcNode);

p->adjvex=d;

p->nextarc=[s].firstarc;

[s].firstarc=p;

q=new(ArcNode);

q->adjvex=s;

q->nextarc=[d].firstarc;

[d].firstarc=q;

}

}

voidPRIN(ALGraph&G)

{

inti;

ArcNode*p;

if==DG||==UDG)

{

for(i=0;i<;++i)

{

printf("V%d:",[i].data);

p=[i].firstarc;

while(p!=NULL)

{

printf("%d\t",p->adjvex+1);

p=p->nextarc;}

printf("\n");}

}

}

voidbfs(ALGraph&G,intv)

{

v--;

ArcNode*p;

intqueue[MAX_NUM],front=0,rear=0;

intw,i;

for(i=0;i<;i++)visited[i]=0;

printf("%4d",v+1);

visited[v]=1;

rear=(rear+1)%MAX_NUM;

queue[rear]=v;

while(front!=rear)

{

front=(front+1)%MAX_NUM;

w=queue[front];

p=[w].firstarc;

while(p!=NULL)

{

if(visited[p->adjvex]==0)

{

printf("%3d",p->adjvex+1);

visited[p->adjvex]=1;

rear=(rear+1)%MAX_NUM;

queue[rear]=p->adjvex;}

p=p->nextarc;}

}

printf("\n");

}

voidCreat_adjgraph(ALGraph&G)

{

printf("1：有向圖2：無向圖\n");

printf("請(qǐng)根據(jù)上述提示輸入圖的類型："

);

scanf("%d",&;

switch

{

caseDG:Creat_adjgraphDG(G);PRIN(G);break;

caseUDG:Creat_adjgraphUDG(G);PRIN(G);break;

default:printf