实验四、图的遍历
一、 实验目的
1．理解并掌握图的逻辑含义；
2．掌握用邻接矩阵和邻接表的方法描述图的存储结构，并能根据实际问题选择合适的存储结构；
3．理解并掌握深度优先遍历和广度优先遍历算法，能够运用遍历算法求解图的应用问题。 二、 实验要求
1． 认真阅读和掌握本实验的参考程序。
2． 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。 3． 保存程序的运行结果，并结合程序进行分析。 三、 实验内容
以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。
参考程序略 代码如下： #include \"stdio.h\" #include \"stdlib.h\" #define MAXSIZE 100
#define MaxVerNum 100 typedef enum{False,True} boolean; boolean visited[MaxVerNum];
typedef struct {
int data[MAXSIZE];
int front,rear;
}SeqQueue,*PSeqQueue;
typedef struct node {
int adjvex; char Info; struct node *next; }EdgeNode;
typedef struct vnode {
char vertex;
EdgeNode *firstedge; }VertexNode;
typedef struct {
VertexNode adjlist[MaxVerNum]; int n,e; }ALGraph;
PSeqQueue Init_SeqQueue() {
PSeqQueue Q;
Q=(PSeqQueue)malloc(sizeof(SeqQueue)); if(Q) {
Q->front=0;
Q->rear=0;
} return Q; }
int Empty_SeqQueue(PSeqQueue Q) { }
int In_SeqQueue(PSeqQueue Q, int x) {
if((Q->rear+1)%MAXSIZE==Q->front) {
if(Q && Q->front==Q->rear) return 1; else return 0;
}
}
printf(\"队满\"); return -1;
else { }
Q->rear=(Q->rear+1)%MAXSIZE; Q->data[Q->rear]=x; return 1;
int Out_SeqQueue(PSeqQueue Q,int *x) {
if(Empty_SeqQueue(Q)) { } else {
Q->front=(Q->front+1)%MAXSIZE; *x=Q->data[Q->front]; printf(\"队空\"); return -1;
}
}
return 1;
void CreateALGraph(ALGraph *G) {
int i,j,k;
EdgeNode *p;
printf(\"请输入顶点数和边数：\"); scanf(\"%d %d\ printf(\"n=%d,e=%d\\n\\n\ getchar();
for(i=0;in;i++) {printf(\"请输入第%d个顶点字符信息(共%d个)：\ scanf(\"%c\ getchar();
G->adjlist[i].firstedge=NULL; }
for(k=0;k<2*G->e;k++) {
printf(\"请输入边对应的顶点序号(共%d个)：\ scanf(\"%d %d\p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=j;
p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; }
printf(\"\\n图已成功创建!对应的邻接表如下：\\n\"); for(i=0;in;i++) {p=G->adjlist[i].firstedge;
printf(\"%c->\ while(p!=NULL) {
printf(\"[ %c ]\ p=p->next; }
printf(\"\\n\"); }
printf(\"\\n\"); }
void Visit(int v) { }
void BFS(ALGraph *G,int v) {
EdgeNode *p;
int u,w; PSeqQueue Q; Q=Init_SeqQueue(); Visit(v); visited[v]=True; In_SeqQueue(Q,v);
while(!Empty_SeqQueue(Q)) {
Out_SeqQueue(Q,&u);
for(p=G->adjlist[u].firstedge;p;p=p->next ) {
w=p->adjvex; if(!visited[w]) {
printf(\" %d,\
}
}
}
}
Visit(w); visited[w]=True; In_SeqQueue(Q,w);
void BFStraverse (ALGraph *G) { int i,v ;
for(v=0;vn;v++)visited[v]=False; for(i=0;in;i++)if(!visited[i]) BFS (G,i); }
int main() {
ALGraph G;
CreateALGraph(&G);
printf(\"该无向图的广度优先搜索序列为：\");
BFStraverse(&G); printf(\"\\nsuccess!\\n\\n\"); }
运行结果如下：
return 0;
