Come coprire il numero massimo di nodi tramite un determinato percorso in un grafico?

Question

Sto cercando di trovare il numero massimo di nodi coperti tramite un percorso in un dato grafico. Ho creato un programma usando la ricorsione, ma sta dando una risposta solo per un semplice grafico non su un grafico complicato.

L'input viene fornito in una stringa di tipo 1 # 2: il nodo 1 è collegato al nodo 2 o viceversa.

Ho creato una matrice della dimensione totale dei nodi e se il nodo è collegato, impostare 1 altro -1 nella matrice. Questa matrice viene utilizzata per calcolare il nodo coperto massimo nel percorso.

Codice:

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

Dove sto facendo errore nel codice di cui sopra?

Answer 1

Il problema principale è che non si memorizza la matrice completa. Questo ciclo:

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

non iterare correttamente sopra input1 per popolare matrix. Di conseguenza, gli ultimi input vengono ignorati (puoi anche vedere che j non viene utilizzato affatto nel ciclo interno). in tal modo si dovrebbe cambiare per una corretta iterazione:

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

(Si consiglia inoltre di migliorare ulteriormente per un foreach ciclo dal momento che non è necessario il valore di i)

ho scoperto questo eseguendo il debug del codice e capendo che non è presente in alcuni nodi e quindi ho pensato che lo matrix fosse incompleto. È necessario stampare matrix per verificare se è corretto.

Alcuni altri problemi:

• È necessario ripristinare l'array visited quando backtracking, altrimenti non sarà possibile valutare 2 percorsi diversi che passano attraverso lo stesso nodo (decommentare visited[path]=false;)
• non ti servono il flag: in entrambi i casi, dovresti controllare se hai un nuovo "punteggio elevato" e diminuire node_covered prima di lasciare il ciclo
• Il tuo codice fallirà se c'è una città che non è connessa a il resto del grafico, perché il tuo Set hs sarà troppo piccolo. Cerca invece il nodo con il numero più alto.

Alcuni possibili miglioramenti:

• Conversione matrix ad una matrice boolean. Ciò eliminerà anche la necessità di inizializzarlo.
• Non sono necessari 2 parametri per getNextPath(). Prova a fare tutto ciò che ti serve con visited_node nel luogo della chiamata. Dovresti quindi essere in grado di semplificare ulteriormente.
• Se riesci a ridurlo a 1 parametro, non avrai bisogno di 2 loop nidificati for per avviare la ricorsione.