仲恺农业技术学院实验报告
计算机与电子工程学院 计算机科学与技术专业 数据结构课
学号 1 2 姓名 实验日期 2005-5-10 教师评定
广度优先遍历图
一、实验目的
对邻接表的认识和对图的广度优先遍历的认识。
二、实验内容
建立一个邻接表如下: 建立一个图如下:
三 、
源 程
序
# include <stdio.h>
# include <malloc.h>
# include <conio.h>
# define MAX_VERTEX_NUM 20
# define MAXQSIZE 100
# define OK 1
typedef int VertexType;
typedef int QElemType;
typedef int InfoType;
typedef struct ArcNode
{ int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct VNode
{ VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{ AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
typedef struct SqQueue
{ QElemType *base;
int front;
int rear;
}SqQueue;
int CreateDG(ALGraph *G)
{ int IncInfo,i,j,k,v1,v2,w;
ArcNode *p;
printf("请输入顶点数 G.vexnum: ");
scanf("%d",&G->vexnum);
printf("请输入弧数 G.arcnum: ");
scanf("%d",&G->arcnum);
printf(" 请 输 入 弧 相 关 指 针 IncInfo (0 for
none) :");
scanf("%d",&IncInfo);
printf("");
for(i=0;i<G->vexnum;++i)
{ G->vertices[i].data=i;
G->vertices[i].firstarc=NULL;
}
printf("请输入弧(V1-->V2)");
for(k=0;k<G->arcnum;++k)
{ printf("请输入第%d 条弧 v1: ",k+1);
scanf("%d",&v1);
printf("请输入第%d 条弧 v2: ",k+1);
scanf("%d",&v2);