主题:求助 图的遍历演示
课程设计:要以邻接多重表为储存结构实现连通无向图的深度优先和广度优先遍历,输出每种遍历下节点访问序列和生成树的边集
深度广度的算法都有,但是不会建立邻接多重表,这里有个算法,谁能把它写成C程序啊?谢谢了
Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表
{
InitAMLGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //顶点数不能为负
G.vexnum=v;
scanf(%d",&a);
if(a<0) return ERROR; //边数不能为负
G.arcnum=a;
for(m=0;m<v;m++)
G.adjmulist[m].data=getchar(); //输入各顶点的符号
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到
p=(EBox*)malloc(sizeof(EBox));
p->ivex=i;p->jvex=j;
p->ilink=NULL;p->jlink=NULL; //边结点赋初值
if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->ivex==i) q=q->ilink;
else q=q->jlink;
}
if(r->ivex==i) r->ilink=p;//注意i值既可能出现在边结点的ivex域中,
else r->jlink=p; //又可能出现在边结点的jvex域中
}//else //插入i链表尾部
if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->jvex==j) q=q->jlink;
else q=q->ilnk;
}
if(r->jvex==j) r->jlink=p;
else r->ilink=p;
}//else //插入j链表尾部
}//for
return OK;
}//Build_AdjList
深度广度的算法都有,但是不会建立邻接多重表,这里有个算法,谁能把它写成C程序啊?谢谢了
Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表
{
InitAMLGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //顶点数不能为负
G.vexnum=v;
scanf(%d",&a);
if(a<0) return ERROR; //边数不能为负
G.arcnum=a;
for(m=0;m<v;m++)
G.adjmulist[m].data=getchar(); //输入各顶点的符号
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到
p=(EBox*)malloc(sizeof(EBox));
p->ivex=i;p->jvex=j;
p->ilink=NULL;p->jlink=NULL; //边结点赋初值
if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->ivex==i) q=q->ilink;
else q=q->jlink;
}
if(r->ivex==i) r->ilink=p;//注意i值既可能出现在边结点的ivex域中,
else r->jlink=p; //又可能出现在边结点的jvex域中
}//else //插入i链表尾部
if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->jvex==j) q=q->jlink;
else q=q->ilnk;
}
if(r->jvex==j) r->jlink=p;
else r->ilink=p;
}//else //插入j链表尾部
}//for
return OK;
}//Build_AdjList