工大后院

 找回密码
 加入后院

扫一扫,访问微社区

QQ登录

只需一步,快速开始

搜索
查看: 1542|回复: 1

这算法错在哪里?

[复制链接]
发表于 2007-6-14 12:00 | 显示全部楼层 |阅读模式
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));
  
  }  
  
  
  
  
}
           

不知道为什么,测试结果总是只访问图的第一个点。
发表于 2007-6-15 19:29 | 显示全部楼层
太长了,我就不看了。。。
等后来人。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 加入后院

本版积分规则

QQ|Archiver|手机版|小黑屋|广告业务Q|工大后院 ( 粤ICP备10013660号 )

GMT+8, 2025-8-30 22:41

Powered by Discuz! X3.5

Copyright © 2001-2024 Tencent Cloud.

快速回复 返回顶部 返回列表