Skip to main content
28 votes
Accepted

Can the pre-order traversal of two different trees be the same even though they are different?

Tree Examples (image): ...
royashcenazi's user avatar
23 votes

What is the meaning of 'breadth' in breadth first search?

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue. The “frontier” is the set of all nodes in the search ...
Throckmorton's user avatar
14 votes

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

The intuition behind is very easy to understand. Suppose I have to find longest path that exists between any two nodes in the given tree. After drawing some diagrams we can observe that the longest ...
MayankPratap's user avatar
12 votes
Accepted

Linear-time algorithm to find an odd-length cycle in a directed graph

Let $G$ be strongly connected. Run BFS (!) from an arbitrary vertex $s$. BFS creates a leveled tree where level of a vertex $v$ is it's directed distance from $s$. If while running BFS you have never ...
Denis Pankratov's user avatar
10 votes

Can the pre-order traversal of two different trees be the same even though they are different?

Counting argument The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes, ...
CR Drost's user avatar
  • 376
10 votes

O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

Your algorithm is known as greedy coloring. Wikipedia gives an example of a bipartite graph, the crown graph, where the greedy coloring can produce a coloring using $n/2$ colors (for the worst ...
Yuval Filmus's user avatar
10 votes
Accepted

What don't I understand in topological sort using DFS?

Main misunderstanding is when nodes are added to the answer - you add them when you leave them, right before/at backtracking So you check A, check C, find that C is terminal - so you add C at the end ...
Noone AtAll's user avatar
9 votes

Why does DFS only yield tree and back edges on undirected, connected graphs?

Let $G=(V,E)$ to be a graph and $u$ and $\nu$ to be its vertices such that $\{u,v\}\subseteq V$ and $(u,\nu)\in E$. Suppose that $u$ is discovered first. Consequently, its color is changed to gray. ...
molexi's user avatar
  • 191
9 votes

Can Breadth-First Search be Implemented Recursively without Data Structures?

You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity. Embedded-Queue Cheating If you look at virtually any description of BFS, e.g.,...
Ami Tavory's user avatar
9 votes
Accepted

Why is the running time for BFS $O(b^{d+1})$?

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to ...
D.W.'s user avatar
  • 162k
9 votes
Accepted

What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?

No, you are not missing anything if you remove $S$ completely. You could implement and run Dijkstra's algorithm correctly still. Set $S$ is used later in the book to help explain the algorithm and ...
John L.'s user avatar
  • 39k
9 votes
Accepted

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

Using the idea of @Mahyar, I think there is another way to find a solution to the problem. Given a tree $T= (V, E)$, find a bipartition of $T = (X\sqcup Y, E)$ (using a simple graph traversal). ...
Nathaniel's user avatar
  • 15.9k
8 votes
Accepted

Time complexity of Depth First Search

The book is counting the number of times each line is executed throughout the entire execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT....
Yuval Filmus's user avatar
8 votes

Why is the running time for BFS $O(b^{d+1})$?

The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is ...
David Richerby's user avatar
8 votes
Accepted

Logspace algorithm for s-t connectivity in undirected forests

This is proved by Cook and McKenzie. We make use of the following notation: $\deg(v)$ is the degree of a vertex $v$. $N(v,1),\ldots,N(v,\deg(v))$ is some fixed ordering of the neighbors of $v$. We ...
Yuval Filmus's user avatar
8 votes

Can the pre-order traversal of two different trees be the same even though they are different?

Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $...
Hendrik Jan's user avatar
  • 30.7k
8 votes

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted ...
David Richerby's user avatar
8 votes

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

We can weight vertices such that the entire tree has a fixed sum of weights; for example, zero. Let us design a recursive procedure that assigns weights to the vertices of a tree $T$ with root $r$ ...
Mahyar's user avatar
  • 81
7 votes

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

Update 3 and corrected answer There's an error in the linked solution set (see update 2 below), but it can be easily corrected with @Yuval Filmus's suggestion in the question's comment, which further ...
xdavidliu's user avatar
  • 858
7 votes

Why is DFS considered to have $O(bm)$ space complexity?

It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in Wikipedia, and suppose that you run it on a tree so that you don't have to keep track of which ...
Yuval Filmus's user avatar
6 votes
Accepted

Is it possible to reconstruct graph if we have given matrix of shortest pairs

I would suggest the following approach. Maintain a data structure $H$ of $(i,j, g(i,j))$ triples so that you can efficiently find and remove a triple $(i,j,w)$ that minimises $w$. Maintain a ...
Jukka Suomela's user avatar
6 votes
Accepted

Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?

For a given vertex, the only thing that matters in the algorithm is if there is an edge from the vertex or a child-vertex to a ancestor-vertex in the DFS exploration tree. In this case, we know that ...
Thophane Vallaeys's user avatar
6 votes
Accepted

Are reversed reverse preorder traversals equivalent to a postorder traversal?

This can be proven by induction on trees. I give details on the conjecture 1 here. It is clearly true for the empty tree and for leaves; Suppose it is true for trees $l$ and $r$. Consider $t$ a node ...
Nathaniel's user avatar
  • 15.9k
5 votes
Accepted

Vertex cover of a graph by removing leaf-vertices from a DFS tree

Look at the definition of vertex cover (as provided by the book). It is strictly defined on undirected graphs. Thus, the answer doesn't apply to directed graphs, nor to any other kinds of graphs you ...
Juho's user avatar
  • 22.6k
5 votes

Breadth-first forest

This asymmetry reflects a "philosophical" difference between the two algorithms. Let us think for a moment about what each of them is trying to achieve. DFS investigates properties related to the ...
quicksort's user avatar
  • 4,262
5 votes
Accepted

Mother vertex of a graph

Find the strongly connected components. If the component graph has more than one source, then there are no mother vertices. Otherwise, the mother vertices are those that belong to the single source.
Yuval Filmus's user avatar
5 votes
Accepted

What do we do instead of DFS on directed graphs?

The issue is not specific to DFS. When looking at directed graphs, even for connected graphs not all nodes are reachable from everywhere. That's why the notion of a graph being strongly connected ...
Raphael's user avatar
  • 72.7k
5 votes
Accepted

Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time?

No, there isn't (not unless P=NP). Take an unweighted directed graph on $n$ vertices, and set all of the edge weights to $-1$. Now there is a simple cycle of weight $-n$ if and only if there is a ...
D.W.'s user avatar
  • 162k
5 votes
Accepted

Breadth First Search actually require specifically Queue instead of any other type of Collection?

It doesn't literally have to be a queue. Anything that ensures that one level is completely explored before moving to the next one would suffice. However, the most natural way to do this is with a ...
David Richerby's user avatar
5 votes
Accepted

Shortest path with a start vertex that touches all nodes at least once with repeats allowed

Your problem is just a TSP in disguise. 1. Dealing with "visit each node at least once" First, compute a modified distance matrix $D(i,j)$, $i,j=1,...,n$ using an all-pairs shortest path algorithm, ...
Vincenzo's user avatar
  • 3,397

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