159能量餐代理招商:关于严蔚敏《数据结构》习题集的一道题的解答
现在有的答案是这样的(就是网上流传的那个答案集中的):
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //将第一个顶点入栈
visit(1);
visited =1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i);
if(j&&!visited[j])
{
visit(j);
visited[j]=1;
Push(S,j); //向左走到尽头
}
}//while
if(!StackEmpty(S))
{
Pop(S,j);
Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步
if(k&&!visited[k])
{
visit(k);
visited[k]=1;
Push(S,k);
}
}//if
}//while
}//Straverse_Nonrecursive
但这个解答明显有问题,如第二个while循环while(Gettop(S,i)&&i)根本就无法结束!
有无高手给个正解先?谢谢啦:)
//又改了一遍,如有问题一起讨论
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //将第一个顶点入栈
visit(1);
visited =1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
for(j=FirstAdjVex(G,i);j&&visited[j];j=Nextadjvex(G,i,j));
if(!j) //邻接结点全部都访问过了
break;
visit(j);
visited[j]=1;
push(S,j);
}//while
Pop(S,j); //把该结点出栈
while(!StackEmpty(S))
{
Gettop(S,i);
for(j=Firstadjvex(G,i);j&&visited[j];j=Nextadjvex(G,i,j));
/*找与该结点邻接的未访问过的结点*/
if(j) /*找到了*/
{
push(S,j);
break;
}
else /*未找到*/
{
pop(S,j);
}
}//while
}//while
}//Straverse_Nonrecursive