Как покрыть максимальное количество узлов по заданному пути в графе?

Question

Я пытаюсь выяснить максимальное количество покрытых узлов по пути в заданном графе. Я сделал программу, использующую рекурсию, но она дает ответ только для некоторого простого графика не на сложном графике.

Ввод задается в строковом массиве, таком как 1 # 2: означает, что узел 1 подключен к узлу 2 или наоборот.

Я создал матрицу общего размера узлов, и если узел подключен, установите 1 else -1 в матрицу. Эта матрица используется для вычисления максимального охваченного узла в пути.

Код:

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

Где я делаю ошибку в коде выше?

Answer 1

Ваша основная проблема заключается в том, что вы не храните полную матрицу. Этот цикл:

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

не правильно перебирать input1 для заполнения matrix. Вследствие этого последние входы игнорируются (вы также можете видеть, что j не используется вообще во внутреннем цикле). Вы, таким образом, следует изменить его на правильной итерации:

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

(Вы также можете улучшить его дальше к Еогеасп цикла, так как вам не нужно значение i)

Я обнаружил это отлаживая ваш код и выясняя, что он не рекурсирует в некоторые узлы, а затем я понял, что matrix был неполным. Вы должны напечатать matrix, чтобы проверить, правильно ли это.

Некоторые другие вопросы:

• Вы должны сбросить visited массив при возвратов, в противном случае вы не сможете оценить 2 разных пути, которые проходят через тот же узел (раскомментируйте visited[path]=false;)
• Вам не нужно flag: в обоих случаях вы должны проверить, есть ли у вас новый «высокий балл» и уменьшить node_covered перед выходом из цикла
• Ваш код не будет работать, если есть город, который не подключен к остальная часть графика, потому что ваш Set hs будет слишком мал. Попробуйте искать узел с наивысшим числом.

Некоторые возможные улучшения:

• Преобразовать matrix к boolean матрицы. Это также устранит необходимость его инициализации.
• Вам не нужны 2 параметра для getNextPath(). Постарайтесь сделать все, что вам нужно, с visited_node в вызывающем месте. Затем вы сможете упростить его.
• Если вам удастся уменьшить его до 1 параметра, вам не понадобится 2 вложенных цикла for, чтобы инициировать рекурсию.