28
votes
Accepted
Can the pre-order traversal of two different trees be the same even though they are different?
Tree Examples (image):
...
- 576
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 ...
- 976
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 ...
- 185
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 ...
- 121
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 ...
- 1,473
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 ...
- 275k
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.♦
- 156k
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 ...
- 38.6k
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....
- 275k
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.,...
- 238
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 ...
- 81.4k
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 ...
- 275k
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 $...
- 29.8k
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 ...
- 81.4k
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 ...
- 838
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
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 ...
- 275k
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 ...
- 1,996
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 ...
- 12.5k
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 ...
- 29.8k
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 ...
D.W.♦
- 156k
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.5k
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.
- 275k
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.♦
- 156k
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 ...
- 81.4k
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, ...
- 3,252
5
votes
Accepted
Archaeological Consistency: Graph Problem
Denote the time of birth of person $A$ by $b_A$, and their time of death by $d_A$, and suppose for simplicity that all of these times are different. We know that:
For every person $A$, $b_A < d_A$....
- 275k
5
votes
Are reversed reverse preorder traversals equivalent to a postorder traversal?
Nathaniels simple and elegant proof is the best way to formally convince yourself your conjectures are true. I want to add a more informal and visual explanation.
The postorder traversal of a binary ...
- 29.8k
Only top scored, non community-wiki answers of a minimum length are eligible