获取图中行驶的最长路线

Question

我有一个相互连接的节点数组

我有下面的节点网络。这里以0为起点，我想尽可能多地移动节点，而一个节点仅移动一次。同样，在从0到目标节点的行程中，我只希望有一个奇数编号的节点（例如1、3、5、7）。现在，我需要找出从起始位置0开始可以走的最长路线。

范例：

int[] array = { 0, 9, 0, 2, 6, 8, 0, 8, 3, 0 };

在上图中，以下是可能性：

0 -> 6 -> 4 (valid path, length = 3 nodes)
0 -> 9 -> 1 (Not valid path, length as we have 2 odd numbers here 1 & 9)
0 -> 2 -> 3 -> 8 (valid path, length = 4 nodes)
0 -> 2 -> 3 -> 8 -> 5 (Not valid path as we have 2 odd numbers here 3 & 5)
0 -> 2 -> 3 -> 8 -> 7 (Not valid path as we have 2 odd numbers here 3 & 7)

So the answer is 4 for this input.

下面是我正在尝试的程序。

public int process(int[] array) {
    int count = array.length;
    ArrayList<Integer>[] branches = new ArrayList[count];
    for (int i = 0; i < count; i++) {
        branches[i] = new ArrayList<>();
    }
    int begin = 0;

    for (int i = 0; i < count; i++) {
        if (array[i] != i) {
            branches[i].add(array[i]);
            branches[array[i]].add(i);
        }
    }

    Arrays.stream(branches).forEach(System.out::println);

    Queue<Network> networkQueue = new LinkedList<Network>();
    ArrayList<Integer> networkList = branches[begin];
    networkList.forEach(value -> {
        Network net = new Network(0, value);
        networkQueue.add(net);
    });

    System.out.println("printing starting nodes.......");
    List<Network> nodes = new ArrayList<>();
    for (Network n : networkQueue) {
        nodes.add(n);
        System.out.println(n.value + " : " + n.road);
    }

    int result = 0;
    return result;
}

class Network {
    int road, value;

    public Network(int road, int value) {
        this.road = road;
        this.value= value;
    }

}

程序打印起点的分支和节点，即0：

[2, 6, 9]
[9]
[0, 3]
[2, 8]
[6]
[8]
[4, 0]
[8]
[5, 7, 3]
[1, 0]
printing starting nodes.......
2 : 0
6 : 0
9 : 0

我被困在寻找最长的路线上，接下来如何继续执行该程序，请在这里帮助我。

Answer 1

这是一个经典的“深度优先搜索”，带有回溯问题。

该算法的要点如下。从起始节点开始，访问其尚未访问的所有邻居，并且不破坏1个限制的最大奇数节点。将当前节点添加到当前路径，如果当前节点号为奇数，则增加奇数节点计数器。递归执行此操作，直到用尽了一个邻居的所有有效路径，然后回退其余邻居的路径。

以下是使用您提供的输入作为测试用例的实现。我还添加了另一个名为res的列表变量列表。这将为您提供所有有效的最长路径。我使用地图来表示图形，但是您可以根据需要进行修改。

import java.util.*;

public class LongestRoute {
    private static int maxLen = 0;
    private static List<List<Integer>> res = new ArrayList<>();

    public static int longestRouteWithRestrictions(Map<Integer, List<Integer>> graph, int startNode) {
        Set<Integer> visited = new HashSet<>();
        visited.add(startNode);
        List<Integer> path = new ArrayList<>();
        path.add(startNode);

        dfs(graph, startNode, visited, startNode % 2 == 1 ? 1 : 0, path);
        return maxLen;
    }

    private static void dfs(Map<Integer, List<Integer>> graph, int currentNode, Set<Integer> visited, int oddNumNodeCnt, List<Integer> path) {
        if(path.size() > maxLen) {
            maxLen = path.size();
            res.clear();
            res.add(new ArrayList<>(path));
        }
        else if(path.size() == maxLen) {
            res.add(new ArrayList<>(path));
        }
        for(int neighbor : graph.get(currentNode)) {
            if(visited.contains(neighbor) || oddNumNodeCnt == 1 && neighbor % 2 != 0) {
                continue;
            }
            path.add(neighbor);
            visited.add(neighbor);
            dfs(graph, neighbor, visited, oddNumNodeCnt + (neighbor % 2 != 0 ? 1 : 0), path);
            path.remove(path.size() - 1);
            visited.remove(neighbor);
        }
    }
    public static void main(String[] args) {
        //Init a test graph
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Integer[] neighbors_0 = {2,6,9};
        List<Integer> list0 = Arrays.asList(neighbors_0);
        graph.put(0, list0);

        Integer[] neighbors_1 = {9};
        List<Integer> list1 = Arrays.asList(neighbors_1);
        graph.put(1, list1);

        Integer[] neighbors_2 = {0,3};
        List<Integer> list2 = Arrays.asList(neighbors_2);
        graph.put(2, list2);

        Integer[] neighbors_3 = {2,8};
        List<Integer> list3 = Arrays.asList(neighbors_3);
        graph.put(3, list3);

        Integer[] neighbors_4 = {6};
        List<Integer> list4 = Arrays.asList(neighbors_4);
        graph.put(4, list4);

        Integer[] neighbors_5 = {8};
        List<Integer> list5 = Arrays.asList(neighbors_5);
        graph.put(5, list5);

        Integer[] neighbors_6 = {0,4};
        List<Integer> list6 = Arrays.asList(neighbors_6);
        graph.put(6, list6);

        Integer[] neighbors_7 = {8};
        List<Integer> list7 = Arrays.asList(neighbors_7);
        graph.put(7, list7);

        Integer[] neighbors_8 = {5,7};
        List<Integer> list8 = Arrays.asList(neighbors_8);
        graph.put(8, list8);

        Integer[] neighbors_9 = {0,1};
        List<Integer> list9 = Arrays.asList(neighbors_9);
        graph.put(9, list9);

        System.out.println(longestRouteWithRestrictions(graph, 0));
        for(List<Integer> route : res) {
            System.out.println(route.toString());
        }
    }
}

Answer 2

很抱歉我没有时间编写它，但这是我要应用的逻辑。

1. 从 0 开始，程序生成邻居的链表。在我们的例子中：

   [0->2]
   [0->9]
   [0->6]
   

2. 检查邻居（列表中的最后一个元素）：如果它们是奇数，则增加引用该路径列表的计数器。如果奇数计数器 ==2 则从进一步的分析中删除该列表

3. 对于每个列表，都从 1. 使用最后一个元素作为输入重新开始。当无法生成更多有效列表时，找到具有最长路径的列表，计算元素数。

请注意，有效的邻居不能与列表中的前一个元素相同，以避免无限循环：唯一可以由[0->2]it生成的有效列表[0->2->3]是 ，而不是[0->2->0]