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、节点 48 2 <--节点2有2条链路； 14 5,<--节点14，节点5 0 <-- 节点 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]);
    }
}