如何在这段代码中实现深度优先搜索？

Question

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

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

如何在这段代码中实现深度优先搜索？

How Do Implement Depth First Search Into This Code?

stack

graph

depth-first-search