DFS

[Phantom]

Here an example of DFS in Python:

Code: Select all

def DFS(graph, pos):
    marks = [False] * len(graph)
    marks[pos] = True
    for i in __DFS(graph, pos, marks):yield i

def __DFS(graph, pos, marks):
    for i in graph[pos]:
        if not marks[i]:
            marks[i] = True
            yield i
            for j in __DFS(graph, i, marks):yield j

#Example:           
graph = [[3], [0, 2, 5], [3, 4], [1, 0], [5, 3], [0, 1, 2, 3]]
for i in DFS(graph, 1): print i

[Phantom]

Here an example of DFS in Ruby:

Code: Select all

def DFS(graph, pos)
marks = [false] * graph.size
marks[pos] = true
__DFS(graph, pos, marks){ |i| yield i }
end

def __DFS(graph, pos, marks)
   for i in graph[pos]:
     if !marks[i]
        marks[i] = true
        yield i
        __DFS(graph, i, marks){ |j| yield j }
     end
   end
end

#Example:
graph = [[3], [0, 2, 5], [3, 4], [1, 0], [5, 3], [0, 1, 2, 3]]
DFS(graph, 1){ |i| puts i }

[Spartan]

someone could write an efficient code on c++? i just want to know 2 or 3 differents ways to do it.