New answers tagged graph-traversal
1
Let $\ell_x$ be the left sub tree at node $x$, Let $r_x$ be the right sub tree at node $x$. So the size of $\ell_x$ is $\mid\ell_x\mid$, and size of $r_x$ is $\mid r_x\mid$.
Let $T(n)$ be number of nodes our procedure visited during in-order traversal.
So when you recurs on the left sub tree at node $x$, the size of problem is $T(n-1-\mid r_x\mid)$, because ...
2
Union find is a data structure (not an algorithm!) that maintains a collection of disjoint sets $\mathcal{S} = \{ S_1, S_2, \dots \}$ under union operations (i.e., replace two sets with their union) and find operations (given an element $x$, report the set $S_i$ containing $x$).
Hopefully it is already clear to you that if, at any point in time, two distinct ...
3
This is the Hamiltonian path problem on partial grid graphs (i.e., graphs which are arbitrary subgraphs of grids) which is known to be NP-complete. Thus, no polynomial algorithm exists unless P = NP.
A good bet here would be to try heuristics and (exact) algorithms designed for Hamiltonian path. In particular, if you model the problem as an instance of ...
2
Any primitive operation that can be done with edge list, also can be done in adjacency list, but the main difference between them is time complexity of the primitive operations, for example, when you want find all adjacent vertices to some vertex $v$ the time complexity is $\Theta(|E|)$ but the same operation on adjacency list is $\Theta(deg(v))$ where $...
2
I think what you're looking for, like I was, is the Minimum Spanning Tree. Here is an article about it.
1
Use BFS from some arbitrary node $v$ in that set. Then, denote by $u_1,\dots,u_k$ the nodes that you want to go through, and take the path $u_1\rightsquigarrow v\rightsquigarrow u_2 \rightsquigarrow v \rightsquigarrow\dots\rightsquigarrow u_k$.
If you want to start at the first layer and end at the last layer then just append a path from any node on the ...
Top 50 recent answers are included
