Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
8 votes
Accepted

How to determine the time and memory complexity for solving a sliding-tile puzzle?

The complexity of the BFS and DFS algorithms depend heavily on the graph being analyzed, and the search strategy being used. If we have a method to consistently get "closer" to a solution, ...
Exalted Toast's user avatar
6 votes
Accepted

How to represent BFS and DFS between adjacency matrix and list?

Maybe not exactly what you are looking for, but there is a really cool and natural way to represent BFS with an adjacency matrix. Consider a graph $G = (V, E)$ and its adjacency matrix representation $...
codeing_monkey's user avatar
5 votes
Accepted

What is the relation between Topological Sort and Strongly Connected Components?

One connection could be the following: Given a graph $G$, construct the graph $G'$ in which every connected component of $G$ is a node, and two nodes in $G'$ have a (directed) edge if there is an edge ...
nir shahar's user avatar
  • 11.6k
5 votes
Accepted

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

The MST of $G$ is not well-defined since there might be multiple MSTs of a graph. However, it can be shown that: Claim 1: either all MSTs use only edges with integer weights or none of them does. ...
Steven's user avatar
  • 29.5k
4 votes

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

A simple algorithm Here is the simplest and fastest algorithm to determine the MST of $G$ only uses edges with an integer weight. It runs in $O(E\,\alpha(V))=O(n\,\alpha(n))$ time. Define weight ...
John L.'s user avatar
  • 39k
3 votes
Accepted

Maximum Independent Set of special Directed Graph

The type of graph you are describing is identical to the one encountered in Pollard's rho algorithm. Connected components of your graph are cycles with directed trees feeding into them (possibly none)....
Yuval Filmus's user avatar
2 votes
Accepted

Iterative Depth First Search for cycle detection on directed graphs

Using the same logic as the recursive algorithm, I added on the stack a pos value which keeps track of the position of the last descendant currently processing. ...
saifrim's user avatar
  • 41
2 votes

First-time and second-time seen edges in DFS on undirected graphs

Here is the simplest example. Let the graph contain two vertices, $x$ and $y$ with one edge $\{x,y\}$. Here is a run of the algorithm. $x$ and $y$ are marked as "undiscovered". $y$ is ...
John L.'s user avatar
  • 39k
2 votes

What's the name of this DFS variation

This tree traversal sounds similar to a Best-first traversal where the heuristic function is based on your weight function w. This strategy uses a priority queue (e....
tylerh111's user avatar
  • 392
2 votes

Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node

Assume the graph is a directed acyclic graph throughout. The algorithm is correct In the first recursion, the algorithm finds a node $u$ that has no incoming edges. In the second recursion, the ...
John L.'s user avatar
  • 39k
2 votes

What is the correct complexity of All paths from Source to Target DFS solution?

First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots ...
Guanaco96's user avatar
  • 101
2 votes
Accepted

pictorial representation of pre and post ordering for edge types

"I am assuming that $u$ is the node/vertex we see first and then we see $v$ later." That is a wrong assumption, which makes that summarizing table unintelligible. The right assumption ...
John L.'s user avatar
  • 39k
2 votes
Accepted

Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?

First of all keep in mind that this is just an analogy meant to convey the intuition behind the DFS algorithm on graphs. Now graphs can be directed, which would correspond to having a labyrinth with ...
Steven's user avatar
  • 29.5k
2 votes

Find palindrome in directed Graph where edges are either blue or red

Here's a possible algorithm. Construct a graph $G'$ with $|V|^2$ vertices where each vertex is labeled with the pair $(a, b)$ with $a, b$ being vertices in $G$. Then, construct all possible edges $(a, ...
orlp's user avatar
  • 13.6k
2 votes
Accepted

Print all nodes which are the endpoint of the diameter of a tree

One-line takeaway: a tree has either one center or two adjacent centers, which are shared by all diameters. The clue to solve the problem faster is sort of hidden in the symmetric tree given in the ...
John L.'s user avatar
  • 39k
2 votes
Accepted

Connectivity in Directed Graph

The problem that you stated is known as the Graph Reachability Query problem. You may want to check this paper: An Efficient Algorithm for Answering Graph Reachability Queries, and the references ...
Inuyasha Yagami's user avatar
2 votes
Accepted

In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest

Yes use induction. You will assume that $G_\pi$ is a forest, and you want to prove that $G_{\pi'}$ is also a forest, where $\pi'$ is $\pi$ after one step of the DFS algorithm. The key point, is that a ...
nir shahar's user avatar
  • 11.6k
2 votes
Accepted

For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross trees

Consider the following graph: A possible DFS starting from $a$ visits the vertices in this order: $\langle a, b, c, d \rangle$ producing the cross-edge $(c,b)$. A possible DFS starting from $b$ ...
Steven's user avatar
  • 29.5k
2 votes

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

Here is one way to do it. First get all the integer edges $E_{\mathbb{Z}}=\{e_1, ..., e_k\}$ in $O(m)=O(n)$ time. Since their weights are integers and bounded by $O(n)$, you can use bucket sort/radix ...
AspiringMat's user avatar
2 votes

Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book

I'm not sure what the problem is, but I will still try to answer. The predecessor of $v$ in a path from $u$ to $v$ is the last vertex seen before $v$. Since there exists a path from $u$ to $v$ then, ...
Nathaniel's user avatar
  • 15.7k
2 votes
Accepted

Minimizing/Maximizing recursion depth for DFS

Unfortunately, I think that that there is a reduction from the longest path problem, which have a $\mathsf{NP}$-complete decision version (finding the maximum depth is equivalent to finding the ...
Nathaniel's user avatar
  • 15.7k
2 votes
Accepted

Checking if there exists a 'source' vertex

Hint: if you find all the strongly connected components in the graph, the quotient graph of the SCCs is a DAG. In this DAG, if there is a meta-node that can reach all the other meta-nodes, you have ...
Pål GD's user avatar
  • 16.4k
1 vote

Transforming from neighbour representation to grid representation

Pick an arbitrary node. Assign it the coordinates $(0,0)$. Now run any graph traversal algorithm -- say, depth-first search. When you visit a node, you know its coordinates. Now you can look at ...
D.W.'s user avatar
  • 160k
1 vote

Is DFS better than BFS for space complexity when finding path from root to a node in a tree?

To keep it short and simple, the answer is yes. BFS, in addition to the set of visited nodes, makes use of queue for unprocessed ...
Aarush Aggarwal's user avatar
1 vote

Is DFS better than BFS for space complexity when finding path from root to a node in a tree?

In the case of the binary tree, and assuming your binary tree is balanced, yes, I think you will be using more space at any given time in general with BFS. DFS would be allocating and releasing memory ...
Carlos R.F.'s user avatar
1 vote

Check if two graphs are edge-disjoint

The adjacency matrix $A_G$ of an undirected graph $G=(V,E)$ is defined as follows: $A_G$ is a $V \times V$ matrix, $A_G(v,v) = 0$ for all $v \in V$, and $A_G(u,v) = 1$ if $\{u,v\} \in E$ and $A_G(u,v) ...
Yuval Filmus's user avatar
1 vote
Accepted

DFS produces the correct Topologically ordered sequence

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph. Now to prove that the ...
devam_04's user avatar
  • 285
1 vote
Accepted

find the strong component containing the vertex v

Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the ...
Nathaniel's user avatar
  • 15.7k
1 vote

Alternatives for finding sources in a DAG

Use a priority queue to keep a list of all vertices with prioritization on in-degrees. Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$. Repeat ...
Pål GD's user avatar
  • 16.4k

Only top scored, non community-wiki answers of a minimum length are eligible