如何在图中通过给定路径覆盖最大数量的节点

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

没有正确地在CCD_ 1上迭代以填充CCD_。因此，最后的输入被忽略(您还可以看到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";
}

(您可能还想将其进一步改进为foreach循环，因为您不需要i的值)

我通过调试您的代码并发现它不会递归到某些节点中发现了这一点，然后我发现matrix是不完整的。您应该打印matrix来检查它是否正确。

其他一些问题：

• 回溯时必须重置visited数组，否则将不会计算通过同一节点的两个不同路径(取消注释visited[path]=false;)
• 你不需要flag：在这两种情况下，你都应该检查你是否有新的"高分"，并在离开循环之前减少input10
• 如果有一个城市没有连接到图的其余部分，则您的代码将失败，因为您的Set hs太小。请尝试查找具有最高数字的节点

一些可能的改进：

• 将matrix转换为boolean矩阵。这也将消除初始化它的需要
• getNextPath()不需要2个参数。试着在呼叫地点用visited_node做你需要的一切。然后，您应该能够进一步简化它
• 如果您设法将其减少为1个参数，则不需要2个嵌套的for循环来启动递归