深度优先算法(DFS)遍历有向无环图寻找最优路径

  • V2_941395
    了解作者
  • 10KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-14 12:30
    上传日期
采用深度优先算法(DFS)遍历有向无环图寻找最优路径,经过优化的深度优先算法,在遍历有向无环图的时候保存路径,并计算路径权值,最总返回最优路径及最有路径的权值
DFSFindBestPath.rar
内容介绍
package answer.dfsFindBestPath.traversing; import java.util.List; import answer.dfsFindBestPath.model.GraphEdge; import answer.dfsFindBestPath.model.GraphNode; /** * 采用深度优先算法获取最佳路径 * @author wilWang * @Date 2017-11-23 */ public class DFSGetBestPath { private int tempWeight = 0; int maxWeight = 0; String result = ""; private StringBuffer wsb = new StringBuffer(); private StringBuffer lsb = new StringBuffer(); public String getResult() { return result; } /** * 采用深度优先算法递归遍历有向无环图 * @param node * @param visited * @return */ public GraphNode searchTraversing(GraphNode node, List<GraphNode> visited) { // 如果已经查看过该节点,返回该节点 if (visited.contains(node)) { return node; } visited.add(node); //添加节点示例 if(lsb.length() > 0){ lsb.append("->"); } lsb.append(node.getLabel()); // System.out.println("节点:" + node.getLabel()); if(node.edgeList.size() > 0){ for (int i = 0; i < node.edgeList.size(); i++) { GraphEdge gEdge = node.edgeList.get(i); int weight = gEdge.getWeight(); //计算当前路径权重 tempWeight += weight; //添加权重示例 if(wsb.length() > 0){ wsb.append("+"); } wsb.append(weight); GraphNode nextNode = searchTraversing(gEdge.getNodeRight(), visited); if(nextNode.getLabel() != null && nextNode.getLabel() != ""){ //减去退出路径的权重 tempWeight -= weight; //删除退出路径的权重示例 if(wsb.length() <= 1){ wsb.delete(wsb.length()-1, wsb.length()); }else{ wsb.delete(wsb.length()-2, wsb.length()); } //删除退出路径的节点示例 if(lsb.length() <= 1){ lsb.delete(lsb.length()-1, lsb.length()); }else{ lsb.delete(lsb.length()-3, lsb.length()); } } //删除当前节点,为遍历其他路径上的节点做准备 visited.remove(nextNode); } }else{ if(maxWeight < tempWeight){ maxWeight = tempWeight;//更细最大权重 //更新最有路径结果 result = maxWeight+"(最优路径是:"+lsb.toString()+"权重之和是:"+wsb.toString()+"="+maxWeight+")"; } } return node; } }
评论
    相关推荐