depth-first-search - Perl 中的 DFS(或 Java 或 C++ ...)

Question

我在 3D 计算机图形学方面做过一些工作，但对图形有些陌生理论。特别是我一直在寻找并尝试使用深度优先搜索 (DFS)，如 Mastering Algors w/Perl (Jarkko埃塔涅米)。到目前为止我还没能得到它:-(但我很确定 DFS是我想要的。

它不必使用 Perl(只是想学习这门语言)，但 Java 或 C++ 会很好。

我有 53 个位置向量，即 (x,y,z)，我表示为

(x1,y1,z1)
(x2,y2,z2)
.
.
.
(x53,y53,z53)

然后我运行我编写的 Perl 程序来生成随机链接节点，分配一些最大值。跳数，比如 6。所以拓扑可能看起来像这个

5                               <-- node 1 has 5 links to
  18 4 23 6 48,                 <--  node 18, node 4, node 23, node 6, node 48
2                               <-- node 2 has 2 links to
  14 5,                         <--  node 14, node 5
0                               <-- node 3 is a leaf since it has no links
.
.
.
2                               <-- node 18 has 2 links to
  3 17                          <--  node 3, node 17  
.
.
.
4                               <-- node 53 has 4 links to
  10 46 49 22                   <--  node 10, node 46, node 49, node 22

我想确定“运行”的路径，直到我碰到一个水槽，即 0。例如节点 1 到节点18 到节点 3，...这条路已经走完了。...

我想我想要DFS；这似乎是一个递归练习。

如果有人理解并可以给我代码，那就太好了。我不是学生，而是 51 岁!也许这与我没有得到这个有关 :-)

---

我看了看我的 q，出于某种原因(可能是我 :-( 它是“乱码”

拓扑应该是这样的5 <-- 节点 1 有 5 个链接； 18 4 23 6 48 <-- 节点 18、节点 4、节点 23、节点 6、节点 482 <-- 节点 2 有 2 个链接； 14 5, <-- 节点 14, 节点 50 <-- 节点 3 是一片叶子，因为它没有链接...2 <-- 节点 18 有 2 个链接； 3 17 <-- 节点 3，节点 17...4 <-- 节点 53 有 4 个链接； 10 46 49 22 <-- 节点 10、节点 46、节点 49、节点 22

只是想说清楚，以防有人可以提供代码(Perl、Java、c++/C ...)

谢谢。

Answer 1

深度优先搜索的思想是先为您的查询搜索尽可能“深”的内容，然后再遍历整个序列。这很容易从数据树的角度来思考:

搜索将从节点 1 -> 53 开始，搜索顺序为1 -> 18 -> 3 -> 17 -> 4 -> 23 -> 6 -> 48 -> 2 -> 5 -> 14 ....

它转到节点 1，查看它的第一个链接:节点 18，然后是节点 18 的第一个链接节点 3，找到一个没有链接的节点。然后返回以相同的深度级别搜索到节点 17 等。在您的情况下，您只需要到此为止。

下面是Java的完整解决方案，抱歉我不熟悉perl所以我把伪代码逻辑写出来了。

除了存在可能导致无限循环的循环链接的情况外，问题相当简单，因此我添加了一个以前访问过的节点列表并对此进行检查以避免冗余或无限搜索。

depthFirstSearch(node) { // call to search a node
    result = depthFirstSearch(node, empty list for previously searched list);
    if (the result is null) {
        print "No leaf node found"
    } else {
        "Found: " + result info
    }
    return result;          
}
depthFirstSearch(node, previouslySearchedList) { // method with a list of previously visited nodes
    // if the node is null, return null
    // add the node to the list of searched nodes
    if (// the node has 0 links) {
        // we have found a leaf, return it.
    } else {
        for (each of the links the current node has) {
            for (each of the previously searched links) { 
                if (the current node has been searched) {
                    set a null return value
                    break the loop
                } else {
                        set the return value to this node
                }
            }
            // recursively search the next node, passing the previously searched list along
            last_node = depthFirstSearch(next,previouslySearchedList);
            if (the last recursive call returned a null value move on to the next child) {
                break the loop
            }
        }
        return the last node found // could be a null, could be a result.
    }
}

这是一个完整的工作解决方案:

class Node {
    int default_size = 10;
    ArrayList<Node> links = new ArrayList<Node>();
    int numberOfLinks = 0;
    int x, y, z, index;
    public Node(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
        this.index = -1;
    }
    public Node(int x, int y, int z, int index) {
        this.x = x;
        this.y = y;
        this.z = z;
        this.index = index; 
    }
    public void addNodeLink(Node node) {
        this.links.add(node);
    }
    public int getIndex() {
        return this.index;
    }
    public int getNumberOfLinks() {
        return links.size();
    }
    public ArrayList<Node> getLinks() {
        return this.links;
    }
    public String getInfo() {
        String info = "";
        if (index < 0) {
            info += "Unindexed node ";
        } else {
            info += "Node " + index + " ";
        }
        info += "with " + this.getNumberOfLinks() + " links\n  ";
        for (int i = 0; i < this.getNumberOfLinks(); i++) {
            info += this.getLinks().get(i).getIndex() + " ";
        }
        return info;
    }
    public String toString() {
        return getInfo();
    }
    public static Node depthFirstSearch(Node node) {
        Node result = depthFirstSearch(node, new ArrayList<Node>());
        if (result == null) {
            System.out.println("\nNo leaf node found");
        } else {
            System.out.println("\nFound: " + result);
        }
        return result;          
    }
    public static Node depthFirstSearch(Node node, ArrayList<Node> searchList) {
        if (node == null) { return null; }
        searchList.add(node);
        if (node.getNumberOfLinks() == 0) {
            System.out.println(" -> Node " + node.getIndex());
            return node;
        } else {
            System.out.print((searchList.size() > 1 ? " -> " : "Path: ") + "Node " + node.getIndex());
            Node last_node = null, next = null;
            int i, j;
            for (i = 0; i < node.getNumberOfLinks(); i++) {
                for (j = 0; j < searchList.size(); j++) { 
                    if (node.getLinks().get(i).getIndex() == searchList.get(i).getIndex()) {
                        next = null;
                        break;
                   } else {
                        next = node.getLinks().get(i);
                   }
                }
                last_node = depthFirstSearch(next,searchList);
                if (last_node != null) {
                    break;
                }
            }
            return last_node;
        }
    }
    public static void main(String[] args) {
        Node[] graph = new Node[53];

        // set up your nodes
        int randomNum = 0 + (int)(Math.random()*100); 
        for (int i = 0; i < graph.length; i++) {
            randomNum = 0 + (int)(Math.random()*100);
            graph[i] = new Node(randomNum,randomNum,randomNum,i+1);
        }

        System.out.println("Example given in question");

        // Example given in question
        graph[0].addNodeLink(graph[17]);
        graph[0].addNodeLink(graph[3]);
        graph[0].addNodeLink(graph[22]);
        graph[0].addNodeLink(graph[5]);
        graph[0].addNodeLink(graph[47]);

        graph[1].addNodeLink(graph[13]);
        graph[1].addNodeLink(graph[4]);

        graph[17].addNodeLink(graph[2]);
        graph[17].addNodeLink(graph[16]);

        graph[52].addNodeLink(graph[9]);
        graph[52].addNodeLink(graph[45]);
        graph[52].addNodeLink(graph[48]);
        graph[52].addNodeLink(graph[21]);

        for (int i = 0; i < graph.length; i++) {
             if (graph[i].getNumberOfLinks() != 0) {
                  System.out.println(graph[i]);
             }
        }

        depthFirstSearch(graph[0]);

        // reset the nodes
        randomNum = 0 + (int)(Math.random()*100); 
        for (int i = 0; i < graph.length; i++) {
            randomNum = 0 + (int)(Math.random()*100);
            graph[i] = new Node(randomNum,((59+3*randomNum)%100),((19+17*randomNum)%100),i+1);
        }



        // circular reference example
        System.out.println();
        System.out.println();
        System.out.println("Circular reference");

        graph[0].addNodeLink(graph[1]);
        graph[1].addNodeLink(graph[2]);
        graph[2].addNodeLink(graph[0]);

        for (int i = 0; i < graph.length; i++) {
             if (graph[i].getNumberOfLinks() != 0) {
                  System.out.println(graph[i]);
             }
        }
        depthFirstSearch(graph[0]);
        System.out.println();
        System.out.println();

        System.out.println("Circular reference, with a leaf node added");

        graph[0].addNodeLink(graph[3]);

        for (int i = 0; i < graph.length; i++) {
             if (graph[i].getNumberOfLinks() != 0) {
                  System.out.println(graph[i]);
             }
        }
        depthFirstSearch(graph[0]);
    }
}