2,259 questions
0
votes
1
answer
50
views
DFS-compatible coordinate-free neighbors in Haskell
I've recently found myself solving a lot of 2D matrix search problems. A typical approach looks like the skeleton below, which searches for a word along 4-directionally connected paths in a 2D array:
...
- 513
2
votes
1
answer
46
views
Why are back edges and forward edges said to be impossible in BFS for an undirected graph?
Is it true that there are no back edges and no forward edges in a BFS of an undirected graph?
I feel this is incorrect. Here is my counterexample (graph is represent using adjacency list):
0 : 1
...
- 123
2
votes
1
answer
70
views
String representation of a tree (nodes) data structure with paths from left to right
Given a tree-like data structure of nodes with each node having a property children that contains the children nodes from left to right, I wish to create a string representation of this data structure ...
- 974
0
votes
1
answer
34
views
How to make an BFS algorithm from an array of integers
There is such a task:
There is an array of integers, you need to get from the very first element of the array to the last one in the minimum number of moves. You can move in two ways:
1 way: you can ...
- 1
1
vote
1
answer
73
views
Is BFS and a Tree Data Structure Sufficient for Comparing if two Trees are Structurally Equal?
I’m working on a problem where I need to compare multiple lineages (family trees) to check if they are structurally identical. Each lineage starts from a single root (ancestor) and extends downwards. ...
- 111
1
vote
2
answers
50
views
Time complexity of a BFS of a graph
I am unable to comprehend how the time complexity of the BFS of a graph is O(v+2E),
where V is the number of vertices and E being the number of edges.
/**
* @param {number} V
* @param {number[][]} ...
- 23
0
votes
0
answers
66
views
Find all spanning trees using BFS
While trying to find all spanning trees using the queue, I came to the conclusion that it would be logical to search edges. If there is no new edge in the tree, I add the edge to the tree and put the ...
- 1
1
vote
1
answer
57
views
Reduce memory use for Breadth-First Search
I am a novice to Comp Science topics. I have been struggling with reducing the memory use when performing a breadth-first search.
For demonstration:
Given a Directed Acyclical Graph (DAG) from Cormen ...
- 13
0
votes
2
answers
70
views
Splitting dag dependencies in python
Splitting dag dependencies in Python
I tried implementing a script for splitting dag dependencies, my goal is to split the node dependencies so that for each node that has more then one dependency, I ...
-1
votes
2
answers
77
views
Yield depth on a depth-first non-recursive tree walker?
I'm trying to find a non-recursive "powerful/versatile" tree walker algorithm, ultimately yielding not just the node but the depth of the node, its parent and its sibling index, and able to ...
- 15.5k
2
votes
0
answers
65
views
How do i iteratively traverse directory and parse it into struct in rust?
with some help, i was able to traverse directory and parse it into Collection struct recursively like this
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct Collection {
pub relative_path:...
- 95
1
vote
0
answers
20
views
Running a Breadth-First Search in Sql-G to get both vertices and edges
I am working on SqlG (https://sqlg.org/docs/3.1.0/) which is an extension of Apache TinkerPop for PostgreSql. I want to perform a breadth-first search from an initial vertex and get all the vertices ...
- 950
2
votes
1
answer
74
views
Depth First Search Time Complexity
Below is Python code for a depth search algorithm.
def add_edge(adj, s, t):
# Add edge from vertex s to t
adj[s].append(t)
# Due to undirected Graph
adj[t].append(s)
print('adj add ...
0
votes
0
answers
80
views
How to find the minimum distance between two matrices in python? (special definitions)
I have 4 permutation matrices A, B, C, D.
we define the distance d(C, D) to be the minimal number of matrix multiplications needed to satisfy the equation D = X.C.Y where the dot is matrix ...
- 143
3
votes
2
answers
110
views
Space Complexity of Dijkstra
I was working on some Leetcode questions for Dijkstra's algorithm and I do not quite understand the space complexity of it. I looked online but I found various answers and some were rather complicated ...
- 33
1
vote
2
answers
102
views
Is there any way to find the gird path in Minimum Path Sum
Minimum Path Sum:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Input: grid = [[1,3,1],[1,5,1],[...
- 39
0
votes
2
answers
61
views
|BFS| I have a question regarding problem number 133 on LeetCode
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
...
-12
votes
1
answer
185
views
Knight's journey solution gives incorrect output?
The knights journey where we are given the start/end points and the size of board(n*n):
Find the minimum steps to reach the end from the starting point. If no path is there return -1:
I've tried ...
- 3
0
votes
0
answers
49
views
Why use two arrays of insertion_time and lowest_insert_time in Tarjans algorithm for Bridges in Graph? [duplicate]
I've been working on the LeetCode problem 1192. Critical Connections in a Network. From various sources, I have the following code:
class Solution {
int timer = 1;
void dfs(int node, int ...
- 11
1
vote
1
answer
73
views
Why is BFS is much quicker than DFS when I implement both of them?
I am trying to use DFS and BFS to find all simple paths that have lengths up to a given k, starting at a given vertex in a directed graph. No cycles are allowed.
My code is as follows, and I have ...
- 75
2
votes
0
answers
114
views
Are BFS and DFS the same and just the Monad is different?
I wrote a tail-recursive BFS in Scala:
import scala.collection.mutable
/** Do BFS from start and return the smallest distance to end (None if not connected) */
def bfs[A](start: A, end: A, neighbors: ...
- 33.3k
0
votes
1
answer
45
views
Why is the time complexity of bidirectional bfs still O(V+E)?
I understand that if the branching factor of the graph is b and distance of goal vertex from source is d, then the time complexity is O(b^d).
I also understand why that would be O(b^d/2) using ...
- 1,150
2
votes
2
answers
90
views
Leetcode 417 BFS Time Limit Exceeded
I am working on Leetcode 417 Pacific Atlantic Water Flow:
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and ...
- 35
0
votes
1
answer
48
views
Issue with circular reference infinite loop when doing BFS on a multidimensional matrix
When doing a Breadth First Search on a Multidimensional Matrix where some cells are blocked, I am getting a circular reference and going into an infinite loop.
How would I backtrack my BFS search to ...
- 11
1
vote
0
answers
37
views
Depth Search between CFGs in BFS algorithm using python with LLVM IR
Context: I am trying to find out the depth between two CFGs using BFS but the code is not properly working as it's only showing the results up to depth 0 and 1 but it's not showing the other depths ...
- 11
-2
votes
1
answer
333
views
detect a cycle using BFS , there is a question on leetcode about course schedule [closed]
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ...
1
vote
1
answer
48
views
Nearest exit from an entrance in a maze
I am trying to solve the following question
https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/?envType=study-plan-v2&envId=leetcode-75
This is my approach
def insidemaze(r,c,nrow,...
0
votes
0
answers
27
views
BFS total memory consumption
For a graph with branching factor 12, the goal at depth 6, and each state taking 120 bytes, how much space BFS takes to keep states in its frontier to search the graph? How much space Depth First ...
2
votes
2
answers
262
views
BFS implementation takes too much time for CSES labyrinth problem
I am trying to solve the CSES Labyrinth problem:
You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.
Input
The first input ...
- 23
0
votes
1
answer
67
views
Finding Biconnected components(blocks) in graph using BFS
I am searching for a code (in any language) that finds biconnected components in a graph using breadth-first search. I am beginner in coding and have an assignment for this algorithm and tried to ...
1
vote
2
answers
91
views
BFS implementation for leetcode problem fails one test case
I am trying to solve a LeetCode problem (1219. Path with Maximum Gold) with BFS approach
Statement:
In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of ...
- 161
1
vote
1
answer
46
views
Confusion in Proof for Breadth First Search Finding Shortest Path in CLRS
I am reading CLRS (https://pd.daffodilvarsity.edu.bd/course/material/book-430/pdf_content), and stuck on the proof of Theorem 22.5 - Correctness of Breadth First Search on Page 600.
The author is ...
0
votes
1
answer
27
views
Level Order Insertion on an Orderless tree
I am attempting to use breadth first search to add to a node to an orderless tree
Tree: Unordered
Node: Each node groups together 3 datapoints, which are usernames
Children: 3 nodes
My current code is ...
- 11
-2
votes
1
answer
55
views
got a hashing error while coding 8 puzzle problem using bfs in python
I wrote a code in python for solving 8 puzzle problem using breadth first search algorithm but I got a hashing error instead in the line 'if child.state not in visited:'.
I wrote a code in python for ...
0
votes
3
answers
113
views
How to reconstruct the shortest path with BFS (Javascript) for Knight chess piece?
I'm currently working for a project with TOP and I'm asked to find the shortest path between 2 squares with a Knight on a 8x8 chessboard. Imagine I want to go from 0,0 to 7,7, my algo need to return ...
- 31
0
votes
3
answers
105
views
C++ Passing Parameters for a Function Pointer that is a Parameter to Another Function?
I want to write Breadth-First Search and Depth-First Search functions for a graph. But these functions should be able to take a function as a parameter so I can pass each node in the graph to the ...
0
votes
1
answer
136
views
DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations
Problem
I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
- 363
-3
votes
1
answer
53
views
Leetcode BFS Set insertion giving TLE (200. Number of Islands)
I am trying to solve the problem: Number of Islands on Leetcode using BFS traversal
When I try to add the (r,c) pair in the visited set first thing in the loop, it gives me TLE in Leetcode.
Code for ...
-1
votes
1
answer
50
views
Why DFS and not BFS for finding cycle in graph [duplicate]
Give the reasons for the above my query
I find the above questions of the traverse of graph. Bfs and DFS both are the traverse to detect the cycle in a graph but most is the dfs why this is the best ...
0
votes
0
answers
89
views
Approach for solving a Breadth first search(BFS) components problem
I am trying to solve this code challenge:
A new king in the North must quickly gather bannermen to defend their realm. Advisers have assessed the map, determining the minimum number of bannermen ...
- 155
0
votes
0
answers
25
views
Breadth First Search Causing Heap Memory Error With exponentially growing graph
I am writing a breadth first search to find a winning move for a block slider board game (image of example below)
The game aims to move pieces out of the way so the red piece can exit the stage.
This ...
- 125
-2
votes
1
answer
66
views
Undirected Graph, get list of all nodes that can be visited
I am new into graph theory I have this, problem I have a graph that will be diferent each time, I want to know if there is an algorithm to know from a random node which nodes I can visit, this ...
- 13
0
votes
0
answers
29
views
Algorithm to connect every node between each level of a graph / tree
I have a problem where I need to be able to find the unique combinations of data spread across n arrays. Each array can contain around 2 to 15 values. In essence I think what I'm looking for is the ...
- 299
5
votes
2
answers
158
views
Generate tuples of non-negative integers closed under promotion? [closed]
Let n be a positive integer, and let S be a set of n-tuples of non-negative integers. (For example, if n is 3, then S could be {(1,2,0), (1,0,1)}.)
Let's define an operation called "promote" ...
- 508
-2
votes
1
answer
28
views
Finding goal through BFS and DFS
I have this undirected, unweighted graph:
I need to find the search paths from node S to node O using depth-first search (DFS) and breadth-first search (BFS). Ties should be broken alphabetically.
I ...
- 7
0
votes
1
answer
141
views
Number of islands problem Leetcode recursive DFS and non recursive BFS
I was trying to fix the following leetcode problem using a recursive DFS approach and a non-recursive BFS approach. Both work, but the recursive DFS one is 3 ms fast vs the non-recursive BFS which is ...
1
vote
1
answer
69
views
Print path to node in a 2D dictionary-structured graph
This question is slightly inspired by the Infinite Craft neal.fun game. I've managed to build a graph structure representing the alchemy additions. For example, { "Water": { "Fire":...
- 1,256
0
votes
1
answer
83
views
BFS Maximize Minimum Distance from a Monster along a path
A player begins on a 2d grid of size n*m. 'E' refers to the end position the the player is trying to get to, 'S' represents the start position and 'X' refers to a monster. There can be multiple ...
- 125
0
votes
0
answers
55
views
Find the path with the minimum number of transfers between stations?
Input data format
N (number of edges, 1 ≤ N ≤ 1000),
next N lines with a pair of numbers for vertices, two numbers representing the start and end stations.
Output data format
Number of transfers.
If ...
- 11
1
vote
2
answers
77
views
BFS ever failing for a unweighted and undirected graph?
So I am just doing some work for my algorithms class and I was just wonder does a BFS tree ever fail on finding the single source shortest path I know that BFS finds the shortest path with the least ...
- 11