如何使图遍历算法适用于大图？

Question

我正在编写一种算法，以便在给定源和目标时遍历图形。该算法应该遍历并在图中显示从源到目的地的所有可能路径。我正在使用广度优先搜索来执行此操作，并且它在小图中工作。但是当提供一个巨大的图（有超过 1000 个顶点）时，程序似乎被冻结并且在很长一段时间后没有显示任何输出。我可以知道如何解决这个问题吗？

我做过的一个简单的测试（小图）

    graph.addVertex("A", 25);
    graph.addVertex("B", 60);
    graph.addVertex("C", 45);
    graph.addVertex("D", 75);
    graph.addVertex("E", 95);
    graph.addVertex("F", 85);
    graph.addVertex("G", 105);

    graph.addEdge("A", "B", "AB", "");
    graph.addEdge("A", "D", "AD", "");
    graph.addEdge("A", "C", "AC", "");
    graph.addEdge("A", "E", "AE", "");
    graph.addEdge("B", "E", "BE", "");
    graph.addEdge("E", "F", "EF", "");
    graph.addEdge("E", "G", "EG", "");
    graph.addEdge("D", "C", "DC", "");
    graph.addEdge("D", "F", "DF", "");
    graph.addEdge("F", "G", "FG", "");
    graph.addEdge("C", "F", "CF", ""); 

    String str = graph.bfs("A", "G");
    System.out.println(str);

我的广度优先搜索算法

// SUBMODULE: bfs
// IMPORT: src (String), dest (String)
// EXPORT: T (String) 
public String bfs( String src, String dest )
{
    String T = "";
    DSAQueue Q = new DSAQueue();             // The queue will store linked list
    DSALinkedList path = null;                   // This is the list for queue
    DSALinkedList adj = null;                    // Adjacency for src

    adj = getAdjacent( src );

    // Make adjacent to linked list first and store in queue
    for( Object o : adj )
    {
        DSALinkedList ll = new DSALinkedList(); // Creating list for every iteration
        DSAGraphVertex vertex = (DSAGraphVertex) o;
        ll.insertLast( vertex );                // Every adjacent vertex is ele of list 
        Q.enqueue( ll );                        // Store the list to queue
    }

    // ASSERTION: We Iterate until Q is empty, Q will store all L[V]
    while( !Q.isEmpty() )
    {
        path = (DSALinkedList) Q.dequeue();          // Dequeue a linked list

        // Get the tail of list
        DSAGraphVertex v = (DSAGraphVertex) path.peekLast(); 

        // We found the complete list path when the tail is dest
        if( v.getLabel().equals(dest) )
        {
            T += src + " -> ";
            for( Object o : path )
            {
                DSAGraphVertex pathVertex = (DSAGraphVertex) o;
                T += pathVertex.getLabel() + " -> ";
            }
            T += "(END)\n";
        }
        else
        {
            // If v.getLabel() is not dest, we need to do bfs from adj of tail
            DSALinkedList tailAdj = v.getAdjacent();

            // Check the number of paths in this vertex
            if( v.getSize() == 1 ) 
            {
                /* If only one path found, simply traverse to the only one path */

                DSAGraphVertex headVertex = (DSAGraphVertex) tailAdj.peekFirst();    // head of the tailAdj
                path.insertLast( headVertex );                  
                Q.enqueue( path );
                headVertex = null;
            }
            else
            {
                /* If the vertex has more than one path, copy all the existing paths for 
                   every single connection, then insert the new node to each list */
                for( Object o : tailAdj )
                {
                    DSALinkedList newList = new DSALinkedList();
                    newList = copyList( path );                 // Copy the existing

                    // Then add the new node into the copied list
                    DSAGraphVertex currVertex = (DSAGraphVertex) o; 
                    newList.insertLast( currVertex );

                    // The queue now has a new list of paths 
                    Q.enqueue( newList );       
                    newList = null;
                }
            }
            tailAdj = null;
        }
        path = null;
    }
    return T;
}

Answer 1

1000 个节点并不算大。我想你的代码中某处有一个无限循环。让我们看看这里有一个可能的无限循环位置：while( !Q.isEmpty() )

啊，是的，我没有看到任何东西阻止您向队列中添加节点。队列应该只处理每个节点一次。您需要保留一个已添加到队列中且不允许再次添加的节点列表。

它不会很快停止，因为你永远不会停止向队列中添加东西，所以它永远不会为空。

你今天的课程：当你有一个只在满足条件时才结束的循环时，请加倍确保满足该条件的可能性。

如何使图遍历算法适用于大图？

How to make graph traversal algorithm to work with large graph?

java

breadth-first-search

infinite

graph-traversal

data-structures