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

Question

我试图通过给定图表中的路径找出覆盖节点的最大数量.我已经使用递归制作了一个程序,但它只给出了一些简单的图形,而不是复杂的图形.

输入以字符串数组(如1#2)给出:表示节点1连接到节点2,反之亦然.

我已经制作了一个总节点大小的矩阵,如果节点连接,则在矩阵中设置1,否则为-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";
}

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

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

其他一些问题：

• 回溯时必须重置visited数组，否则将无法评估经过同一节点的 2 条不同路径（取消注释visited[path]=false;）
• 您不需要flag：在这两种情况下，您应该检查是否有新的“高分”并node_covered在离开循环之前减少
• 如果有一个城市未连接到图表的其余部分，您的代码将会失败，因为您的城市Set hs太小了。尝试寻找编号最大的节点。

一些可能的改进：

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