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

问题描述：

所以我有这个任务，我一次读了一行，每次用逗号隔开，例如，帮助遍历节点/输入文件读取

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

这确实另一FILEREAD第二方法......让我以创建邻接矩阵

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

我想只有一个文件读取，但我有问题从一个未知的大小制作矩阵它只有在文件读取后，我发现大小。任何帮助或建议将大大赞赏！

答

我对代码几点意见：

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循环的beggining，去除如果条件（因为你知道的队列不为空）：

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

希望帮助....

答

这是一个双向或单向图吗？

无论采用哪种方式，您都可以使用地图来表示从一个城市到另一个城市的边缘。鉴于此，您可以编写一个方法

Set getReachableNodes（String startingNode，Map reachability）;

并查看期望的目标是否在结果集合中。

实际上，我不知道，如果它的双向或uni我给出的小样本输入文件不需要双向来获取跨地点的方式 – xiaolin 2011-02-17 05:04:04

您可以详细说明使用Map的含义吗？我实际上从来没有使用过它..地图上有一个关键字和一个附加值。我怎样才能使用这个来实现city1连接city2，它连接到city6 ...等等...... – xiaolin 2011-02-17 05:10:35

是的，假设你有String标签，使用`Map `来表示从一个节点（关键字）到另一个（值）。所以说有从奥克兰到圣何塞，圣何塞到奥克兰，从奥克兰到旧金山的边缘： – 2011-02-17 05:14:12

答

我认为好软件的关键在于选择最佳的数据结构。我认为这比程序更重要（当然这些重要）。我不相信二维数组是一个巨大的图表，而大量的城市列表是最佳的数据结构;对于这两种类型的数据结构，您都不得不进行线性搜索。这意味着随着这些数据结构的增长，速度会变得更糟。

因此，我建议重新设计您依靠HashMap<String>和HashSet<String>。 HashMap的主要价值是不断查找时间，这意味着性能不会变得更糟（如果您对它的工作原理感兴趣，请参阅Wikipedia上的更多内容）。

因此，如上述一些答案建议，在伪轮廓是：

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加）和 m.put（C2，加入C1组）

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

相关推荐