|
7.24③ 试利用栈的基本操作编写,按深度优先搜索策略
遍历一个强连通图的非递归形式的算法。算法中不规定具
体的存储结构,而将图Graph看成是一种抽象的数据类型。
实现下列函数:
void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType));
/* Travel the digraph 'dig' with Depth_First Search. */
图以及相关类型、函数和辅助变量定义如下:
Status visited[MAX_VERTEX_NUM];
int LocateVex(Graph g, VertexType v);
VertexType GetVex(Graph g, int i);
int FirstAdjVex(Graph g, int v);
int NextAdjVex(Graph g, int v, int w);
void visit(char v);
Status InitStack(SStack &s);
Status Push(SStack &s, SElemType x);
Status Pop(SStack &s, SElemType &x);
Status StackEmpty(SStack s);
Status GetTop(SStack s, SElemType &e);
我的代码是:
void Traverse(Graph dig, VertexType v0, void (*visit)(VertexType))
/* Travel the digraph 'dig' with Depth_First Search. */
{
int num;
SStack s;
VertexType v,v1;
visit(v0);
Push(s,v0);
visited[LocateVex(dig,v0)]=TRUE;
v=GetVex(dig,LocateVex(dig,v0));
while(!StackEmpty(s))
{ if(!FirstAdjVex(dig,v))
{Pop(s,v1);
if(!StackEmpty(s))
GetTop(s,v);
else return;
}
else
v1=GetVex(dig,LocateVex(dig,FirstAdjVex(dig,v)));
num=LocateVex(dig,v1);
while(visited[num])
{if(NextAdjVex(dig,v,v1))
{v1=GetVex(dig,LocateVex(dig,NextAdjVex(dig,v,v1)));
num=LocateVex(dig,v1);}
else
{Pop(s,v1);
if(!StackEmpty(s))
GetTop(s,v);
else return;
num=LocateVex(dig,v1);
}
}
visit(v1);
Push(s,v1);
visited[LocateVex(dig,v1)]=TRUE;
v=GetVex(dig,LocateVex(dig,v1));
}
}
不知道为什么,测试结果总是只访问图的第一个点。 |
|