文档介绍:.
数据构造教程
上机实验报告
实验七、图算法上机实现
一、实验目的:
认识熟知图的定义和图的基本术语,掌握图的几种存储构造。
掌握毗邻矩阵和毗邻表定义及特点,并经//成立无向图的毗邻表,n为极点数,e为边数,g[]存储n个顶
点表结点
EdgeNode*p;
inti,j,k;
printf("Inputdataofvetex(0~n-1);\n");
for(i=0;i<n;i++)//成立有n个极点的极点表
{
g[i].vertex=i;//读入极点i信息
g[i].firstedge=NULL;//初始化指向极点i的毗邻表表头
指针
}
for(k=1;k<=e;k++)//输入e条边
{
printf("Inputedgeof(i,j):");
scanf("%d,%d",&i,&j);
p=(EdgeNode*)malloc(sizeof(EdgeNode));
p->adjvex=j;//在极点vi的毗邻表中增添毗邻点为j的结
点
p->next=g[i].firstedge;//插入是在毗邻表表头进行的
'.
.
g[i].firstedge=p;
p=(EdgeNode*)malloc(sizeof(EdgeNode));
p->adjvex=i;//在极点vj的毗邻表中增添毗邻点为i的结
点
p->next=g[j].firstedge;//插入是在毗邻表表头进行的
g[j].firstedge=p;
}
}
intvisited[MAXSIZE];//MAXSIZE为大于或等于无向图极点个
数的常量
voidDFS(VertexNodeg[],inti)
{
EdgeNode*p;
printf("%4d",g[i].vertex);//输出极点i信息,即接见极点i
visited[i]=1;
p=g[i].firstedge;//根据极点i的指针firstedge查找其毗邻
表的第一个毗邻边结点
while(p!=NULL)
{
if(!visited[p->adjvex])//如果毗邻的这个边结点未被访
问过
DFS(g,p->adjvex);//对这个边结点进行深度优先搜寻
'.
.
p=p->next;//查找极点i的下一个毗邻边结点
}
}
voidDFSTraverse(VertexNodeg[],intn)
{//深度优先搜寻遍历以毗邻表存储的图,其中g为极点数,n为
极点个数
inti;
for(i=0;i<n;i++)
visited[i]=0;//接见标志置0
for(i=0;i<n;i++)//对n个极点的图查找未接见过的极点并由
该极点开始遍历
if(!visited[i])//当visited[i]等于0时即极点i未接见过
DFS(g,i);//从未接见过的极点i开始遍历
}
voidmain( )
{
inte,n;
VertexNodeg[MAXSIZE];//定义极点表结点种类数组g
printf("Inputnumberofnode:\n");//输入图中节点个数边
的个数
scanf("%d",&n);
printf("Inputnumberofedge:\n");//输入图中边的个数
'.
.
scanf("%d",&e);
printf("Makeadjlist:\n");
CreatAdjlist(g,e,n);//成立无向图的毗邻表
printf("DFSTraverse:\n");
DFSTraverse(g,n);//深度优先遍历以毗邻表存储的无向图
printf("\n");
}
运行结果: