java - 获取图形中经过的最长路线

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 的列表变量列表。这将为您提供所有有效的最长路径。我用一张 map 来表示一个图形，但是你可以随意修改它。

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());
        }
    }
}