【图的深度优先遍历】

前言

深度优先遍历简称DFS，主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

使用递归实现深度优先遍历算法代码实现

public class DataFlowGraph {
   private static final String NODE_PROPERTY="nodeProperty";
   private static final String EDGE_LABLE="link";
   /**
    * 图
    */
   private Graph graph =null;
   /**
    * 图遍历临时栈
    */
   private Stack<String> stack = new Stack<String>();
   /**
    * 起点开始的所有路径
    */
   private Map<String,List<List<String>>> allPathMap=new HashMap<>();
   public DataFlowGraph (String flow) {
      JSONObject jsonObj= JSONObject.parseObject(flow);
      generateGraph(jsonObj);
   }
   public FlowGraph(JSONObject flowJson) {
      generateGraph(flowJson);
   }
   /**
    * 遍历DAG图中所有路径
    * @param id
    * @throws Exception 
    */
   public void findPathByStart(String id) throws Exception {
      stack.push(id);
      boolean bl=cyclicCheck(stack);
      if(bl) {
         throw new Exception("图存在环路");
      }
      Vertex vertex=graph.getVertex(id);
      Iterable<Vertex>  outVertexs=vertex.getVertices(Direction.OUT);
       int len=count(outVertexs);
      if(len>0) {          
         for(Vertex node:outVertexs) {
            findPathByStart(node.getId().toString());        
         }
         stack.pop();   
      }else {
         addToPath(stack);
         if(!stack.isEmpty()) {
            stack.pop();
         }
         return;
      }
      
   }

   /**
    * 检查是否存在环路 
    * @param pathStack
    * @return true 存在 false 不存在
    */
   private boolean cyclicCheck(Stack<String> pathStack) {
      HashSet<String> set = new HashSet<>();
      set.addAll(pathStack);
      int setSize=set.size();
      int stackSize=pathStack.size();
      if(stackSize>setSize) {
         return true;
      }else {
         return false;
      }
   }
   /**
    * 将pathStack转换为list，
    * @param pathStack
    */
   private void addToPath(Stack<String> pathStack) {
      List<String> singlePath=new ArrayList<String>();
      singlePath.addAll(pathStack);
      String startId=singlePath.get(0);
      List<List<String>> pathList=allPathMap.get(startId);
      if(pathList==null) {
         pathList=new ArrayList<List<String>>();
         allPathMap.put(startId, pathList);
      }
      pathList.add(singlePath);
   }
   /**
    * 根据节点id获取其属性
    * @param nodeId
    * @return
    */
   public JSONObject getNode(String nodeId) {
      Vertex vertex=graph.getVertex(nodeId);
      if(vertex!=null) {
         return (JSONObject)vertex.getProperty(NODE_PROPERTY);
      }else {
         return null;
      }
   }
   /**
    * 获取下一步所有节点
    * @param nodeId
    * @return
    */
   public JSONArray getNextNode(String nodeId) {
      JSONArray array=null;
      Iterable<Edge> ie=graph.getVertex(nodeId).getEdges(Direction.OUT);
      for(Edge edge:ie) {
         Vertex vertex=edge.getVertex(Direction.OUT);
         if(array==null) {
            array=new JSONArray();
         }
         array.add(vertex.getProperty(NODE_PROPERTY));
      }
      return array;
   }
   /**
    * 获取所有起始节点
    * @return
    */
   public List<String> getStartNodes() {
      List<String> starts=new ArrayList<String>();
       Iterable<Vertex> iterator=graph.getVertices();
        for(Vertex tmpv:iterator) {
           Iterable<Edge> edges=tmpv.getEdges(Direction.IN, EDGE_LABLE);
           int count=count(edges);
           if(count==0) {
              starts.add(tmpv.getId().toString());
           }
        }
        return starts;
   }
   
   /**
    * 通过json串生成图
    * @param flowJson
    */
   private void generateGraph(JSONObject flowJson) {
      graph = new TinkerGraph();
      //构建Vertex
      JSONArray nodes=flowJson.getJSONArray("nodes");
      Map<String,Vertex> nodeMap=new HashMap<String,Vertex>();
      int len=nodes.size();
      for(int i=0;i<len;i++) {
         JSONObject node=nodes.getJSONObject(i);
         String id=node.getString("id");
         
         Vertex vertex = GraphHelper.addVertex(graph, id, NODE_PROPERTY, node);
         nodeMap.put(id, vertex);
      }
      //构建Edge
      JSONArray links=flowJson.getJSONArray(JsonContant.DAG_LINKS);
      Map<String,JSONObject> linkMap=new HashMap<String,JSONObject>();
      len=links.size();
      for(int i=0;i<len;i++) {
         JSONObject link=links.getJSONObject(i);
         String id=link.getString(JsonContant.DAG_LINKS_ID);
         String fromId=link.getString(JsonContant.DAG_LINKS_FROM);
         String toId=link.getString(JsonContant.DAG_LINKS_TO);
         linkMap.put(id, link);
         Vertex vertexFrom=nodeMap.get(fromId);
         Vertex vertexTo=nodeMap.get(toId);
         GraphHelper.addEdge(graph,id, vertexFrom, vertexTo,"link" ,"name", "edge"+i);
      }

   }

   public List<List<String>> getAllPath(String startId) {
      return allPathMap.get(startId);
   } 
}