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.
Post Reply
User avatar
Phantom
Posts: 58
Joined: 7 years ago
Location: Cuba
Gender: None specified

DFS

Post by Phantom » 6 years ago

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: 7 years ago
Location: Cuba
Gender: None specified

Re: DFS

Post by Phantom » 6 years ago

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: 6 years ago
Gender: Male
Cuba

Re: DFS

Post by Spartan » 5 years ago

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

Post Reply

Return to “Algorithms”