The graph-traversal tag has no wiki summary.
0
votes
1answer
21 views
Sequential hash tree traversal
A lot of articles say that hash tree traversal cost to any randomly chosen leaf is $\mathcal{O}(\log_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at ...
0
votes
1answer
66 views
Why does DFS only yield tree and back edges on undirected, connected graphs?
Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.
Now, from intuition and in class lectures by Steven Skiena, I know ...
2
votes
1answer
40 views
Correctness of Strongly Connected Components algorithm for a directed graph
I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph ...
1
vote
0answers
73 views
Bridge determination in undirected graphs
A bridge (critical edge) in an undirected graph is an edge whose removal increases the number of connected components.
I need to determine all critical edges in an undirected graph, in $O(V+E)$ time. ...
1
vote
1answer
33 views
Difference between cross edges and forward edges in a DFT
In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal).
There are some leftover edges connecting some of the other nodes. What is the difference ...
1
vote
0answers
24 views
Node-weighted CSP in Prim's algorithm?
I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix:
$$
\left[ ...
3
votes
1answer
69 views
Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
3
votes
1answer
79 views
A Good Resource for Christofides' Heuristic
Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound?
To be specific:
(Disclaimer : I am an engineer who knows ...
1
vote
3answers
128 views
The purpose of grey node in graph depth-first search
In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex ...
1
vote
1answer
72 views
Dfs algorithm and cycles question
Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge?
Looks to me likes its true ,is it?
-1
votes
3answers
95 views
BFS in K shortest paths
Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes?
If so where can it be useful?
4
votes
3answers
191 views
Algorithm for getting the outer boundary of a large graph
I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of ...
1
vote
1answer
87 views
Calculating traversal position of a node in a full binary tree, given its path
Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in ...
5
votes
2answers
194 views
How do I structure hexagon edge data?
In my program, it draws them by offsetting every other row by half of the width, as pictured above. Each tile can be referenced by coordinates, also shown above.
I want to know how many blue ...
2
votes
0answers
23 views
Inferences about Branching in TSP algorithm
I am building a program that uses branching-and-bounding to find an optimal path in a complete graph (the heuristic, faster algorithm is the second part). I have to begin and end at node 0. I was ...
8
votes
3answers
175 views
Finding the height of all nodes in a forest
I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges ...
8
votes
1answer
278 views
Graphs that cause DFS and BFS to process nodes in the exact same order
For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are ...
2
votes
0answers
40 views
IDS algorithm optimality for grid?
My homework is implementing algorithms BFS, DFS, depth-limited and IDS for the map as a 2D grid with 8 directions of movement.
I read that the IDS algorithm is optimal, but in my case is not optimal ...
5
votes
0answers
164 views
Kosaraju-Sharir algorithm and the inserted vertex
This is a question from my homework and I need some help.
We are trying to run Kosaraju-Sharir algorithm over $G$, adirectional graph with arcs $(u,v)$. In the first DFS pass we inserted vertex $u$ ...
1
vote
1answer
194 views
Improve worst case time of depth first search on Euler graphs
How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point?
I need to do the whole search but it is not fast enough for ...
22
votes
6answers
2k views
Graph searching: Breadth-first vs. depth-first
When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).
Now, are ...
6
votes
3answers
115 views
Unique path in a directed graph
I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've ...
3
votes
3answers
49 views
Can two neighbors in a graph be at the same depth in a DFS tree?
In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)
