3

我在 3D 计算机图形学方面做过一些工作，但对图论有点陌生。特别是，我一直在研究并尝试使用深度优先搜索 (DFS) 来解决我的问题，如 Mastering Algors w/Perl (Jarkko Hietaniemi) 中所述。到目前为止，我还没有得到它:-(但我很确定 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 ...）

谢谢。

4

1 回答 1

0

深度优先搜索的想法是首先为您的查询搜索“深度”，然后在整个火车上移动。就数据树而言，这很容易想到：

图形可视化

搜索将从节点 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]);
    }
}
于 2013-10-28T18:58:30.200 回答