实验四 图的遍历和应用(深度优先遍历)

实验四 图的遍历与应用

一、 实验目的 1．掌握图的含义；

2． 掌握用邻接矩阵和邻接表的方法描述图的存储结构； 3． 理解并掌握深度优先遍历和广度优先遍历的存储结构。 二、 实验要求

1． 认真阅读和掌握本实验的参考程序。

2． 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。 3． 保存程序的运行结果，并结合程序进行分析。 三、 实验内容

以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。

深度优先遍历：

#define MaxVerNum 100 /* 最大顶点数为*/ typedef enum {False,True} boolean; #include \#include \

boolean visited[MaxVerNum];

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 CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/ {

int i,j,k; int N,E; EdgeNode *p;

printf(\请输入顶点数和边数：\); scanf(\,&G->n,&G->e);

printf(\,G->n,G->e); getchar();

for(i=0;in;i++) /* 建立有n个顶点的顶点表*/ {

printf(\请输入第%d个顶点字符信息(共%d个)：\,i+1,G->n); scanf(\,&(G->adjlist[i].vertex)); /* 读入顶点信息*/ getchar();

G->adjlist[i].firstedge=NULL; /* 顶点的边表头指针设为空*/ }

for(k=0;k<2*G->e;k++) /* 建立边表*/ {

printf(\请输入边对应的顶点序号(共%d个)：\,2*G->e); scanf(\,&i,&j);/* 读入边的顶点对应序号*/

p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新边表结点p p->adjvex=j; /* 邻接点序号为j */

p->next=G->adjlist[i].firstedge;/* 将结点p插入到顶点Vi的链表头部*/ G->adjlist[i].firstedge=p; }

printf(\图已成功创建!对应的邻接表如下：\\n\); for(i=0;in;i++) {

p=G->adjlist[i].firstedge;

printf(\,G->adjlist[i].vertex); while(p!=NULL) {

printf(\,G->adjlist[p->adjvex].vertex); p=p->next; }

printf(\); }

printf(\); } /*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 DFS(ALGraph *G,int v) /* 从第v个顶点出发深度优先遍历图G */ {

int w;

printf(\,G->adjlist[v].vertex);

visited[v]=True; /* 访问第v个顶点，并把访问标志置True */ for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))

if (!visited[w]) DFS(G,w); /* 对v尚未访问的邻接顶点w递归调用DFS */ }

void DFStraverse(ALGraph *G)

/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/ { int i,v;

for(v=0;vn;v++)

visited[v]=False;/*标志向量初始化*/ //for(i=0;in;i++)

if(!visited[0]) DFS(G,0); }/*DFS*/

void main() {

ALGraph G;

CreateALGraph(&G);

printf(\该无向图的深度优先搜索序列为：\); DFStraverse(&G);

printf(\); }

深度优先遍历实验结果截图：