获取图中最长的路径

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

我在寻找最长的路径上遇到了困难，下一步该如何进行这个程序，请在这里帮助我。

- learner

---

循环路径是否被允许？例如，2和4可以相连，创建一个圆形路径“0 -> 6 -> 4 -> 2 -> 0”吗？ - Andreas

@Andreas，节点不是双向的，因此在我的情况下不允许循环。 - learner

1. 我认为你的意思是边缘不是双向(无向)的。
2. 从你的问题中没有任何迹象表明你的图是有向的。实际上，根据箭头未指定方向的情况，该图像实际上表明了一个无向图。
3. 即使有定向边，也可以定义一个圆形路线，所以你并没有真正回答我的问题。

- Andreas

简短的澄清问题，您是否真的需要解决图形的问题？还是您的问题仅限于树（如您的示例所示）？从您关于方向的评论中，我了解到可能不会有从每个节点到每个其他节点的路径。您还说循环路径不可能。这是否限制了要找到的路径，还是它是您的图形形成的基本约束？ - second

@second，我对图形和树结构的知识不是很了解，因此无法发表评论。从起点 0 开始，我可以前往其他节点 1,2,3,4,5,6,7,8,9。 - learner

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

- Lyn

---

我不确定这是否正确。问题在于可能有多条通往节点的路径 - 一些通过奇数节点，一些则更短而没有经过奇数节点。如果存在从该中间节点通过奇数节点的外向长路径，并且您首先通过奇数节点路径访问了中间节点，则似乎会错过该路径。一个解决方案是将访问视为节点和oddNumCodeCnt的一对。 - Hans Olsson

这不会错过您提到的情况。遍历仅在命中第二个奇数节点时停止。回溯技术确保您将探索两种情况。如果此中间节点本身是奇数编号，则已经具有另一个奇数编号节点的路径在此结束。如果此中间节点本身是偶数编号，则算法将继续探索其未访问的邻居。 - Lyn

Answer 2

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

1. starting from 0 the program generate linked lists of neighbors. In our case:

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

2. checking neighbors (last elements in lists): if they are odd then increment a counter that refer to that path list. If the odd counter ==2 then erase that list from further analsys

3. for each list start again from 1. using last element as input. When no more VALID lists can be generated find the one with longest path, counting elements.

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

- Zartof

---

我也有同样的想法，但是我卡在了如何在我的程序中实现它上。 - learner

你应该开始创建一个链表的列表，这样你就可以轻松地添加和删除元素（链表）。所以只需将节点起始点推入链表即可。为了简化一切，Node类应该有一个邻居列表，其中包含邻居节点。使用这个方法，步骤1不应该太难。同样，步骤2的检查也不应该太难。作为停止步骤3循环的条件，你可以使用像“直到在每个列表中最后一个节点的唯一邻居是前一个节点”这样的验证，或者换句话说，“直到达到的节点是叶子节点”。 - Zartof

Answer 3

这是C++的代码，但我认为它的工作方式相同：

#include <vector>

using namespace std;
void dfs(vector<vector<int>> &graphs, int nextidx, int& ticket, int& cities);

int solution(vector<int>& T)
{
    if (T.empty()) return 0;

    vector<vector<int>> graphs(T.size());

    int ticket = 1;
    int citiesmax = 0;
    for (int i = 1; i < T.size(); ++i) {
        graphs[T[i]].emplace_back(i);
    }

    //    0-> 2, 6, 9
    //    1-> _
    //    2-> 3
    //    3-> 8
    //    4-> _
    //    5-> _
    //    6-> 4
    //    7-> _
    //    8-> 5, 7
    //    9-> 1

    
    for (int i = 0; i < graphs[0].size(); ++i)
    {
        int nextidx = graphs[0][i];
        int cities = 1;
        dfs(graphs, nextidx, ticket, cities);
        if(cities > citiesmax)
        {
            citiesmax = cities;
        }
    }
    
    return citiesmax;

}

void dfs(vector<vector<int>> &graphs, int nextidx, int &ticket, int& cities)
{
    if (graphs[nextidx].empty()) return;


    for (int i = 0; i < graphs[nextidx].size(); ++i)
    {
        if (graphs[nextidx][i] % 2 > 0)
        {
            if (ticket == 0) return;
            ticket--;       
        }
        int idx = graphs[nextidx][i];
        cities++;
        dfs(graphs, idx, ticket, cities);
    }
    return;
}


int main()
{
    vector<int> test1 = {0,9,0,2,6,8,0,8,3,0};


    int res = solution(test1);
    
}

- ineedhelp

Answer 4

您可以尝试下面的方法，实现起来应该相对简单且易于跟踪。首先，您需要形成一个Node类，其中包含有关三个事项的信息：

1. 从节点 0 开始访问每个节点一次，到达此节点时已经访问过的所有节点路径的最大长度。
2. 一个名为 oddCounter 的变量，用于计算迄今为止在这条路径上遇到的奇数节点数。
3. 一个布尔变量 isVisited ，用于知道该节点是否已被访问。

现在只需使用上述类型的类的实例作为节点实现BFS，并在执行BFS时相应地更新每个节点变量即可。

请注意，您需要从节点 0 开始对所有节点执行BFS，每次重置上述3个变量的值，以便您可以通过此节点跟踪更远的路径。如果已经找到一个奇数节点，那么您可以终止超出某些节点的循环。这样，在未来，当您可能想要将 2 或 3 个奇数编号的节点包括在路径中时，它会更加灵活。

此外，您需要创建一个resultList和currList，每当遍历到一个新节点时就创建一个新的currList，如果currList的长度大于我们所拥有的约束条件下的resultList的长度，则使用currList更新resultList。

我相信这种方法可以进一步优化，使用动态规划。由于您知道从给定节点到达某个节点的路径长度和奇数节点的数量，现在只需从ith节点开始进行BFS，并使用memoization来跟踪先前的路径长度和奇数编号节点，这些信息我们已经使用上面创建的类进行了跟踪。

- CodeHunter