java - 帮助遍历节点/输入文件读取

Question

所以我有这个作业，我一次读 1 行，用逗号分隔，例如

Atlanta, Philadelphia   
New York, Philadelphia   
Philadelphia, Chicago   
Washington, Florida
.....
up to a vast amount.. (I don't know the amount)

每条线代表两个位置之间的连通性(例如，亚特兰大连接到费城)创建连接的节点和不连接的节点，例如华盛顿和佛罗里达彼此连接但没有其他连接。

程序应该做的是读取文件并给定两个城市参数，如果已连接则它应该输出 Yes，如果未连接则输出 No。

我完成了我的程序，它可以工作，但效率不高。我不知道我能做什么。这是使代码效率低下的程序的一部分。

第一个输入读取文件，因此我可以确定不同城市列表的大小，它还会删除任何重复的城市。

private static void createCityList() throws IOException{

        try {
            FileReader a = new FileReader(file);
            BufferedReader br = new BufferedReader(a);
            String line;
            line = br.readLine();

            while(line != null){
                StringTokenizer st = new StringTokenizer(line, ",");
                while(st.hasMoreTokens()){ 
                    String currentToken = st.nextToken();
                    if(!cityList.contains(currentToken.trim())){ 
                        cityList.add(currentToken.trim());
                    }//if
                }//while hasMoreTokens
                line = br.readLine();//read the next line
            }//while line != null
            br.close();
        }//try

        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        length = cityList.size(); // set length to amount of unique cities

    }//createCityList

执行另一个文件读取的第二种方法...允许我创建邻接矩阵

private static void graph() throws IOException{ 
    cityGraph = new int[cityList.size()][cityList.size()]; 

        try {
            FileReader a = new FileReader(file);
            BufferedReader br = new BufferedReader(a);
            String line;
            line = br.readLine();


            while(line != null){
                StringTokenizer st = new StringTokenizer(line, ",");
                while(st.hasMoreTokens()){ 
                    String firstToken = st.nextToken().trim();
                    String secondToken = st.nextToken().trim();
                    cityGraph[cityList.indexOf(firstToken)][cityList.indexOf(secondToken)] = 1; 
                    cityGraph[cityList.indexOf(secondToken)][cityList.indexOf(firstToken)] = 1; 
                }//while hasMoreTokens

                line = br.readLine();//read the next line

            }//while line != null

            br.close();

        }//try

        catch (FileNotFoundException e) {
            e.printStackTrace();
        }//catch
    }//graph

我的 final方法在这 2 个城市上运行 DFS 以确定其是否已连接

private static void isConnected(String s1, String s2){

        city1 = cityList.indexOf(s1); //set city to the index of s1 or s2 in the cityList LinkedList.
        city2 = cityList.indexOf(s2); 


        int startNode = city1;
        q.add(startNode); // start node

        while(!q.isEmpty()){
        //visit vertex
            for(int i = 0; i < length; i++){
                if(cityGraph[startNode][i] == 1){
                    if( i == city2 ){ 
                        System.out.println("yes");
                        return;
                    }//if city2 found
                    q.add(i);
                    cityGraph[startNode][i] = 0; //Set to visited
                }//if vertex exist
            }//for
            q.remove();//remove the top element and start with new node
            if(!q.isEmpty()){
                startNode = (Integer) q.element();
            }//if

        }//while q is not empty     
        System.out.println("no");
    }//isConnected

我试图只读取一个文件，但我在从未知大小制作矩阵时遇到问题，只有在读取文件后我才能找出大小。任何帮助或建议都会非常有用赞赏!

Answer 1

我对代码有几点意见:

1) 获取第一个代码片段中的那些行:

while(st.hasMoreTokens()){ 
    String currentToken = st.nextToken();
    if(!cityList.contains(currentToken.trim())){ 
        cityList.add(currentToken.trim());
    }//if
}//while hasMoreTokens

cityList.contains() 方法在城市数量上消耗线性时间，while(st.hasMoreTokens()) 可能运行 O( V^2) 次，其中 V 是顶点数，因为您可以拥有密集图。所以，就在这个循环中，你消耗了 O(V^3) 时间，这已经比 DFS (O(V + E) O(V^2 ) 在密集图中)。你无法加速 O(V^2) 循环，因为你必须读取所有边，但你可以使用更高效的数据结构来保存该城市列表，即哈希 (O(1) 查找，O(1) 插入)。

2) 在第二个代码片段上:

while(st.hasMoreTokens()){ 
    String firstToken = st.nextToken().trim();
    String secondToken = st.nextToken().trim();
    cityGraph[cityList.indexOf(firstToken)][cityList.indexOf(secondToken)] = 1; 
    cityGraph[cityList.indexOf(secondToken)][cityList.indexOf(firstToken)] = 1; 
}//while hasMoreTokens

完全一样。使用哈希而不是列表。

3) DFS 的内部循环

if(cityGraph[startNode][i] == 1){
    if( i == city2 ){ 
        System.out.println("yes");
        return;
    }//if city2 found
    q.add(i);
    cityGraph[startNode][i] = 0; //Set to visited
}//if vertex exist

有两个问题。一是每次运行 DFS 时都会覆盖图形表示。通过设置 cityGraph[startNode][i] = 0;，您实际上是在删除图形的一条边。如果您要为每个 DFS 重建图形，那将是一个巨大的问题。

第二个问题是，在我看来，您以错误的方式标记了已访问的节点。您只是标记已访问的 EDGES，而不是节点。如果你有路径 1 -> 2 和路径 1 -> 4 -> 2，你将访问(并添加到队列)节点 2 两次。

要解决这两个问题，请使用 boolean visited[#cities] 数组。每次启动 DFS 时，都会将所有节点设置为未访问。每次检查边缘时，都会检查您是否已经访问过该节点。如果没有，将其添加到队列中。

最后一点，

q.remove();//remove the top element and start with new node
if(!q.isEmpty()){
    startNode = (Integer) q.element();
}//if

这很丑陋，因为您已经在 while 循环中检查队列是否为空。相反，您可以将此代码移动到 while 循环的开头，删除 if 条件(因为您知道队列不为空):

while(!q.isEmpty()){
    startNode = (Integer) q.element();
    q.remove();

希望对您有所帮助....