DFS в Perl (или Java или C ++ ...)

Question

Я сделал кое-что в компьютерной 3D-графике, но я немного новичок в теории графов.В частности, я искал и пытался решить мою проблему, используя поиск в глубину (DFS), как описано в «Освоении Алгора с 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 423 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 * ​​1020 * <p>Просто хочу прояснить ситуацию, если кто-то может предоставить код (Perl, Java, c ++ / C ...)

Спасибо.

Answer 1

Идея глубокого поиска вначале состоит в том, чтобы сначала найти «глубокий» запрос, а затем перейти через поезд. Это легко представить в терминах дерева данных:

Поиск будет идти от узлов 1 -> 53, порядок поиска будет 1 -> 18 -> 3 -> 17 -> 4 -> 23 -> 6 -> 48 -> 2 -> 5 -> 14 ....

Идет к Узлу 1, просматривает свою первую ссылку: узел 18, затем первый узел 3 узла 18, попадает на узел без ссылки. Затем возвращается к поиску на том же уровне глубины до узла 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]);
    }
}