# Tag Info

Accepted

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

Tree Examples (image): ...
• 576

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 ...
• 996

### 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 ...
• 305
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 ...
• 1,483

### 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, ...
• 376

### 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 ...
• 278k
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 ...
• 225

### 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. ...
• 191

### 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.,...
• 248
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 ...
• 162k
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 ...
• 39k
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). ...
• 15.9k
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....
• 278k

### 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 ...
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 ...
• 278k