如何在java中穿越由道路连接的城市网络？

Question

我遇到一个问题，他们说，连接城市和道路的网络是以整数数组的形式给出的。数组的索引和该索引处的值之间的关系决定了网络的外观。

例如，城市网络可以用整数数组表示，如数组= {9,1,4,9,0,4,8,9,0,1}

在本例中，array =9表示城市0和城市9之间有一个连接道路1。

我可以使用什么数据结构或算法来存储这些信息，这样我就可以回答如下问题

有多少城市是由长度为1、2、3或.的道路连接起来的。或者在我遇到奇数城市之前，我可以覆盖的最大城市数是多少。

线性思维不会给我带来任何好处。

主要条件是没有两个城市有超过一条路径。所以这不是一个闭合循环。

我不能使用二叉树逻辑，因为即使我们将网络重新排列为一棵树，我们最终也会得到一个父节点和不同数量的子节点。

有人能帮我解决这个问题吗？

Answer 1

这里你需要的是一个图表。

如果你有City类，并且这个类有一个链接的城市列表(在开始时应该是空的)，并且这个类有方法链接(OtherCity)，你可以将相应的城市添加到相应的列表中。

// Pseudo code
class City
 List<City> links;

 void link( City otherCity)
   if (! links.contains( otherCity ) )  
     links.add( otherCity )
   otherCity.add( this )

您还可以在构造函数中提供城市链接或添加静态链接(cityA，城市)方法，具体取决于您的需要。

这只适用于所有道路都是双向的情况，如果你可以有单向关系，你应该有两个列表(传入/传出连接的城市)

Answer 2

这样的网络被称为graphs (wikipedia link)。

有几种不同的方法可以在计算机程序中表示图，最常见的一种是“邻接表”，它基本上告诉你只需一跳就可以从给定的城市到达哪些城市。您问题中的示例图的邻接列表为：

[[9, 4, 8], [1, 9], [4], [9], [2, 0, 5], [4], [8], [9], [6, 0], [0, 3, 7, 1]]

这意味着:城市0连接到城市9、4和8。城市1连接到城市1和9。城市2连接到城市4。以此类推。

此邻接表是使用如下函数构建的：

int[][] adjacencyList(int[] network) {
    int[][] adjacency = new int[network.length][network.length];
    int[] neighborCount = new int[network.length];

    for (int i = 0; i < network.length; i++) {
        if (i == network[i]) {
            adjacency[i][neighborCount[i]++] = i;
        } else {
            adjacency[i][neighborCount[i]++] = network[i];
            adjacency[network[i]][neighborCount[network[i]]++] = i;
        }
    }

    for (int i = 0; i < network.length; i++) {
        adjacency[i] = Arrays.copyOf(adjacency[i], neighborCount[i]);
    }

    return adjacency;
}

长度为1、2或3的道路连接了多少个城市

这个问题可以用breadth first search和depth first search等graph traversal algorithms来回答。基本思想是，邻接表告诉你走一条路可以到达哪些城市。如果你现在看看你可以从这些城市得到什么，那就是你可以用2条道路到达的地方。诸若此类。

在遇到奇数城市之前，我可以覆盖的最大城市数是多少

为此，首先删除所有奇数城市，然后在生成的网络中找到最长路径。查找longest path in a graph是一个众所周知的难题。