数据结构实验———图实验报告.doc

. .
优选
数 据 结 构
实
验
报
告
目的要求
１．掌握图的存储思想及其存储实现。
２．掌握图的深度、广度优先遍历算法思想及其程序实现。
３．掌握图的常见应用link(ALGraph *G)
{ int i,j;
ArcNode *s;
printf("请依次输入顶点数、边数：");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i=0;i<G->vexnum;i++)
{ G->vertices[i].data='A'+i;
G->vertices[i].firstarc=NULL;
}
for (i=0;i<G->vexnum;)
{ printf("请输入顶点的数组坐标(假设退出，请输入-1)：");
scanf("%d",&i);
if(i==-1) break;
printf("请输入顶点所指向下一个顶点的数组坐标：");
scanf("%d",&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j;
s->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=s;
}
}
// 输出邻接表
void visit(ALGraph G)
{ int i;
ArcNode *p;
printf("%4s%6s%18s\n","NO","data","adjvexs of arcs");
. .
优选
for (i=0;i<;i++)
{
printf("%4d%5c ",i,[i].data);
for(p=[i].firstarc;p;p=p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}
}
// 计算各顶点的度及入度
void cacu(ALGraph *G)
{
ArcNode *p;
int i;
for (i=0;i<G->vexnum;i++)
{G->vertices[i].degree=0;G->vertices[i].indegree=0;}//度与初度初始化为零
for (i=0;i<G->vexnum;i++)
for(p=G->vertices[i].firstarc;p;p=p->nextarc)
{G->vertices[i].degree++;
G->vertices[p->adjvex].degree++;
G->vertices[p->adjvex].indegree++;
}