python (65.1k questions)

javascript (44.2k questions)

reactjs (22.7k questions)

java (20.8k questions)

c# (17.4k questions)

html (16.3k questions)

r (13.7k questions)

android (12.9k questions)

Questions - depth-first-search

Find all Cycles in the Directed Graph including back edges

Given a graph below, find all the possible path from vertex 1 to come back to 1 including back edges. Result: [1,2,3,2,1] [1,2,1] [1,2,3,1] I tried using DFS able to get only...
test-img

Arundhathi D

java

algorithm

graph

graph-theory

depth-first-search

Votes: 0

Answers: 1

Latest Answer

You were close to the answer. In order to detect a cycle in a graph, you need to use the Depth first search algorithm. That's correct. But there are a couple of things in your solution that has to imp...
test-img

Alexander Ivanchenko

What is wrong with this Coin Change solution using DFS with memoization?

I've solved Leetcode's Coin Change 2 problem with a DFS + memoization approach in Python, with the solution below # O(m*n) def change(amount: int, coins: List[int]) -> int: cache = {} ...
test-img

user3613025

c++

depth-first-search

memoization

Votes: 0

Answers: 1

Latest Answer

Your memoization in the C++ solution looks at index and amount (a constant), when your Python one looks at index and a. Changing it accordingly fixes it, i.e [...] if (dp[index][a] != -1) { r...
test-img

Julien BERNARD

Connected Component in Undirected Graph in python

Find connected component in undirected graph. Each node in the graph contains a label and a list of its neighbors. this is the link: https://www.lintcode.com/problem/431/ Leetcode requires membership ...
test-img

Yilmaz

python

algorithm

graph-theory

depth-first-search

Votes: 0

Answers: 1

Latest Answer

Your condition if not node: doesn't make sense: you're not modifying nodes or making them Falsey. Depth first search explores a forest of rooted trees. Your outer loop over nodes looks for the roots o...
test-img

kcsquared

How to I code Depth First Search without recurrence

How to implement Depth First Search code in python without recurrence. I have done it by class and recurrence method. the following is by recurrence method: graph1 = { 'A' : ['B','C','F'], 'B' : ['A',...
test-img

Red_Haired_Shanks

python

depth-first-search

Votes: 0

Answers: 1

Latest Answer

Basically by explicitly managing a stack instead of using the function call stack. Based on your first variant, function dfs will look like: def dfs(graph,node): stack = [node] while stack: ...
test-img

Michael Butscher

Posts

Questions

Blogs

Jobs