Page 1 of 1

DFS

Posted: Mon Jun 11, 2012 1:12 am
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
``````

Re: DFS

Posted: Mon Jun 11, 2012 2:32 pm
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 }
``````

Re: DFS

Posted: Mon Apr 29, 2013 4:01 pm
someone could write an efficient code on c++? i just want to know 2 or 3 differents ways to do it.