How to traverse through a network of cities connected by roads in java?

I encountered a problem where they say, a network of cities and road connecting them is given as an array of integers. The relationship between the index of the array and value at that index determines how the network looks.

for example a network of cities can be represented by an integer array like this
array = {9,1,4,9,0,4,8,9,0,1}

in this example array[0] = 9 means there is a link between city 0 and city 9 by a connecting road of 1.

what data structure or algorithm can I use to store this information so that i can answer questions like

how many cities are connected by road of length 1 or 2 or 3 or.....
or
what is maximum number of cities I can cover before I encounter a city with odd number.

Linear thinking is not getting me anywhere.

Main Condition is no two cities have more than one path. So its not a close loop.

I can't use binary tree logic because even if we rearrange the network as a tree, we end up with 1 parent and varying number of children.

Can anyone help me solve this ?

Networks like this are called graphs (wikipedia link).

There are a couple different ways you can represent a graph in a computer program, the most common one is the "adjacency list" which basically tells you what are cities you can get to from a given city with just one hop. The adjacency list for the example graph in your question would be:

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

This means: City 0 is connected to cities 9, 4, and 8. City 1 is connected to cities 1 and 9. City 2 is connected to city 4. And so on.

This adjacency list was built with a function like this:

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

> how many cities are connected by road of length 1 or 2 or 3

This question is answered with graph traversal algorithms such as breadth first search and depth first search. The basic idea is, the adjacency list tells you which cities you can get to by taking one road. If you now look at where you can get from those cities, that's where you can get with 2 roads. And so on.

> what is maximum number of cities I can cover before I encounter a city with odd number

You do this by first removing all odd-numbered cities, and then finding the longest path in the resulting network. Finding the longest path in a graph is a known hard problem.

What you need here is a graph.

If you have City class, and this class has a list of linked cities (which should be empty at start), and this class has method link(otherCity) you can add the corresponding city to the respective list.

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

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

You could also provide a city link in the constructor or add a static link(cityA, city) method, depending on your needs.

This is only for the case where all roads are two-way, if you can have one-way relationships, you should two lists (incoming/outgoing connected cities)