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

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; } }