如何在该代码中实现深度优先搜索

Question

在这里有点挣扎。我想实现一个深度优先搜索，这是一个邻接列表图。正在全力工作，但我对实现这样的搜索有点一无所知。在开始DFS之前，是否需要添加堆栈类？任何帮助都会很棒！

class vertex:
    def __init__(self, label, edges = []):
        self.id = label
    self.edges = []
class graph(vertex):
    def __init__(self):
        self.vertices = {}
    def addVertex(self, label):            
        self.vertices[label] = vertex(label)
        return self.vertices              
    def addEdge(self,frm,to):
        self.vertices[frm].edges = self.vertices[frm].edges + [to]
        return self.vertices
    def dot(self):
        for v in self.vertices:
            for e in self.vertices[v].edges:
                print "%s -> %s;"%(v, e)
    def viewVertLink(self):
        for v in self.vertices:
            print ""
            print "Vertex:","(",v,")"
            for e in self.vertices[v].edges:
                print "%s -> %s;"%(v, e)

if __name__ == '__main__':
    g = graph()
    for i in range(10):
        str(g.addVertex(i))
    str(g.addEdge(0,1))
    str(g.addEdge(0,2))
    str(g.addEdge(1,3))
    str(g.addEdge(1,4))
    str(g.addEdge(2,3))
    str(g.addEdge(3,5))
    str(g.addEdge(4,5))
    str(g.addEdge(4,6))
    str(g.addEdge(6,7))
    str(g.addEdge(7,1))
    str(g.addEdge(7,8))
    str(g.addEdge(8,9))
    str(g.addEdge(9,0))

    print "digraph G{"
    g.dot()
    print "}"

Answer 1

我想提供的不仅仅是伪代码，但我不太理解您使用的语言。但的实施速度很快

Get a stack
mark your source as visited and push to stack
while stack is not empty
retrieve element on top of stack without removing it
Go through its adjacent nodes
if you find a node that has not been visited
mark it as visited and push into stack
repeat from source, except this time with the new item
else if all adjacent vertices have been visited pop the stack

下面是一个java实现

void dfs(int adjacency_matrix[][], int source){
    Stack<Integer> stack = new Stack<>();
    int numNodes = adjacency_matrix[source].length -1;
    boolean [] visited = new boolean[numNodes +1];
    visited[source] = true;
    stack.add(source);
    while(!stack.isEmpty()){
        int current = stack.peek(); // don't remove the element but get it
        System.out.println("Current node being visited is "+current);
        for(int x = 0; x <= numNodes; x++){
            if(adjacency_matrix[current][x] == 1 && visited[x] == false){
                visited[x] = true;
                stack.push(x);
                break;
            }else if(x == numNodes){
                stack.pop();
            }
        }
    }
}