问答题 设无向图G有n个顶点e条边,写一算法建立G的邻接多重表,要求该算法时间复杂性为O(n+e),且除邻接多重表本身所占空间之外只用O(1)辅助空间。【东南大学1995六(16分)1997二(15分)】
【正确答案】正确答案:邻接多重表的边结点结构是(ivex,jvex,ilink,jlink,mark)。输入一条边的核心语句段如下: cin>>vl>>v2 ; i=GraphLocateVertex(g,V1);j=GraphLocateVertex(g,v2); p=new(ENode);//申请边结点 P一>ivex=i;p->jvex=j; P一>ilink=g[i].firstedge;p一>j link=g[j].firstedge; g[i].firstedge=p;g[j].firstedge=p;
【答案解析】