时间戳

首页 > 解决方案 > DFS（深度优先搜索）节点序列

java - DFS（深度优先搜索）节点序列

问题描述

long我想为Java类型的节点实现 dfs 。

我的算法正确计算了节点的数量和数量

边的数量，但不是节点的序列。请你帮助我好吗

修改我的算法，以便我计算节点的顺序

访问过，对吗？

这是我的代码：

private int getNumberOfNodes(long firstNode) {  
    List<Long> marked = new ArrayList<>();  //------------------------------------------->
    Stack<Long> stack = new Stack<Long>();  //step 1  Create/declare stack
    stack.push(firstNode);                  //Step 2 Put/push inside the first node
    while (!stack.isEmpty()) {              //Repeat till stack is empty:
       Long node = stack.pop();             //Step 3 Extract the top node in the stack
       marked.add(node);                    //------------------------------------------->
       long[] neighbors = xgraph.getNeighborsOf(node); //Get neighbors
       if (neighbors.length % 2 == 0) {
           
       } else {
           numOfNodesWithOddDegree++;
       }
       int mnt = 0;
       for (long currentNode : neighbors) {
           if (!marked.contains(currentNode) && !stack.contains(currentNode) ) { //&& !stack.contains(currentNode)  
               stack.push(currentNode);

           } else {
               
           }
           if (!marked.contains(currentNode)) {
               numOfEdges++;
           }
       }
    }
    return marked.size(); //(int) Arrays.stream(neighbors).count();
}

标签： javaalgorithmgraphdepth-first-searchgraph-traversal

解决方案

我猜你检查marked了序列的列表。

由于您的图是无向的，遍历的顺序可能会根据您首先推入堆栈的邻居而有所不同。这意味着您的功能的逻辑：

 xgraph.getNeighborsOf(node)

可能会影响您的顺序。请参阅此 wiki 的顶点排序https://en.wikipedia.org/wiki/Depth-first_search

所以我的结论是：你可能有不同的遍历顺序，这并不意味着你的DFS是错误的，只要是Deep first search，与给定的答案稍有不同是可以的。

推荐阅读