写出对给定的无定向图从V1结点开始广度优先搜索历序列和广度优先生成树.

Question

写出对给定的无定向图从V1结点开始广度优先搜索历序列和广度优先生成树.

Answer 1

#include
#define QueueSize 100
typedef int DataType;
typedef struct{
int front;
int rear;
int count;
DataType data[QueueSize];
}CirQueue;
void InitQueue(CirQueue *Q){
Q->front=Q->rear=0;
Q->count=0;
}
int QueueEmpty(CirQueue *Q){
return Q->count==0;
}
int QueueFull(CirQueue *Q){
return Q->count==QueueSize;
}
void EnQueue(CirQueue *Q,DataType x){
if(QueueFull(Q)){
printf("Queue overflow!");
exit(1);
}
Q->count++;
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
DataType DeQueue(CirQueue *Q){
DataType temp;
if(QueueEmpty(Q)){
printf("Queue underflow!");
exit(1);
}
temp=Q->data[Q->front];
Q->count--;
Q->front=(Q->front+1)%QueueSize;
return temp;
}
DataType QueueFront(CirQueue *Q){
if(QueueEmpty(Q)){
printf("Queue is empty!");
exit(1);
}
return Q->data[Q->front];
}
#include "CirQueue.h"
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
typedef struct node{
int adjvex;
struct node *next;
}EdgeNode;
typedef struct vnode{
VertexType vertex;
EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct{
AdjList adjlist;
int n,e;
}ALGraph;
void CreateALGraph(ALGraph *G){
int i,j,k;
EdgeNode *s;
scanf("%d%d",&G->n,&G->e);
getchar();
printf("Enter the name of the nodes:\n");
for(i=0;in;i++){
G->adjlist[i].vertex=getchar();
G->adjlist[i].firstedge=NULL;
getchar();
}
for(k=0;ke;k++){
printf("Enter the edge of the graph:\n");
scanf("%d%d",&i,&j);
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=i;
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;
}
}
void DFS(ALGraph *G,int i){
EdgeNode *p;
printf("visit vertex:%c\n",G->adjlist[i].vertex);
visited[i]=TRUE;
p=G->adjlist[i].firstedge;
while(p){
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void DFSTraverse(ALGraph *G){
int i;
for(i=0;in;i++)
visited[i]=FALSE;
for(i=0;in;i++)
if(!visited)
DFS(G,i);
}
void BFS(ALGraph *G,int k){
int i;
CirQueue Q;
EdgeNode *p;
InitQueue(&Q);
printf("visit vertex:%c\n",G->adjlist[k].vertex);
visited[k]=TRUE;
EnQueue(&Q,k);
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);
p=G->adjlist[i].firstedge;
while(p){
if(!visited[p->adjvex]){
printf("visit vertex:%c\n",G->adjlist[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex);
}
p=p->next;
}
}
}
void main(){
ALGraph G;
CreateALGraph(&G);
BFS(&G,0);
}