Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

67 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

Shortest Path using DFS on weighted graphs

I read that shortest path using DFS is not possible on a weighted graph. I pretty much understood the reason of why we can't apply on DFS for shortest path using this example:- Here if we follow ...
144 views

Distance of a Graph node to a group of nodes?

Consider a graph where edges represent the similarity of two nodes. In general, the graph is sparse with edges existing between only similar nodes (I can achieve this by deleting edges with similarity ...
183 views

Efficient algorithm to find an vertex that is not an articulation vertex

This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201. Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion ...
40 views

Finding continuous line consisted of points surrounding points of different color

I have a problem with creating an algorithm that would find continuous line consised of points of one color (say blue) that surrounds points of different color (say red). This problem occurs in "Dots"...
318 views

What is the time and space complexity of unidirectional bfs and bidirectional bfs?

How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?
470 views

Finding a path visiting most nodes in complete digraph with cost limit and positive or negative edge weights

I'm leaving out some specifics because this is a challenge problem and I don't want to be spoon-fed the answer, but I need a nudge in the right direction. I am given a complete digraph with the ...
278 views

Making DFS more efficient

I was looking for non-recursive implementation of DFS algorithm. I found the following pseudocode on this page. ...
35 views

How to choose the maximum vertices you can delete from set while atleast 1 of its neighbors is in set?

We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected: ...
168 views

What is the algorithmic complexity of DFS under the cache oblivious model?

Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size &...
596 views

Traveling Salesman problem solution for small graph?

So let's say i have a graph like this and salesman starts his journey at "A" How do i solve the TSP problem for this graph with pen and paper on exam?
470 views

Fastest Algorithm to find shortest path between two edges in a graph

If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)? I am trying to answer a question in the EPI book. ...
47 views

optimal path for traversing nodes

So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least ...
581 views

Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
159 views

Generalized steps to find tree traversal for any m-ary tree

So far I've read traversal techniques $(Pre-Order, In-Order, Post-Order)$ on binary trees. But In exam I've thrown up with a question, which requires me to find in-order traversal of a ternary tree. I ...
498 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...