# Tag Info

Accepted

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

Tree Examples (image): ...

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

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

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

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

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

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

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