资源描述：
《数据结构图的建立和遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、课程名称：数据结构开课实验室：计算中心204室2011年10月日年级、专业、班学号姓名成绩实验项目名称图的建立和遍历指导教师教师评语教师签名：年月日一、实验内容和目的目的：撑握图的建立和遍历，熟悉图的建立和输出，还有两种遍历（深度和广度优先遍历）。内容：编出图的程序，能够体图的性质、内容和算法。二、上机实验环境计算中心204；操作系统：MicrosoftVisualC++；软件平台：MicrosoftVisualC++三、上机操作方法、步骤打开计算机进入WindowsXP→在桌面建立自己的工作目录→进入MicrosoftVisua
2、lC++6.0→文件/新建/文件/C++SourceFile/位置/命名→输入源程序→编译/组建→运行。四、设计分析：图是一种复杂的非线性结构。图结构在人工智能、计算机科学等领域有着广泛的运用。学好它就得了解结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在图结构中，对结点的前趋和后继个数都不加限制的，即结点之间的关系是任意的。#include#include#definemaxnode30#definenull0-8-#definem20typedefs
3、tructst_arc{intadjvex;intweight;structst_arc*nextarc;}arcnode;typedefstruct{intvertex;structst_arc*firstarc;}vernode;typedefvernodeadjlist[maxnode];intqueue[maxnode];voiddfs(adjlistg,intk,intvisited[])//从顶点K出发深度优先搜索{arcnode*p;intw;visited[k]=1;printf("%d",g[k].vertex)
4、;p=g[k].firstarc;while(p!=null){w=p->adjvex;if(visited[w]==0)-8-dfs(g,w,visited);p=p->nextarc;}}voidbfs(adjlistg,intk,intvisited[])//从顶点K出发广度优先搜索{intfront=0,rear=1,w;arcnode*p;visited[k]=1;//访问初始顶点printf("%d",k);queue[rear]=k;//初始顶点入队列while(front!=rear){front=(front+1
5、)%m;w=queue[front];//按访问次序依次出队列p=g[w].firstarc;while(p!=null){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%d",p->adjvex);rear=(rear+1)%m;queue[rear]=p->adjvex;;}p=p->nextarc;-8-}}}voidtrave_bfs(adjlistg,intn)//数组visited标志图中的顶点是否已被访问{inti,visited[maxnode];fo
6、r(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)bfs(g,i,visited);}voidtrave_dfs(adjlistg,intn)//数组visited标志图中的顶点是否已被访问{inti,visited[maxnode];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)dfs(g,i,visited);}voidprint(adjlistg,intn)-8-{arc
7、node*q;inti;printf("输出的是所建立无向图的邻接表结构:");for(i=1;i<=n;i++){printf("t%dt",i);printf("%d->",g[i].vertex);q=g[i].firstarc;while(q!=null){printf("%d,",q->adjvex);printf("%d->",q->weight);q=q->nextarc;}printf("Null");printf("");}}voidmain(){arcnode*p,*q;adjlistg;inti,
8、j,n,k,w,e;printf("请输入建立的无向图所包含的顶点总个数和总边数(用逗号隔开):");-8-scanf("%d,%d",&n,&e);for(k=1;k<=n;k++){getchar();printf("t输入每个顶点的信息，必
