DFS

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
User avatar
Phantom
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender: None specified

DFS

Postby Phantom » 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



User avatar
Phantom
Posts: 58
Joined: Thu Nov 17, 2011 11:21 am
Location: Cuba
Gender: None specified

Re: DFS

Postby Phantom » 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 }

Spartan
Posts: 11
Joined: Thu Apr 05, 2012 9:36 pm
Gender: None specified

Re: DFS

Postby Spartan » 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.


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest