实验四 图的遍历与应用
一、 实验目的 1．掌握图的含义；
2． 掌握用邻接矩阵和邻接表的方法描述图的存储结构； 3． 理解并掌握深度优先遍历和广度优先遍历的存储结构。 二、 实验要求
1． 认真阅读和掌握本实验的参考程序。
2． 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。 3． 保存程序的运行结果，并结合程序进行分析。 三、 实验内容
以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。
广度优先遍历： 具体实验的详细代码：
#define MaxVerNum 100 /* 最大顶点数为*/ #define MAXSIZE 100
typedef enum {False,True} boolean; #include \#include \typedef int DataType;
boolean visited[MaxVerNum];
typedef struct /*定義一個隊列*/ {
DataType data[MAXSIZE]; int front,rear;
}SeqQueue,*PSeqQueue;
PSeqQueue Init_SeqQueue() /*隊列初始化*/ {
PSeqQueue Q;
Q=(PSeqQueue)malloc(sizeof(SeqQueue)); if(Q) {
Q->front=0;
Q->rear=0; }
return Q; }
int In_SeqQueue(PSeqQueue Q,DataType x) /*入隊操作*/ {
if((Q->rear+1)%MAXSIZE==Q->front) {
printf(\隊滿\ return -1; } else {
Q->rear=(Q->rear+1)%MAXSIZE; Q->data[Q->rear]=x; return 1; } }
int Empty_SeqQueue(PSeqQueue Q) /*判斷隊空*/ {
if(Q&&Q->front==Q->rear) return (1); else
return (0); }
int Out_SeqQueue(PSeqQueue Q,DataType *x) /*出對操作*/ {
if(Empty_SeqQueue(Q)) {
printf(\隊空\ return -1; } else {
Q->front=(Q->front+1)%MAXSIZE; *x=Q->data[Q->front]; return 1; } }
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; /* ALGraph是以邻接表方式存储的图类型*/
void Visit(DataType w) {
printf (\}
//建立一个无向图的邻接表存储的算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/ { int i,j,k; /*int N,E;*/ EdgeNode *p; printf(\请输入顶点数和边数：\ scanf(\ printf(\ getchar(); for(i=0;i
printf(\图已成功创建!对应的邻接表如下：\\n\ for(i=0;i
} /*CreateALGraph*/
int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点 {
if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex; else return 0; }
int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点 { EdgeNode *p; p=g->adjlist[vi].firstedge; while( p!=NULL && p->adjvex!=vj) p=p->next; if(p!=NULL && p->next!=NULL) return p->next->adjvex; else return 0; }
void BFS(ALGraph *G,int v) {
/*從v出發按廣度優先遍歷圖G；使用輔助隊列Q和訪問標誌數組visited*/ EdgeNode *p; int u,w;
PSeqQueue Q; /*定義一個隊列*/ Q=Init_SeqQueue(); /*置空的隊列Q*/
Visit(v); /*訪問v，注意Visit函數和visited數組的區別*/ visited[v]=True; /*把訪問標誌置True*/ In_SeqQueue(Q,v); /*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]) {
Visit(w);
visited[w]=True;
In_SeqQueue(Q,w); /*u的尚未訪問的鄰接頂點w入隊列Q*/ } } }
} /*BFS*/
void BFStraverse(ALGraph G) {
int v;
for(v=0;v void main() { int v; ALGraph G; CreateALGraph(&G); printf(\该无向图的廣度优先搜索序列为:\ BFStraverse(G); printf(\} 广度优先遍历实验结果截图：
实验四----图的遍历与应用(广度优先遍历)
