图树检查

Question

- 我已经编写了代码来检查输入文件中作为邻接列表给出的图是否为树并将其输出到输出文件中。

- 评论解释了在每个阶段发生的操作。

--adjacencyList.get（no_of_vertices）= new ArrayList（）;行是给编译错误

The left-hand side of an assignment must be a variable 

- 任何人都可以在代码中指出。

import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.Collections; 
import java.util.Iterator; 
import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 
import java.io.PrintWriter; 

public class isTree implements Comparator<Integer> { 

    /* Variables used :: 
     (1) adjacencyList -- Contains the adjacency list as an array after being extracted from list. Each row contains all vertices connected 
          to the corresponding vertex given by row. 
     (2) no_of_edges -- Contains number of edges in the graph 
     (3) no_of_vertices -- Contains number of vertices in graph 
     (4) result   -- Contains whether a graph is a tree or not 
    */ 
    ArrayList<ArrayList<Integer>> adjacencyList = new ArrayList<ArrayList<Integer>>(100); 
    int no_of_edges=0; 
    int no_of_vertices=0; 
    String result; 

    /* Operation control function which calls all other functions on the graph input provided. */ 
    private isTree(String input_file,String output_file){ 
     createArrayList(input_file);  
     no_of_edges = findingEdges(adjacencyList); 
     if(!result.equals("Not a Tree")){ 
      if(checkCondition1(no_of_edges,no_of_vertices) && checkCondition2(adjacencyList,no_of_vertices)) 
       result = "Its a Tree"; 
      else 
       result = "Not a Tree"; 
     } 
     printingResultInFile(output_file); 
    } 

    /* Creation of ArrayList from the input File by extracting line by line and using comma delimiter to split the numbers in each line 
     which are then stored as vertices in increasing order in the adjacency row of the list. */ 
    private void createArrayList(String input_name){ 
     int j; 
     String line; 
     String [] vertices; 
     Scanner in=null; 
     int len; 
     try { 
      in = new Scanner(new File(input_name)); 
     }catch(FileNotFoundException e) { 
      System.out.println("File Not Found"); 
     } 
     while(in.hasNextLine()){ 
      List<Integer> rowList = adjacencyList.get(no_of_vertices); 
     rowList = new ArrayList<Integer>(); 
     line = in.nextLine(); 
     if(line.equalsIgnoreCase("null")){ 
      no_of_vertices++; 
      continue; 
     } 
     vertices = line.split(","); 
     len = vertices.length; 
     for(j=0;j<len;j++){ 
      rowList.add(Integer.parseInt(vertices[j])); 
     } 
     Collections.sort(rowList); 
     no_of_vertices++; 
     } 
    } 
    public int compare(Integer a,Integer b){ 
      if(a >= b) 
       return 1; 
      else 
       return -1; 
    } 

    /* Finding number of edges by calculating the total number of vertices in all the rows of adjacency list and dividing by 2 since edge 
     edge relation is symmetric. */ 

    private int findingEdges(ArrayList<ArrayList<Integer>> adjacencyList){ 
     int i; 
     for(i=0;i<no_of_vertices;i++){ 
      if(adjacencyList.get(i).contains(i)){ 
       result = "Not a Tree"; 
       return -1; 
       } 
      else{ 
       no_of_edges = no_of_edges+adjacencyList.get(i).size(); 
      } 
     } 
     no_of_edges = no_of_edges/2; 
     return no_of_edges; 
    } 

    /* Takes in 2 inputs firstly 'e' which is the number of edges and secondly 'v' which is number of vertices 
     in the graph. Since a tree satisfies e = v - 1 relation we are checking this relation in the function */ 

    private boolean checkCondition1(int no_of_edges,int no_of_vertices){ 
     if(no_of_edges == no_of_vertices - 1) 
      return true; 
     else 
      return false; 
    } 

    /* Implementing Depth First Search as explained below: 
     (1)Pushes vertex 1 to the stack. 
     (2)Checks if vertex 1 is not there in template list and adds. 
     (3)It pops vertex 1 out and adds it to template 
     (4)It pushes all vertices connected to 1 to stack if they are not present on template list. 
     (5)It pops a vertex from stack and adds it to template list and adds all its connected vertices to 
      the stack if they are not present in the template list. 
     (6)This is repeated until the stack is empty. 
    */ 
    private boolean checkCondition2(ArrayList<ArrayList<Integer>> adjacencyList,int no_of_vertices){ 
     pArrayStackInt stack = new pArrayStackInt(no_of_vertices); 
     int j=1,k; 
     ArrayList<Integer> template = new ArrayList<Integer>(); 
     stack.push(1); 
     while(!stack.isEmpty()){ 
      j=stack.pop(); 
      template.add(j); 
      Iterator<Integer> itr = adjacencyList.get(j-1).iterator(); 
      j++; 
      while(itr.hasNext()){ 
       k=itr.next(); 
       if(!template.contains(k)) 
        stack.push(k); 
      } 

     } 
     if(template.size()==no_of_vertices) 
      return true; 
     else 
      return false; 
    } 

    /* Printing whether the given input file is a tree or not onto the output file depending upon the value stored 
     in result variable */ 

    private void printingResultInFile(String output_file){ 
     PrintWriter out=null; 
     try { 
      out = new PrintWriter(output_file); 
     } 
     catch (FileNotFoundException e) { 
      System.out.println("File Not Found"); 
     } 
     out.write(result); 
     out.close(); 
    } 

    /* 2 inputs are provided at the runtime as arguments firstly input_file name and secondly output file name. 
     Input file name is stored in args[0] and Output file name is stored in args[1]. With these input file name 
     and output file name a new instance of isTree is created */ 

    public static void main(String[] args){ 
     String input_file = args[0]; 
     String output_file = args[1]; 
     new isTree(input_file,output_file); 
    } 
} 
/* Implementing stack data structure by providing push, pop and isEmpty operations */ 
class pArrayStackInt{ 
    private int head[]; 
    private int pointer; 

    public pArrayStackInt(int capacity){ 
     head = new int[capacity]; 
     pointer = -1; 
    } 
    public boolean isEmpty(){ 
     return pointer == -1; 
    } 
    public void push(int i){ 
     if(pointer+1 < head.length) 
      head[++pointer] = i; 
    } 
    public int pop(){ 
     return head[pointer--]; 
    } 
} 

Answer 1

应该List<Integer> someName = adjacencyList.get(no_of_vertices); 的.get()返回一个ArrayList<Integer>，你必须关闭保存到另一个变量以后使用它。