关于套汇问题的构想
lydc吧
全部回复
仅看楼主
level 6
使用临接表存储图,checkrate()函数以深度优先搜索为模板,共有两个重载,公有checkrate(int)函数有一个int型参数,用于定位从哪个节点开始搜索,私有checkrave(int start,bool **visited,int path,int aim)函数中,int型参数start用于传入起始节点,bool型参数二维数组用于记录两个节点之间的路径是否经过,防止路径重复,int型参数path用于记录路径,aim记录总起始点,即公共函数传入的参数
2011年12月21日 06点12分 1
level 6
须知在整个过程中,每次调用私有checkrate()的时候aim值保持不便(亦可定义静态变量代替)。在公有checkrate()函数内初始化path、visited、rate,并通过while循环依次把指定查询的节点的每一个临接节点在主表中的下标作为start调用私有checkrate()函数,私有checkrate()内部对传入的start和rate进行判断,是否满足start等于aim且rate大于1,若满足则输出path、rate并return,否则使用节点指针定位节点并对传入的path、visited、rate进行操作,使用while循环把当前节点的每一个临接节点在主表中的下标作为start值和当前path、visited、rate传入私有checkrate()函数进行递归调用。这样就能找出所有以传入位置节点为出发点的回路,并输出满足条件的回路,以此达到检测套汇路径的目的
2011年12月21日 16点12分 2
level 6
思考:私有checkrate()中的循环内部,每次递归调用自身之前将visited二维数组初始化为传入的原始二维数组,以保证对当前节点的所有临接节点查找的时候不会互相影响
2011年12月21日 16点12分 3
1