2

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

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

我试图只读取一个文件，但我在从未知大小制作矩阵时遇到问题，只有在读取文件后我才知道大小。任何帮助或建议将不胜感激！

4

3 回答 3

2

我对代码有几点意见：

1）在第一个代码片段中使用这些行：

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

该cityList.contains()方法消耗城市数量的线性时间，以及 V 是顶点数量的while(st.hasMoreTokens())可能运行O(V^2)时间，因为您可以拥有密集图。O(V + E)因此，仅在这一循环中，您就消耗了 O(V^3) 时间，这已经比 DFS （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 重建图形，那将是一个大问题。

第二个问题是，在我看来，您以错误的方式标记访问过的节点。您只是标记访问的边缘，而不是节点。如果您有路径 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();

希望有帮助....

于 2011-02-17T05:22:02.113 回答
1

这是双向图还是单向图？

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

设置 getReachableNodes(String startingNode, 地图可达性);

并查看所需的目标是否在结果集中。

于 2011-02-17T04:54:50.120 回答
1

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

所以我建议重新设计你依赖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, set with c2 added) AND m.put(c2, set with c1 added)

于 2011-02-17T12:13:25.047 回答