28 votes
Accepted

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

Tree Examples (image): ...
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 ...
13 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 ...
12 votes

Difference between cross edges and forward edges in a DFT

A DFS traversal in an undirected graph will not leave a cross edge since all edges that are incident on a vertex are explored. However, in a directed graph, you may come across an edge that leads to ...
11 votes
Accepted

What does pre-, post- and in-order walk mean for a n-ary tree?

No, it's not limited to binary trees. Yes, pre-order and post-order can be used for $n$-ary trees. You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the ...
  • 145k
10 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 ...
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 ...
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 ...
  • 145k
9 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, ...
  • 366
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 ...
  • 35.5k
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....
8 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.,...
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 ...
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 $...
  • 28.2k
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 ...
7 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 as $\in$ $V$ and $(u,\nu)\in E$. Suppose that $u$ is discovered first. Consequently, its color is changed to gray. Then, $\nu$ ...
  • 181
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 ...
  • 818
7 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 ...
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 ...
6 votes
Accepted

LCA from children using bottom up approach?

Here is one approach. Given leaves $\alpha,\beta$, first compute the depths $d(\alpha),d(\beta)$ of both leaves (to compute the depth of a leaf, measure how many times you need to apply the parent ...
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 ...
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 ...
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 ...
  • 7,568
5 votes
Accepted

Finding the k-shortest path between two nodes

In the $k$ shortest path problem, we wish to find $k$ path connecting a given vertex pair with minimum total length. Eppstein [1] has an algorithm running in $O(m+n \log n + k)$ time to find the $k$ ...
  • 22.1k
5 votes
Accepted

Algorithm to determine whether a given graph is a caterpillar tree

When considering such recognition algorithms, it is sometimes helpful to consider equivalent characterizations of the graph in question. Your observations and ideas are valid. In other words, we can ...
  • 22.1k
5 votes
Accepted

How many number of different binary trees are possible for a given postorder (or preorder) traversal

Every binary tree (with the right number of nodes) has exactly one labelling that satisfies a given postorder labelling. So you need to find the number of binary trees. That is the famous Catalan ...
  • 28.2k
5 votes
Accepted

Efficient algorithm for finding weakly connected components

Replace every directed edge $u \to v$ with an undirected edge $(u,v)$. Now use any standard algorithm for finding connected components in the resulting undirected graph. One standard approach for ...
  • 145k
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 ...
  • 22.1k
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.
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 ...
  • 145k

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