How to cover the maximum number of nodes for a given path in a graph?

Question

I am trying to figure out the maximum number of nodes covered by the path in a given graph. I made a program using recursion, but it gives an answer only for some simple graph, not on a complex graph.

Input is specified in a string array such as 1 # 2: means that node 1 is connected to node 2 or vice versa.

I made a matrix from the total size of the nodes, and if node is connected, set 1 else -1 in the matrix. This matrix is ​​used to calculate the maximum node coverage in the path.

the code:

import java.io.*; import java.util.*; public class Medium { public static int node_covered; public static int big=0; public static boolean[] visited; public static int matrix_length; public static String[][] matrix; public static String[] input=new String[] //answer is 7. {"1#2", "2#3","3#4","3#5","5#6","5#7","6#7","7#8"}; public static void main(String[] args){ int total_nodes=maxno_city(input); System.out.println(total_nodes); } public static int maxno_city(String[] input1) { int ln=input1.length; HashSet hs = new HashSet(); for(int i=0; i<ln;i++) { String[] temp=input1[i].split("#"); hs.add(temp[0]); hs.add(temp[1]); } matrix_length=hs.size(); hs.clear(); matrix=new String[matrix_length][matrix_length]; //initialize matrix for (String[] row : matrix) Arrays.fill(row, "-1"); //System.out.println(Arrays.deepToString(matrix)); for(int i=0;i<matrix_length;i++) { for(int j=0; j<matrix_length;j++) { String[] temp=input1[i].split("#"); int first=Integer.parseInt(temp[0])-1; int second=Integer.parseInt(temp[1])-1; matrix[first][second]="1"; matrix[second][first]="1"; } } //System.out.println(Arrays.deepToString(matrix)); //initialized //now start work on matrix for(int i=0;i<matrix_length;i++) { for(int j=0; j<matrix_length;j++) { visited=new boolean[matrix_length]; if(matrix[i][j].equals("1")) { node_covered=0; getNextPath(j,i); //visited[i]=true; } } } return big; } //recursive method public static void getNextPath(int path,int visited_node) { boolean flag=false; visited[visited_node]=true; node_covered++; for(int i=0;i<matrix_length;i++) { if(matrix[path][i].equals("1") && visited[i]==false) { //visited[i]=true; flag=true; getNextPath(i,path); //visited[i]=false; } } if(flag==false) { if(big<node_covered) { big=node_covered; //System.out.println(big); } } else { node_covered--; } //visited[path]=false; } } 

Where am I mistaken in the above code?

Answer 1

The main problem is that you are not storing the full matrix. This loop:

 for(int i=0;i<matrix_length;i++) { for(int j=0; j<matrix_length;j++) { String[] temp=input1[i].split("#"); int first=Integer.parseInt(temp[0])-1; int second=Integer.parseInt(temp[1])-1; matrix[first][second]="1"; matrix[second][first]="1"; } } 

iterates over input1 incorrectly to populate matrix . As a result, the last inputs are ignored (you can also see that j is not used at all inside the inner loop). Therefore, you should change it to the correct iteration:

 for (int i = 0; i < input1.length; i++) { String[] temp = input1[i].split("#"); int first = Integer.parseInt(temp[0]) - 1; int second = Integer.parseInt(temp[1]) - 1; matrix[first][second] = "1"; matrix[second][first] = "1"; } 

(You can also improve it further in the foreach loop, since you don't need the value of i )

I discovered this by debugging your code and finding out that it does not recurs to some nodes, and then I realized that matrix was incomplete. You must type matrix to check if this is correct.

Some other problems:

• You must reset your visited array when tracing back, otherwise you will not evaluate two different paths passing through the same node (uncomment visited[path]=false; )
• You don’t need a flag : in both cases you should check if you have a new “high score” and reduce the node_covered before leaving the loop
• Your code will not work if there is a city that is not connected to the rest of the schedule, because your Set hs will be too small. Try to find the node with the highest number.

Some possible improvements:

• Convert matrix to boolean . This will also eliminate the need to initialize it.
• You do not need 2 parameters for getNextPath() . Try to do everything you need with visited_node in the calling place. Then you can simplify it.
• If you manage to reduce it to 1 parameter, you will not need 2 nested for loops to initialize the recursion.