如何使图遍历算法能够处理大图?

huangapple go评论70阅读模式
英文:

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

问题

// 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 into a linked list first and store it in the queue
    for (Object o : adj) {
        DSALinkedList ll = new DSALinkedList(); // Creating a list for every iteration
        DSAGraphVertex vertex = (DSAGraphVertex) o;
        ll.insertLast(vertex);                // Every adjacent vertex is an element of the list 
        Q.enqueue(ll);                        // Store the list in the 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 the list
        DSAGraphVertex v = (DSAGraphVertex) path.peekLast(); 

        // We found the complete path when the tail is the destination
        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 the destination, we need to perform BFS from the adjacent vertices of the tail
            DSALinkedList tailAdj = v.getAdjacent();

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

                DSAGraphVertex headVertex = (DSAGraphVertex) tailAdj.peekFirst();    // head of 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 into each list */
                for (Object o : tailAdj) {
                    DSALinkedList newList = new DSALinkedList();
                    newList = copyList(path);                 // Copy the existing list

                    // 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;
}
英文:

I am writing an algorithm to traverse through the graph when given a source and destination. The algorithm should traverse and show all possible paths from source to destination in the graph. I am using Breadth First Search to do this and it worked in small graph. But when a huge graph is supplied (having more than 1000 vertex), the program seems to be freezed and does not show any output after a long time. May I know how to solve this?

A simple one test that I have conducted (small graph)

    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);

My Breadth First Search Algorithm

// 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;
}

答案1

得分: 0

1000个节点并不算是一个很大的图。我想你的代码中可能有一个无限循环。让我们看看你有一个可能出现无限循环的地方:while( !Q.isEmpty() )

啊,是的,我没有看到任何停止你将节点添加到队列的操作。队列应该只处理每个节点一次。你需要保持一个已经被添加到队列中的节点列表,并且不允许再次被添加。

它不会快速停止,因为你从不停止向队列中添加内容,所以它永远不会为空。

今天的教训是:无论何时你有一个只在满足条件时才结束的循环,请确保这个条件确实可以被满足。

英文:

1000 nodes isn't that big of a graph. I imagine you have an infinite loop somewhere in your code. Let's see here you have one possible place for an infinite loop: while( !Q.isEmpty() )

Ah yes, I don't see anything that stops you from adding nodes to the queue. The queue should only process each node once. You need to keep a list of nodes that have been added to the queue and are not allowed to be added again.

It doesn't stop quickly, because you never stop adding stuff to the queue, so it can never be empty.

Your lesson of the day: Whenever you have a loop that only ends when a condition is met, make doubly sure it's possible for that condition to be met.

huangapple
  • 本文由 发表于 2020年10月11日 15:45:04
  • 转载请务必保留本文链接:https://go.coder-hub.com/64301721.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定