数据结构实验八 图的创建与遍历.doc
文本预览下载声明
实验八 图的创建与遍历
实验目的：
通过上机实验进一步掌握图的存储结构及基本操作的实现。
实验内容与要求：
分别基于邻接矩阵和邻接表存储结构实现图的基本运算，要求：
⑴能根据输入的顶点、边/弧的信息建立图；
⑵实现图中顶点、边/弧的插入、删除；
⑶实现对该图的深度优先遍历；
⑷实现对该图的广度优先遍历。
源程序：
#includestdio.h
#includestdlib.h
#define intinity 1024
#define maxvex 20
typedef struct{
char vex[maxvex];
int arcs[maxvex][maxvex];
}Mgraph;\\数组式结构体
void Createmgraph(Mgraph G,int n)\\创建邻接矩阵图函数，这个简单按照一般步骤就可以了
{int i,j;
printf(请输入顶点\n);
for(i=1;i=n;i++)
{scanf(%c,G.vex[i]);
fflush(stdin);
}
printf(请输入邻接矩阵(先行后列)\n);
for(i=1;i=n;i++)
for(j=1;j=n;j++)
{scanf(%d,G.arcs[i][j]);
fflush(stdin);
}
printf(创建图的邻接矩阵为\n);
for(i=1;i=n;i++)
printf(%3c,G.vex[i]);\\这里动脑筋使他输出的界面看起来就像是一个矩阵，对位置和空格进行了调整。
printf(\n);
for(i=1;i=n;i++)
{ printf(%c,G.vex[i]);
for(j=1;j=n;j++)
printf(%2d ,G.arcs[i][j]);
printf(\n);
}
}
void Insertmgraph(Mgraph G,int n)\\插入函数，这里有个缺陷，只能在尾部插入，那就简单了
{int i,j;
printf(请输入插入的节点\n);
scanf(%c,G.vex[n+1]);
printf(请输入扩建的邻接表(先行后列)\n);
for(j=1;j=(n+1);j++)
{scanf(%d,G.arcs[n+1][j]);
fflush(stdin);
}
for(i=1;i(n+1);i++)
{scanf(%d,G.arcs[i][n+1]);
fflush(stdin);
}
printf(输出新的图\n);
for(i=1;i=(n+1);i++)
printf(%3c,G.vex[i]);
printf(\n);
for(i=1;i=(n+1);i++)
{ printf(%c,G.vex[i]);
for(j=1;j=(n+1);j++)
printf(%2d ,G.arcs[i][j]);
printf(\n);
}
}
void Deleatmgraph(Mgraph G,int n,int m)\\删除函数，这里不局限在哪一个点，删哪一个都可以，不过删最后对下面有好处。
{int i,j;
printf(请输入要删除的节点\n);
scanf(%c,G.vex[m]);
for(i=m;in;i++)
G.vex[i]=G.vex[i+1];
for(i=1;i=n;i++)
for(j=m;jn;j++)
G.arcs[i][j]=G.arcs[i][j+1];
for(j=1;jn;j++)
for(i=m;in;i++)
G.arcs[i][j]=G.arcs[i+1][j];
printf(输出新的图\n);
for(i=1;in;i++)
printf(%3c,G.vex[i]);
printf(\n);
for(i=1;in;i++)
{ printf(%c,G.vex[i]);
for(j=1;jn;j++)
printf(%2d ,G.arcs[i][j]);
printf(\n);
}
}
void Bfstraverse(Mgraph G,int n)\\广度遍历函数，由于每个函数之间都有影响所以不得不在深度函数前运行
{int i,j,t,k=2;
显示全部