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

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

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

每条线代表两个位置之间的连通性（例如，亚特兰大连接到费城），创建连接的节点和没有像华盛顿和佛罗里达那样连接的节点彼此连接但没有其他人连接。该程序假设要做的是读取文件并给出两个城市参数，它假设吐出是，如果它连接/否，如果不是。我完成了我的程序并且它工作，但它效率不高。我很难过我能做什么。以下是使代码效率低下的程序的一部分。第一个输入读取文件，以便我可以确定不同城市列表的大小，并且还删除任何重复的城市。

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

我的最终方法在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

我正在尝试只读取一个文件，但是我遇到的问题是从一个未知的大小制作一个矩阵，只有在我找到大小的文件读取之后。任何帮助或建议都会很大不胜感激！

已邀请:

3 个回复

鞘垒飘

我对代码有一些评论： 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();

希望有所帮助....

孝箱捆讨

这是双向还是单向图？无论哪种方式，您都可以使用Map来表示从一个城市到另一个城市的边缘。鉴于此，您可以编写一个方法设置getReachableNodes（String startingNode，Map reachability）; 并查看所需目标是否在结果集中。

嘘伪

我认为良好软件的关键是选择最佳数据结构。我认为这比程序更重要（当然，这些程序很重要）。我不相信一个巨大的图形的二维数组和大量城市的列表是最佳的数据结构;对于这两种类型的数据结构，您不得不进行线性搜索。这意味着随着这些数据结构的大小增加，速度将变得更糟。所以我建议重新设计你依赖HashMap<String>和HashSet<String>。 HashMap的主要价值是持续的查找时间，这意味着性能不会变差（如果您对它的工作方式感兴趣，可以在维基百科上阅读更多内容）。因此，正如上面提到的一些答案所示，伪代码的轮廓将是：

HashMap<String, HashSet<String>> m = new ...
For each pair c1 c2 {
     if c1 is not a key in m {
          HashSet<String> set = new HashSet<String>
          set.add(c2)
          m.put(c1, set);

     }
     else //c is a key
          m.get(c1).add(c2)
 }

现在查看c1和c2是否连接：

boolean isDirectlyConnected(c1, c2) { 
  return m.get(c1).contains(c2) || m.get(c2).contains(c1) 
}         

boolean isConnected (c1, c2) {    //checking the transitive closure of directly connected
   HashSet<String> citiesAlreadyChecked = new ...   //cities whose edges have already been checked
   Queue<String>  citiesToCheck = new ...
   citiesToCheck.push(c1)
   while (citiesToCheck is not empty) {
         String cityBeingCurrentlyChecked = citiesToCheck.pull
         if (isDirectlyConnected(cityBeingCurrentlyChecked,c2)) {
               return true;
         } 
         else {
               citiesAlreadyChecked.add(cityBeingCurrentlyChecked)
               for (String adjacentCity: m.get(cityBeingCurrentlyChecked)) {
                    if (adjacentCity is not in citiesAlreadyChecked) {
                           citiesToCheck.push(adjacentCity)
                    }
               }
          }
    }
    return false  
   //transitive colsure of cities connected to c1 have been checked, and c2 was not found there.

}

人们还可以使图形双重链接，从而摆脱||在isDirectlyConnected中。在通过调用构建时完成双重链接 m.put（c1，添加c2设置）AND m.put（c2，添加c1设置）

要回复问题请先登录或注册

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

3 个回复

发起人

filereader

adjacency_matrix

问题状态

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

与内容相关的链接

3 个回复

发起人

filereader

adjacency_matrix

问题状态