数据结构图的遍历实验报告

.

实验项目名称： 图的遍历

一、实验目的

应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验内容

问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备

计算机，Code::Blocks。 四、实验原理

用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果

#define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

教育资料

.

typedef struct ArCell{ int adj;

}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct

{ infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph;

int LocateVex(MGraph *G,char* v) { int c = -1,i;

for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;}

MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入 {

int i,j,k,w; char v1[20],v2[20];

printf(\请输入图的顶点数,弧数:\scanf(\

教育资料

.

printf(\结点名字:\\n\for(i=0;ivexnum;i++){ printf(\

scanf(\for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) G->arcs[i][j].adj=INFINITY;

printf(\请输入一条边依附的两个顶点和权值:\\n\for(k=0;karcnum;k++) {printf(\第%d条边:\\n\printf(\起始结点:\scanf(\printf(\结束结点:\scanf(\

//printf(\边的权值:\//scanf(\

i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>=0&&j>=0){ //G->arcs[i][j].adj=w; G->arcs[j][i]=G->arcs[i][j]; }} return G; }

教育资料

.

int FirstAdjVex(MGraph *G,int v) { int i;

if(v<=0 && vvexnum){ //v合理 for(i=0;ivexnum;i++) if(G->arcs[v][i].adj!=INFINITY) return i; }

return -1; }

void VisitFunc(MGraph *G,int v) {

printf(\}

int NextAdjVex(MGraph *G,int v,int w) { int k;

if(v>=0 && vvexnum && w>=0 && wvexnum)//v,w合理 {

for( k=w+1;kvexnum;k++) if(G->arcs[v][k].adj!=INFINITY) return k;

教育资料

.

}

return -1; }

int visited[MAX];

void DFS(MGraph *G,int v)//从第v个顶点出发递归地深度优先遍历图G { int w; visited[v]=1;

VisitFunc(G,v);//访问第v个结点

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w]){ DFS(G,w);

printf(\}

void DFSTraverse(MGraph *G,char *s)//深度优先遍历 {int v,k;

for(v=0;vvexnum;v++) visited[v]=0; k=LocateVex(G,s); if(k>=0&&kvexnum){ for(v=k;v>=0;v--){ if(!visited[v]) DFS(G,v);}

教育资料