文档介绍:实验内容: 实验时间:2012 年 06 月 15 日
,采用邻接矩阵表示法,构造一个无向网。
,实现从键盘输入数据,建立一个有向图的邻接表。
,输出该邻接表。
,采用邻接表存储实现无向图的深度优先非递归遍历。
,采用邻接表存储实现无向图的广度优先遍历。
,在主函数中设计一个简单的菜单,分别调试上述算法。
实验目的及要求:
、广度优先遍历算法思想及其程序实现
实验内容、方法与步骤:(使用附页填写并附在本页后)
实验结果:
小结:
通过这次实验,我掌握了图的存储思想及其存储实现,认识到图的深度、广度优先遍历算法思想及其程序实现,深刻了解了图的常见应用算法的思想及其实现程序。
#include <>
#include<>
#include<>
#define MaxVertexNum 10 /* 顶点最大个数*/
#define MAXSIZE 100
#define INFINITY 10000 /* 用10000代替∞*/
typedef struct ell
{ int adj;
}ell,AdjMatrix[MaxVertexNum][MaxVertexNum];
typedef struct
{int vexs[MaxVertexNum];
AdjMatrix arcs;
int vexnum,um;
}Mgragh;
/*构造无向网*/
Mgragh *CreateUDN(Mgragh *N)
{
int i,j,k,w;
int v1,v2;
printf("\t输入顶点个数和边数:");
scanf("\t%d %d",&N->vexnum,&N->um);
printf("\t输入%d个顶点的元素:",N->vexnum);
for(i=0;i<N->vexnum;i++){
scanf("\t%d",&N->vexs[i]); }
for(i=0;i<N->vexnum;i++)
for(j=0;j<N->vexnum;j++)
N->arcs[i][j].adj=INFINITY;
for(k=0;k<N->um;k++){
printf("\t输入第%d条边所依附的顶点:",k+1);
scanf("\t%d%d",&v1,&v2);
printf("\t输入权值:");
scanf("\t%d",&w);
for(i=0;i<N->vexnum;i++)
if(v1==N->vexs[i]) break;
for(j=0;j<N->vexnum;j++)
if(v2==N->vexs[j]) break;
N->arcs[i][j].adj=w;
N->arcs[j][i]=N->arcs[i][j];
} printf("\t ");
for(i=0;i<N->vexnum;i++) printf(" \t v%d",N->vexs[i]); printf(