Tag Info

Hot answers tagged graph-traversal

43

I'd like to quote an answer from Stack Overflow by hstoerr which covers the problem nicely: That heavily depends on the structure of the search tree and the number and location of solutions. If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth ...

37

One point that's important in our multicore world: BFS is much more easy to parallelize. This is intuitively reasonable (send off threads for each child) and can be proven to be so as well. So if you have a scenario where you can make use of parallelism, then BFS is the way to go.

31

(I made this a community wiki. Please feel free to edit.) If $b$ is the branching factor $d$ is the depth where the solution is $h$ is the height of the tree (so, $d\le h$) Then DFS takes $O(b^h)$ time and $O(h)$ space BFS takes $O(b^d)$ time and $O(b^d)$ space IDDFS takes $O(b^d)$ time and $O(d)$ space Reasons to choose DFS must see whole tree anyway ...

28

Tree Examples (image): A: B: ‾‾ ‾‾ 1 1 / / \ 2 2 3 / 3 This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3. Tree B root׳s value is 1, ...

24

When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to ...

22

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 data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always ...

20

Wikipedia has the answer: All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails. This will explain the diagram:- Forward edge: (u, v), where v is a descendant of u, but not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree....

17

One scenario (other than finding the shortest path, which has already been mentioned) where you may have to choose one over the other to get a correct program would be infinite graphs: If we consider for example a tree where each node has a finite number of children, but the height of the tree is infinite, DFS might never find the node you're looking for - ...

15

Breadth-first and depth-first certainly have the same worst-case behaviour (the desired node is the last one found). I suspect this is also true for averave-case if you don't have information about your graphs. One nice bonus of breadth-first search is that it finds shortest paths (in the sense of fewest edges) which may or may not be of interest. If your ...

13

If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order. Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller ...

12

It is NP-complete to even decide whether any path exists. It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem. Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem: ...

10

Transposing the adjecency matrix $A$ does $\qquad A[i,j] = 1 \iff A^T[j,i] = 1$. In terms of graphs, that means $\qquad u \to_G v \iff v \to_{G^T} u$. In other words, transposing reverses the direction of all edges. Note that $G^T$ has the same strong components as $G$. The algorithm you are looking at is Kosaraju's algorithm. Be carful with your notion ...

10

A path of length $n$ consists of $n$ line segments in the plane. You want to find all intersections between these line segments. This is a standard problem that has been studied in depth in the computer graphics literature. A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric ...

10

There are exponentially many such routes. Think of a sequence of $n$ diamonds. At each diamond, you can go either left or right, independently of what you do at all other diamonds. This leads to $2^n$ paths, each of which is non-intersecting. Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on ...

10

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges: 1-connectedness (ie. between any 2 nodes in a tree there is exactly one path) any node can serve as the root of the tree. Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ ...

9

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 a vertex that has been discovered before such that that vertex is not an ancestor or descendent of the current vertex. Such an edge is called a cross edge.

9

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 path will always occur between two leaf nodes( nodes having only one edge linked). This can also be proved by contradiction that if longest path is between two ...

9

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 Wikipedia article by "For each child: traverse the subtree rooted at that child by recursively calling the traversal function". We assume that the for-loop ...

8

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. Perhaps the following simpler example will make this clear: PROCEDURE A(n) 1 global = 0 2 for i from 1 to n: 3 B(i) 4 return global PROCEDURE B(i) 1 ...

8

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 appropriate when the graph is only defined implicitly and may be infinite, or where you've decided in advance that you're only going to search to a fixed depth. An ...

8

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 solve. The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits ...

8

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 $1,2,\dots,n$. This means that we can name the nodes of any binary tree structure so that it will generate the same pre-order sequence as that of another ...

8

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, o o o o o / / / \ \ \ o o o o o o . / \ ...

7

First of all, it depends a bit how you can access your data to say which algorithms works best. Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that \text{height}(v)=\begin{...

7

A depth first search on a directed graph can yield 4 types of edges; tree, forward, back and cross edges. As we are looking at undirected graphs, it should be obvious that forward and back edges are the same thing, so the only things left to deal with are cross edges. A cross edge in a graph is an edge that goes from a vertex $v$ to another vertex $u$ such ...

7

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., this one on Wikipedia, then you can see that the algorithm adds attributes to nodes. E.g., the Wikipedia version adds to each node the attributes distance and ...

6

In the long run, it's really better to understand the graph theory terminology, but for now, here is an explanation of Christofides's algorithm. I'm not an expert in this area so I can't offer much by way of intuition. Also, I should note that by now, better algorithms are known for some variants, see for example the recent survey by Vygen. We denote the ...

6

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 operation until you reach the root). Suppose without loss of generality that $d(\alpha) \geq d(\beta)$. Replace $\alpha$ with $\alpha$'s $(d(\alpha) - d(\beta))$'...

6

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 construct a sequence $v_1,v_2,\ldots$ of nodes starting with $v_1 = s$ and $v_2 = N(s,1)$ (if $\deg(s) = 0$ then $s$ is connected to $t$ iff $s = t$). Given \$v_{...

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